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

0

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

Cristopher Moore

posted on 08 February 2017

pdf (110 views, 75 download, 0 comments)

## Recent comments