Definitions and Heuristics

In an Erdös–Rényi random graph, vertices have degrees that have asymptotically a Poisson distribution. However, as discussed in Section 1.4, in social and communication networks, the distribution of degrees is much different from the Poisson and in many cases has a power law form, that is, the fraction of vertices of degree k, pk ~ Ck-β as k → ∞. Molloy and Reed (1995) were the first to construct graphs with specified degree distributions. We will use the approach of Newman, Strogatz, and Watts (2001, 2002) to define the model.

Let d1,…dn be independent and have P(di = k) = pk. Since we want di to be the degree of vertex i, we condition on En = {d1 + … + dn is even}. If the probability P(E1) ∊ (0, 1) then P(En) → ½ as n → ∞ so the conditioning will have little effect on the finite-dimensional distributions. If d1 is always even then P(En) = 1 for all n, while if d1 is always odd, P(E2n) = 1 and P(E2n+1) = 0 for all n.

To build the graph we think of di half-edges attached to i and then pair the half-edges at random. The picture gives an example with eight vertices.