Stochastic Block Model: Community Detection

Stochastic Block Model: N nodes divided into k groups. Edges added with probability p_in within groups and p_out between groups.

The Kesten-McKay detectability threshold (Decelle et al. 2011): communities are algorithmically detectable only when (p_in−p_out)²N/k > (p_in+p_out(k−1)). At the threshold, the second eigenvalue of the adjacency matrix enters the bulk (semicircle).

Spectral clustering: use eigenvectors 2..k of the Laplacian to embed nodes, then k-means. Colors show planted (true) vs detected communities.