Stochastic Block Model — Community Detection

Detectability phase transition via belief propagation

The Stochastic Block Model (SBM) places N nodes in K communities; edges form with probability p_in within communities and p_out between them. The Kesten-Stigum threshold (Decelle et al 2011) predicts a phase transition: community detection is information-theoretically impossible when (p_in−p_out)² < 2K(p_in+(K−1)p_out)/n. Belief propagation on the sparse graph achieves this threshold.