Title: 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.