On the Estimation of the Number of Communities for Sparse Networks

• 成果类型: Article
• 署名作者: Hwang, Neil; Xu, Jiarui; Chatterjee, Shirshendu; Bhattacharyya, Sharmodeep
• 署名单位: City University of New York (CUNY) System; City University of New York (CUNY) System; Oregon State University
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2023.2223793
• 发表日期: 2024
• 页码: 1895-1910
• 关键词: model; features

摘要

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. for this article are available online.