# Community Recovery in Graphs with Locality

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2016.

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

- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms](https://mlsanity.com/paper/2401.08197/) (2024)

## Abstract (arXiv)

Motivated by applications in domains such as social networks and computational biology, we study the problem of community recovery in graphs with locality. In this problem, pairwise noisy measurements of whether two nodes are in the same community or different communities come mainly or exclusively from nearby nodes rather than uniformly sampled between all nodes pairs, as in most existing models. We present an algorithm that runs nearly linearly in the number of measurements and which achieves the information theoretic limit for exact recovery.