Optimal Estimation of the Number of Communities

In network analysis, how to estimate the number of communities <i>K</i> is a fundamental problem. We consider a broad setting where we allow severe degree heterogeneity and a wide range of sparsity levels, and propose Stepwise Goodness-of-Fit (StGoF) as a new approach. This is a stepwise algorithm, where for m=1,2,…, we alternately use a community detection step and a goodness-of-fit (GoF) step. We adapt SCORE [19] for community detection, and propose a new GoF metric. We show that at step <i>m</i>, the GoF metric diverges to ∞ in probability for all <i>m</i> &lt; <i>K</i> and converges to <i>N</i>(0, 1) if <i>m</i> = <i>K</i>. This gives rise to a consistent estimate for <i>K</i>. Also, we discover the right way to define the signal-to-noise ratio (SNR) for our problem and show that consistent estimates for <i>K</i> do not exist if SNR→0, and StGoF is uniformly consistent for <i>K</i> if SNR→∞. Therefore, StGoF achieves the optimal phase transition. Similar stepwise methods (e.g., [38, 34]) are known to face analytical challenges. We overcome the challenges by using a different stepwise scheme in StGoF and by deriving sharp results that are not available before. The key to our analysis is to show that SCORE has the <i>Non-Splitting Property (NSP)</i>. Primarily due to a non-tractable rotation of eigenvectors dictated by the Davis-Kahan sin (θ) theorem, the NSP is non-trivial to prove and requires new techniques we develop.