SBM Detectability — Mossel-Neeman-Sly

Stochastic Block Model: two communities, intra-edge prob p_in, inter-edge prob p_out. The Kesten-Stigum threshold separates detectable from undetectable phases.

Parameters

n (nodes): 80 avg degree k: 8 SNR (a-b)²/2k: 1.00

KS threshold: SNR=1
SNR>1 → detectable
SNR<1 → impossible
Current: AT threshold

Mossel-Neeman-Sly (2015/2016): for k=2 equal-size communities, detection is possible iff (a−b)²>2(a+b) where p_in=a/n, p_out=b/n. Spectral methods (non-backtracking operator) achieve this threshold.