Detectability λ—
KS threshold—
Modularity Q—
Detectable?—
SBM probability:
P(A|z) = ∏ p_in^{A_ij}(1-p_in)^{1-A_ij} [i,j same block]
KS detectability:
λ = (p_in - p_out)/(p_in/K + p_out(K-1)/K)
threshold: λ² > K²/(K-1)
Modularity Q:
Q = (1/2m)Σ[A_ij - k_i k_j/2m]δ(z_i,z_j)
P(A|z) = ∏ p_in^{A_ij}(1-p_in)^{1-A_ij} [i,j same block]
KS detectability:
λ = (p_in - p_out)/(p_in/K + p_out(K-1)/K)
threshold: λ² > K²/(K-1)
Modularity Q:
Q = (1/2m)Σ[A_ij - k_i k_j/2m]δ(z_i,z_j)
The SBM is the canonical model for networks with community structure. The Kesten-Stigum threshold separates detectable from undetectable regimes — below it, no algorithm can recover communities better than chance.