the configuration model

The configuration model is the standard way to build a random graph with a prescribed degree sequence. Erdos-Renyi forces a Poisson degree distribution, which real networks violate; the configuration model fixes this by letting you specify exactly how many neighbours each vertex has and then connecting them as randomly as possible. The question it answers is: among all graphs with a given list of degrees, what does a uniformly random one look like, and how can we generate and analyze it?

The construction is the stub-matching (pairing) recipe. Give vertex i a number d_i of half-edges or 'stubs' sticking out; the total number of stubs must be even, say 2m. Then choose a uniformly random perfect matching of all 2m stubs into m pairs, and for each matched pair draw an edge between the corresponding vertices. The result is a multigraph (self-loops and multiple edges can occur). Two facts make this useful. First, conditioned on producing a simple graph (no loops or multi-edges), the configuration model is uniformly distributed over all simple graphs with that exact degree sequence — so it is a genuine sampler of the uniform degree-constrained graph. Second, the probability of being simple stays bounded away from 0 as n grows precisely when the degrees have bounded second moment (sum of d_i^2 of order n); for heavier-tailed degrees self-loops and multi-edges proliferate and one works with the multigraph or with an erased/repaired version. The local structure of the configuration model converges to a branching process whose offspring follow the SIZE-BIASED degree distribution shifted by one: the neighbour of a random vertex has degree k with probability proportional to k times (fraction with degree k) — the classic friendship paradox, 'your friends have more friends than you do'.

The configuration model is the reference model for sparse networks with realistic degree distributions, and the cleanest setting for the modern theory of the giant component, distances and epidemics on networks. The Molloy-Reed criterion states the phase transition: a giant component exists iff the expected size-biased excess degree exceeds 1, i.e. iff sum d_i(d_i - 2) > 0, equivalently E[D(D-1)]/E[D] > 1 where D is the degree of a random vertex — a precise generalization of the Erdos-Renyi 'mean degree greater than 1'. The honest caveats: the model produces multigraphs unless conditioned to be simple, and that conditioning is only well-behaved under a second-moment condition on the degrees; and the analysis assumes the degree sequence is essentially fixed (or converges nicely), so it is a model of a degree sequence, not a generative growth model like preferential attachment — it does not explain WHY networks have heavy tails, only lets you impose one.