Kesten-Stigum detectability threshold for the symmetric SBM

a and b are the rescaled within- and between-group degrees c_in and c_out, so the mean degree is c = (a + (k - 1) b) / k.

Usage

Sgtsbnd(a, b, k = 2)

Arguments

a

Rescaled within-group degree, non-negative.

b

Rescaled between-group degree, non-negative.

k

Number of equally sized groups, at least 2.

Value

List with detectable, estimate, margin, c, threshold, k.

Details

Formula: detectable iff |a - b| > k sqrt(c), equivalently (a - b)^2 > k (a + (k - 1) b). The placeholder this replaces carried an extra 1/(k-1), which is correct only at k = 2; equation (44) on page 14 of arXiv:1109.3041 was read from a rendered page image.

References

Decelle, A., Krzakala, F., Moore, C. & Zdeborova, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E 84, 066106. doi:10.1103/PhysRevE.84.066106 ; equation (44).

Examples

Sgtsbnd(a = 5, b = 1)$detectable    # (a - b)^2 = 16 > k (a + b) = 12
#> [1] 1
Sgtsbnd(a = 3, b = 2)$detectable
#> [1] 0