Stochastic Block Model — Planted Partition & Phase Transition

SBM: n nodes in k groups. Edges within groups with prob p_in, between groups with p_out. Detectability threshold (Decelle et al 2011): detection is possible iff (p_in − p_out)² > k²(p_in + p_out)/n. Below this, no algorithm can recover communities better than chance.

n nodes: 80 k groups: 3 p_in: 0.30 p_out: 0.05

Detectability: — | SNR = (p_in − p_out)²·n / [k²(p_in+p_out)] | Threshold SNR = 1