# The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2017.

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

- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?](https://mlsanity.com/paper/2205.10009/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise](https://mlsanity.com/paper/2405.20993/) (2024)
- [Is it easier to count communities than find them?](https://mlsanity.com/paper/2212.10872/) (2022)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [Approximate sampling and estimation of partition functions using neural networks](https://mlsanity.com/paper/2209.10423/) (2022)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)
- [Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier](https://mlsanity.com/paper/2107.14323/) (2021)
- [Generative models for two-ground-truth partitions in networks](https://mlsanity.com/paper/2302.02787/) (2023)
- [Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise](https://mlsanity.com/paper/2302.03306/) (2023)
- [Model inference for ranking from pairwise comparisons](https://mlsanity.com/paper/2512.15269/) (2025)
- [Graph energy as a measure of community detectability in networks](https://mlsanity.com/paper/2601.05065/) (2026)

## Abstract (arXiv)

Community detection in graphs is the problem of finding groups of vertices which are more densely connected than they are to the rest of the graph. This problem has a long history, but it is undergoing a resurgence of interest due to the need to analyze social and biological networks. While there are many ways to formalize it, one of the most popular is as an inference problem, where there is a "ground truth" community structure built into the graph somehow. The task is then to recover the ground truth knowing only the graph. Recently it was discovered, first heuristically in physics and then rigorously in probability and computer science, that this problem has a phase transition at which it suddenly becomes impossible. Namely, if the graph is too sparse, or the probabilistic process that generates it is too noisy, then no algorithm can find a partition that is correlated with the planted one---or even tell if there are communities, i.e., distinguish the graph from a purely random one with high probability. Above this information-theoretic threshold, there is a second threshold beyond which polynomial-time algorithms are known to succeed; in between, there is a regime in which community detection is possible, but conjectured to require exponential time. For computer scientists, this field offers a wealth of new ideas and open questions, with connections to probability and combinatorics, message-passing algorithms, and random matrix theory. Perhaps more importantly, it provides a window into the cultures of statistical physics and statistical inference, and how those cultures think about distributions of instances, landscapes of solutions, and hardness.