Graph colored by true (outer ring) vs detected (inner) community
Phase diagram: detectability vs (c_in, c_out) — KS threshold boundary
SBM Parameters
Detectability
KS threshold (c_in-c_out)²—
k·c̄ (avg degree)—
Detectable?—
Overlap (detected)—
SNR (c_in-c_out)²/kc̄—
—
(c_in − c_out)² > k · c̄
The Kesten-Stigum threshold marks when community structure becomes statistically detectable.
Below: no algorithm can do better than chance. Above: spectral methods and belief propagation recover communities. The transition is sharp for sparse graphs (n→∞).
Below: no algorithm can do better than chance. Above: spectral methods and belief propagation recover communities. The transition is sharp for sparse graphs (n→∞).