# Determining the Number of Communities in Degree-corrected Stochastic Block Models

arXiv: https://arxiv.org/abs/1809.01028 · HTML: https://mlsanity.com/paper/1809.01028/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2018.

## Built on by (most cited first, 10 of 10)

- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Variational Estimators of the Degree-corrected Latent Block Model for Bipartite Networks](https://mlsanity.com/paper/2206.08465/) (2022)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [Restricted Tweedie Stochastic Block Models](https://mlsanity.com/paper/2310.10952/) (2023)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Individual-heterogeneous sub-Gaussian Mixture Models](https://mlsanity.com/paper/2604.05337/) (2026)

## Abstract (arXiv)

We propose to estimate the number of communities in degree-corrected stochastic block models based on a pseudo likelihood ratio statistic. To this end, we introduce a method that combines spectral clustering with binary segmentation. 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 degrees -- growing at a rate no slower 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 semi-dense.