# Estimating the number of communities in networks by spectral methods

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2015.

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

- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Variational Estimators of the Degree-corrected Latent Block Model for Bipartite Networks](https://mlsanity.com/paper/2206.08465/) (2022)
- [Restricted Tweedie Stochastic Block Models](https://mlsanity.com/paper/2310.10952/) (2023)
- [SIMPLE-RC: Group Network Inference with Non-Sharp Nulls and Weak Signals](https://mlsanity.com/paper/2211.00128/) (2022)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [Simultaneous estimation of connectivity and dimensionality in samples of networks](https://mlsanity.com/paper/2508.12483/) (2025)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)

## Abstract (arXiv)

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.