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 currently
motivated by 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 planted “ground truth” community structure around
which the graph is generated probabilistically. Our task is then to
recover the ground truth knowing only the graph.
Recently it was discovered, first h euristically i n p hysics a nd 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 t hat i s 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 be exponentially hard.
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.