# Hypothesis Testing for Automated Community Detection in Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2013.

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

- [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)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Exact Recovery of Community Structures Using DeepWalk and Node2vec](https://mlsanity.com/paper/2101.07354/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [Detection problems in the spiked matrix models](https://mlsanity.com/paper/2301.05331/) (2023)
- [Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models](https://mlsanity.com/paper/2308.14988/) (2023)
- [A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrix](https://mlsanity.com/paper/2102.11658/) (2021)
- [Statistical embedding: Beyond principal components](https://mlsanity.com/paper/2106.01858/) (2021)
- [Spectral goodness-of-fit tests for complete and partial network data](https://mlsanity.com/paper/2106.09702/) (2021)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs](https://mlsanity.com/paper/2403.13286/) (2024)
- [Review on Determining the Number of Communities in Network Data](https://mlsanity.com/paper/2503.00352/) (2025)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Goodness-of-Fit Tests for Latent Class Models with Ordinal Categorical Data](https://mlsanity.com/paper/2602.21572/) (2026)

## Abstract (arXiv)

Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. The problem of finding communities or clusters in a network has received much attention from statistics, physics and computer science. However, most clustering algorithms assume knowledge of the number of clusters k. In this paper we propose to automatically determine k in a graph generated from a Stochastic Blockmodel. Our main contribution is twofold; first, we theoretically establish the limiting distribution of the principal eigenvalue of the suitably centered and scaled adjacency matrix, and use that distribution for our hypothesis test. Secondly, we use this test to design a recursive bipartitioning algorithm. Using quantifiable classification tasks on real world networks with ground truth, we show that our algorithm outperforms existing probabilistic models for learning overlapping clusters, and on unlabeled networks, we show that we uncover nested community structure.