Stochastic Block Model

Stochastic Block Model (SBM): n nodes in k communities; edges drawn with probability p_in within communities and p_out between. The planted partition is recoverable when (p_in − p_out)² > 2(p_in + p_out)/n — the Kesten-Stigum threshold for sparse graphs.
Left: adjacency matrix reordered by community (block structure visible when p_in ≫ p_out). Right: graph layout with spectral embedding (2 leading eigenvectors of Laplacian). Color = spectral cluster assignment via k-means on eigenvectors. The detectability transition at (√p_in − √p_out)² = k·p_out is a phase transition: below it, no algorithm can do better than random guessing.