# Finding One Community in a Sparse Graph

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2015.

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

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Bayes optimal learning in high-dimensional linear regression with network side information](https://mlsanity.com/paper/2306.05679/) (2023)
- [Streaming Belief Propagation for Community Detection](https://mlsanity.com/paper/2106.04805/) (2021)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [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 a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for rm degrm in - rm degrm out > √rm degrm out/e and fail for rm degrm in - rm degrm out < √rm degrm out/e (with rm degrm in, rm degrm out the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for rm degrm in - rm degrm out < √rm degrm out/e.