Publication Type
Journal Article
Version
publishedVersion
Publication Date
4-2021
Abstract
We propose to estimate the number of communities in degree-corrected stochastic block models based on a pseudo likelihood ratio. For estimation, we consider a spectral clustering together with binary segmentation method. This approach guarantees an upper bound for the pseudo likelihood ratio statistic when the model is over-fitted. We also derive its limiting distribution when the model is under-fitted. Based on these properties, we establish the consistency of our estimator for the true number of communities. Developing these theoretical properties require a mild condition on the average degree: growing at a rate faster than log(n), where n is the number of nodes. Our proposed method is further illustrated by simulation studies and analysis of real-world networks. The numerical results show that our approach has satisfactory performance when the network is sparse and/or has unbalanced communities.
Keywords
Clustering, community detection, degree-corrected stochastic block model, K-means, regularization
Discipline
Computer Sciences | Econometrics
Research Areas
Econometrics
Publication
Journal of Machine Learning Research
Volume
22
Issue
69
First Page
1
Last Page
63
ISSN
1532-4435
Publisher
JMLR
Embargo Period
8-3-2021
Citation
MA, Shujie; SU, Liangjun; and ZHANG, Yichong.
Determining the number of communities in degree-corrected stochastic block models. (2021). Journal of Machine Learning Research. 22, (69), 1-63.
Available at: https://ink.library.smu.edu.sg/soe_research/2485
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Additional URL
https://jmlr.org/papers/v22/20-037.html