On the Estimation of the Number of Communities for Sparse Networks

Neil Hwang, Jiarui Xu, Shirshendu Chatterjee and Sharmodeep Bhattacharyya

Journal of the American Statistical Association, 2024, vol. 119, issue 547, 1895-1910

Abstract: 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.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01621459.2023.2223793 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:jnlasa:v:119:y:2024:i:547:p:1895-1910

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/UASA20

DOI: 10.1080/01621459.2023.2223793

Access Statistics for this article

Journal of the American Statistical Association is currently edited by Xuming He, Jun Liu, Joseph Ibrahim and Alyson Wilson

More articles in Journal of the American Statistical Association from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().