Generate SBM random graphs and infer community structure. Visualize the Kesten-McKay detectability threshold: communities become undetectable when the signal-to-noise ratio crosses a critical value.
SBM(n,k,p_in,p_out): nodes partitioned into k groups; edges drawn with probability p_in within groups, p_out across. Kesten-McKay detectability threshold (Decelle-Krzakala 2011): communities detectable iff (p_in-p_out)²·n/k > k·p_out. Below threshold: no algorithm can recover structure. Connected to spectral gap of non-backtracking operator. Belief propagation is Bayes-optimal at threshold.