|
Abstract:
|
We are interested in testing whether a network has one community versus multiple communities. The test should (a) accommodate mixed-memberships, (b) have a tractable null distribution and (c) adapt to different sparsity levels. We derive the lower bound using a phase transition framework which identifies a Region of Impossibility, where no test can achieve nontrivial power while controlling type-I error. The Region of Possibility can be partitioned based on community structure into an asymmetric setting and a symmetric setting. We introduce three new statistics: the Degree Chi-Square (DCS) statistic, the orthodox Signed Quadrilateral (oSQ) statistic and the Power-Enhanced (PE) statistic which combines DCS and oSQ. We show that DCS is rate-optimal in the asymmetric setting and oSQ is rate-optimal in the symmetric setting. The PE statistic is optimally adaptive to both settings and follows a chi-square distribution with two degrees of freedom asymptotically under the null hypothesis. Our results yield novel insights into the limits of statistical inference in network models, as well as valuable tests for applications such as stopping rule design in recursive community detection.
|
