the Chung-Lu and stochastic block models
/ chung loo; SBM /
These are inhomogeneous random graphs: generalizations of G(n,p) where the edge probability is allowed to depend on which vertices are involved. The Chung-Lu model targets a prescribed expected degree for each vertex (a soft, independent-edge alternative to the configuration model); the stochastic block model (SBM) divides vertices into communities and makes the edge probability depend on the communities of the two endpoints. Together they are the canonical models for two of the most important features of real networks that Erdos-Renyi lacks: heterogeneous degrees and community structure. The question they answer is: how do we build a tractable random graph that has hubs, or has clusters, while keeping edges independent?
In the Chung-Lu model each vertex i is assigned a weight w_i, and edge (i,j) is present independently with probability proportional to w_i w_j (specifically about w_i w_j / (sum_k w_k), capped at 1). Then the expected degree of i is essentially w_i, so prescribing the weights prescribes the expected degree sequence — and choosing power-law weights yields a power-law graph with independent edges, which is far easier to analyze than the configuration model. In the stochastic block model with q communities, every vertex is labelled by a community, and two vertices in communities a and b are joined independently with probability B_{ab} (a q-by-q matrix of probabilities). The 'assortative' case B_{aa} > B_{ab} models communities that are denser inside than between. Both are special cases of the general inhomogeneous random graph of Bollobas-Janson-Riordan, in which edge (i,j) appears with probability kappa(x_i, x_j)/n for a kernel kappa on a space of vertex types; the giant component and other features are then read off from an integral operator built from kappa (a giant exists iff that operator has norm exceeding 1, the operator-theoretic generalization of 'mean degree greater than 1').
These models are the foundation of modern community detection and network statistics. The SBM in particular is the testbed for a sharp algorithmic phase transition: in the two-community sparse SBM with within-probability a/n and between-probability b/n, the communities can be recovered better than chance (weak recovery) if and only if (a - b)^2 > 2(a + b) — the Kesten-Stigum / Decelle-Krzakala-Moore-Zdeborova threshold, below which the partition is information-theoretically invisible. The honest caveat: Chung-Lu and the SBM keep edges independent given the types, which makes them analytically friendly but means they share Erdos-Renyi's locally tree-like, low-clustering nature — they generate hubs and blocks but few triangles, so they still do not reproduce the high clustering of social networks. And the SBM's recovery thresholds are theorems about THIS generative model; real community detection must cope with model misspecification, which the clean threshold theory does not address.
In the symmetric 2-community SBM with n vertices, within-edge probability a/n and between-edge probability b/n, weak recovery of the planted partition is possible iff (a-b)^2 > 2(a+b). For example a = 6, b = 1 gives (a-b)^2 = 25 and 2(a+b) = 14, so 25 > 14 — communities are recoverable. Lower the contrast to a = 4, b = 3: (a-b)^2 = 1 < 2(a+b) = 14, and no algorithm can beat random guessing.
The Kesten-Stigum threshold (a-b)^2 = 2(a+b): below it the planted communities are statistically undetectable.
Like G(n,p), these keep edges independent given vertex types, so they are locally tree-like with almost no triangles — they capture hubs and communities but NOT the high clustering of real social networks. The detection thresholds are theorems about the model, not about misspecified real data.