Stochastic Block Model — Planted Partition

Random graph with community structure: within-block edges p, between-block edges q. The Kesten-Stigum threshold marks the detectability boundary.

Decelle et al. (2011) showed via the cavity method that community detection is impossible below the Kesten-Stigum threshold (p-q)^2 = 2(p+q)K/n even with optimal algorithms. Above threshold, spectral methods and belief propagation succeed.