Stochastic Block Model

SBM Parameters

Nodes N 60 Communities K 3 Within-group p_in 0.30 Between-group p_out 0.05

P(A_ij=1) = p_in [same block] / p_out [diff]

KS threshold: (p_in−p_out)² > K·(p_in+(K-1)p_out)/N

KS threshold: —

Spectral gap: —

Detection accuracy: —

The SBM (Holland-Laskey-Leinhardt 1983) is the canonical model for community structure. Detection is possible when the signal exceeds the Kesten-Stigum threshold (information-theoretic limit). Spectral methods use eigenvectors of the modularity matrix. Below threshold: community recovery is information-theoretically impossible even in principle.

SBM Parameters

Adjacency Matrix (true block order)

Spectral Embedding (2nd & 3rd eigenvectors)