### 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.

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.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.