Stochastic Block Model — Community Detection
Generate SBM random graphs and detect communities via spectral clustering. Observe the detectability phase transition.
SBM Phase Transition: The Kesten-Stigum threshold determines detectability: (p−q)² > k·(p+(k−1)q)/(n/k). Below this threshold, no algorithm can detect communities better than chance (Decelle et al 2011). Spectral clustering uses the top-k eigenvectors of the modularity or Bethe-Hessian matrix. Color shows true communities (rings = detected communities when detection is run).