Power Enhancement and Phase Transitions for Global Testing of the Mixed Membership Stochastic Block Model
share
The mixed-membership stochastic block model (MMSBM) is a common model for social networks. Given an n-node symmetric network generated from a K-community MMSBM, we would like to test K=1 versus K>1. We first study the degree-based χ^2 test and the orthodox Signed Quadrilateral (oSQ) test. These two statistics estimate an order-2 polynomial and an order-4 polynomial of a "signal" matrix, respectively. We derive the asymptotic null distribution and power for both tests. However, for each test, there exists a parameter regime where its power is unsatisfactory. It motivates us to propose a power enhancement (PE) test to combine the strengths of both tests. We show that the PE test has a tractable null distribution and improves the power of both tests. To assess the optimality of PE, we consider a randomized setting, where the n membership vectors are independently drawn from a distribution on the standard simplex. We show that the success of global testing is governed by a quantity β_n(K,P,h), which depends on the community structure matrix P and the mean vector h of memberships. For each given (K, P, h), a test is called optimal if it distinguishes two hypotheses when β_n(K, P,h)→∞. A test is called optimally adaptive if it is optimal for all (K, P, h). We show that the PE test is optimally adaptive, while many existing tests are only optimal for some particular (K, P, h), hence, not optimally adaptive.
READ FULL TEXT