Stochastic Block Model

Spectral community detection · detectability threshold · Bethe Hessian

—

Adjacency matrix (sorted by community)

Graph (colored by detected community)

Spectral embedding (2nd & 3rd eigenvectors)

Nodes N: 60

Communities K: 3

p_in: 0.30

p_out: 0.05

SBM: nodes in K groups; edge prob p_in within, p_out between.
Detectability threshold: (p_in−p_out)²·n/(K·c) > 1 where c=avg degree.
Spectral method: eigenvectors of Laplacian/Bethe Hessian cluster communities above threshold.