Stochastic Block Model
Community detection & modularity in random graphs
Graph Parameters
Communities k:
3
Nodes per community:
12
In-community prob p_in:
0.55
Cross-community prob p_out:
0.05
Layout:
Block
Regenerate Graph
SBM:
Nodes partitioned into k communities. Edges placed with prob p_in within, p_out across blocks.
Modularity Q:
Q = (1/2m) Σ[A_ij - k_i·k_j/2m]·δ(c_i,c_j)
Q near 1 → strong community structure
Q near 0 → Erdos-Rényi random
Detectability threshold:
(p_in - p_out)² > k(p_in + p_out)/N