Stochastic Block Model — Community Detection

Graph generation and belief propagation detectability threshold

40
2
0.50
0.10
Modularity: —
Detectable: —
Mean degree: —
The Stochastic Block Model (SBM) generates random graphs with planted community structure. Nodes in the same community connect with probability p_in; across communities with p_out. The Kesten-Stigum threshold: communities are detectable by belief propagation iff (p_in−p_out)²n > q²·p_avg. Below this threshold, no algorithm can recover better than random. Node colors show true community; size shows inferred confidence.