# Community Detection in Sparse Random Networks

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2013.

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

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models](https://mlsanity.com/paper/2308.14988/) (2023)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [A practical test for a planted community in heterogeneous networks](https://mlsanity.com/paper/2101.05928/) (2021)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

We consider the problem of detecting a tight community in a sparse random network. This is formalized as testing for the existence of a dense random subgraph in a random graph. Under the null hypothesis, the graph is a realization of an Erd"os-R'enyi graph on N vertices and with connection probability p0; under the alternative, there is an unknown subgraph on n vertices where the connection probability is p1 > p0. In Arias-Castro and Verzelen (2012), we focused on the asymptotically dense regime where p0 is large enough that np0>(n/N)o(1). We consider here the asymptotically sparse regime where p0 is small enough that np0<(n/N)c0 for some c0>0. As before, we derive information theoretic lower bounds, and also establish the performance of various tests. Compared to our previous work, the arguments for the lower bounds are based on the same technology, but are substantially more technical in the details; also, the methods we study are different: besides a variant of the scan statistic, we study other statistics such as the size of the largest connected component, the number of triangles, the eigengap of the adjacency matrix, etc. Our detection bounds are sharp, except in the Poisson regime where we were not able to fully characterize the constant arising in the bound.