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

Abstract

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.

This review article first appeared in the Bulletin of the EATCS; I plan to update it sporadically, and this is the first such update. It is aimed primarily at computer scientists, but hopefully others will enjoy it as well

References in corpus (1)

• Phase transitions in semisupervised clustering of sparse networks

Cited by in corpus (22)

• Selective Exposure shapes the Facebook News Diet
• Bayesian stochastic blockmodeling
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Charting the replica symmetric phase
• Universality of the stochastic block model
• Mean-field theory of graph neural networks in graph partitioning
• Hierarchical community structure in networks
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Random Spatial Network Models with Core-Periphery Structure
• Subexponential-Time Algorithms for Sparse PCA
• PCA Initialization for Approximate Message Passing in Rotationally Invariant Models
• The Overlap Gap Property in Principal Submatrix Recovery
• Convex Relaxation Methods for Community Detection
• Detectability of hierarchical communities in networks
• Community Detection in the Hyperbolic Space
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families
• Pair-Matching: Links Prediction with Adaptive Queries
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• New Abilities and Limitations of Spectral Graph Bisection
• Optimizing collective fieldtaxis of swarming agents through reinforcement learning