Community structure detectability near the Kesten–Stigum threshold
The planted partition SBM places n nodes into k equal blocks; edges form with probability p_in within blocks and p_out across them. The Kesten–Stigum threshold (for sparse graphs) is (p_in − p_out)² > p_out·k/n; below it, no polynomial algorithm can recover communities. Color shows ground-truth block; node position shows force-directed layout.