—
Stochastic Block Model (SBM): The SBM generates random graphs where nodes belong to K
communities. Nodes in the same community connect with probability p_in; nodes in different
communities connect with probability p_out. The key question is: when can we detect communities?
The Kesten-Stigum threshold (for 2 communities, equal size n): detection is possible
iff (p_in − p_out)² > 2(p_in + p_out)/n · K². Below this threshold, no algorithm can
distinguish the planted partition from a random graph (information-theoretic limit).
The adjacency matrix (left) shows the block structure; warm colors = edges within communities,
cool colors = edges between. The spectral gap of the Laplacian determines detectability.