Optimal Estimation of the Number of Network Communities

• 成果类型: Article
• 署名作者: Jin, Jiashun; Ke, Zheng Tracy; Luo, Shengming; Wang, Minzhe
• 署名单位: Carnegie Mellon University; Harvard University
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2022.2035736
• 发表日期: 2023
• 页码: 2101-2116
• 关键词: model

摘要

In network analysis, how to estimate the number of communities K 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 Jin for community detection, and propose a new GoF metric. We show that at step m, the GoF metric diverges to infinity in probability for all m < K and converges to N(0,1) if m = K. This gives rise to a consistent estimate for K. Also, we discover the right way to define the signal-to-noise ratio (SNR) for our problem and show that consistent estimates for K do not exist if SNR -> 0, and StGoF is uniformly consistent for K if SNR -> infinity. Therefore, StGoF achieves the optimal phase transition. Similar stepwise methods 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 Nonsplitting Property (NSP). Primarily due to a nontractable rotation of eigenvectors dictated by the Davis-Kahan sin(theta) theorem, the NSP is nontrivial to prove and requires new techniques we develop. Supplementary materials for this article are available online.