On the Estimation of the Number of Communities for Sparse Networks
研究了基于Bethe Hessian矩阵谱的非参数方法在稀疏网络（节点平均度低于对数阶）中估计社区数量K的一致性问题，提出了在子对数稀疏区间的有效估计程序。
Among the nonparametric methods of estimating the number of communities (K) in a community detection problem, methods based on the spectrum of the Bethe Hessian matrices (Hζ with the scalar parameter ζ) have garnered much popularity for their simplicity, computational efficiency, and robustness to the sparsity of data. For certain heuristic choices of ζ, such methods have been shown to be consistent for networks with N nodes with a common expected degree of ω( log N). In this article, we obtain several finite sample results to show that if the input network is generated from either stochastic block models or degree-corrected block models, and if ζ is chosen from a certain interval, then the associated spectral methods based on Hζ is consistent for estimating K for the sub-logarithmic sparse regime, when the expected maximum degree is both o( log N) and ω(1), under some mild conditions even in the situation when K increases with N. We also propose a method to estimate the aforementioned interval empirically, which enables us to develop a consistent K estimation procedure in the sparse regime. We evaluate the performance of the resulting estimation procedure theoretically, also empirically through extensive simulation studies and application to a comprehensive collection of real-world network data. Supplementary materials for this article are available online.