Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Erdős–Rényi Random Graphs

So far a graph was a single object: an adjacency matrix, a degree sequence, a set of edges. The Erdős–Rényi model replaces that object by a probability distribution over graphs. We can then ask questions such as “how many edges does a typical graph have?” or “when does a giant connected component appear?”, and answer them exactly — and check the answers by simulation.

Reading. Blum, Hopcroft & Kannan, Foundations of Data Science, Ch. 4; van Steen, Graph Theory and Complex Networks, Ch. 3.

Why model graphs randomly?

  • Null model. What does a network look like when there is no structure at all? Anything that the random model does not produce (heavy-tailed degrees, many triangles, small diameter) is what we mean by “structure” in real data.

  • Generative model. Statements such as “most graphs are connected” hold with high probability (whp) — for a single graph they are simply true or false.

  • Testbed. Community detection, spectral clustering or PageRank are first tested on random graphs, where the correct answer is known by construction.

The two models

Definition (Erdős–Rényi, G(n,p)G(n,p)). Fix nn vertices. For each of the (n2)\binom{n}{2} unordered pairs, insert the edge independently with probability pp.

Definition (G(n,m)G(n,m)). All graphs with nn vertices and exactly mm edges are equally likely.

The two are closely related: G(n,m)G(n,m) is G(n,p)G(n,p) conditioned on having exactly mm edges (with p=m/(n2)p = m / \binom{n}{2}), and for large nn the conditioning changes almost nothing.

n = 200  p = 0.05  number of possible pairs = 19900
G(n,p) edges: 1025    G(n,m) edges: 996

Number of edges

Let N=(n2)N = \binom{n}{2}. The number of edges MM is a sum of NN independent Bernoulli(p)(p) variables, hence

M∼Bin ⁣(N,p),E[M]=Np,Var(M)=Np(1−p).M \sim \mathrm{Bin}\!\left(N, p\right), \qquad \mathbb{E}[M] = Np, \qquad \mathrm{Var}(M) = Np(1-p).

The mean degree follows immediately: dˉ=2 E[M]/n=(n−1)p\bar d = 2\,\mathbb{E}[M]/n = (n-1)p.

theory : mean = 6237.5   std = 76.98
empirical: mean = 6239.1   std = 77.34

The degree distribution

The degree of one fixed vertex is the number of successes among the n−1n-1 pairs that contain it:

D∼Bin(n−1,p),E[D]=(n−1)p,Var(D)=(n−1)p(1−p).D \sim \mathrm{Bin}(n-1, p), \qquad \mathbb{E}[D] = (n-1)p, \qquad \mathrm{Var}(D) = (n-1)p(1-p).

Poisson limit

The interesting regime is a constant average degree cc: take p=c/(n−1)p = c/(n-1) and let n→∞n\to\infty. Then E[D]=c\mathbb{E}[D] = c and

Pr⁡(D=k)=(n−1k)pk(1−p)n−1−k  →n→∞  e−c ckk!.\Pr(D = k) = \binom{n-1}{k} p^k (1-p)^{n-1-k} \;\xrightarrow[n\to\infty]{}\; e^{-c}\,\frac{c^k}{k!}.

(The first factor behaves like (n−1)k/k!(n-1)^k/k!, the last one like e−ce^{-c}.) So a large sparse Erdős–Rényi graph has Poisson degrees: most vertices have degree close to cc, and the maximum degree is only O(log⁡n/log⁡log⁡n)O(\log n / \log\log n). Real networks look very different — see the last section.

<Figure size 600x400 with 1 Axes>
mean degree: empirical = 2.961  theory c = 3

Triangles and clustering

For a fixed triple of vertices to form a triangle, its three edges must be present:

E[#triangles]=(n3)p3.\mathbb{E}\big[\#\text{triangles}\big] = \binom{n}{3} p^3 .

The local clustering coefficient of a vertex vv is the fraction of pairs of its neighbours that are themselves connected. In G(n,p)G(n,p) those edges are independent of the neighbourhood, so on average

E[Cv]≈p,\mathbb{E}[C_v] \approx p ,

which is tiny for the sparse graphs we care about (p=c/np = c/n). This is the main defect of the model: real social networks have clustering coefficients of order 10-1 while pp is of order 10-3.

p =  0.01 | avg clustering = 0.0118 (p = 0.0100) | triangles: measured     11, theory      10.6
p =  0.02 | avg clustering = 0.0202 (p = 0.0200) | triangles: measured     82, theory      84.7
p =  0.05 | avg clustering = 0.0532 (p = 0.0500) | triangles: measured   1359, theory    1323.4
p =  0.10 | avg clustering = 0.1007 (p = 0.1000) | triangles: measured  10785, theory   10586.8
p =  0.20 | avg clustering = 0.2005 (p = 0.2000) | triangles: measured  84181, theory   84694.4
<Figure size 600x400 with 1 Axes>

Thresholds: the graph changes qualitatively as pp grows

Most statements about G(n,p)G(n,p) are threshold statements: there is a value p∗(n)p^*(n) such that below it a property holds whp, and above it fails whp (or vice versa).

PropertyThresholdTypical picture
at least one edgep≍n−2p \asymp n^{-2}isolated edges
a fixed subgraph with kk vertices, ℓ\ell edgesp≍n−k/ℓp \asymp n^{-k/\ell}e.g. triangles at p≍n−1p\asymp n^{-1}
a tree on kk verticesp≍n−k/(k−1)p \asymp n^{-k/(k-1)}e.g. paths of length 2 at p≍n−2/3p\asymp n^{-2/3}
giant componentp≍1/np \asymp 1/nmean degree c=1c=1
connectivityp≍log⁡n/np \asymp \log n / nevery vertex has a neighbour

The last two are the ones we care about. Both are read off the number of isolated vertices: for p=clog⁡n/np = c\log n / n,

E[#isolated]=n(1−p)n−1≈n e−clog⁡n=n1−c,\mathbb{E}\big[\#\text{isolated}\big] = n(1-p)^{n-1} \approx n\,e^{-c\log n} = n^{1-c},

which tends to 0 when c>1c>1 and to ∞\infty when c<1c<1 — hence the threshold log⁡n/n\log n / n.

    c          p  isolated (measured)    n^(1-c)
 0.60   0.007458                   18      12.01
 0.80   0.009943                    1       3.47
 1.00   0.012429                    3       1.00
 1.20   0.014915                    0       0.29
 1.50   0.018644                    0       0.04

The giant component (a preview)

Take p=c/np = c/n and let SS be the fraction of vertices in the largest component. A branching-process argument (each neighbour has on average cc further neighbours) gives the self-consistency equation

S=1−e−cS,S = 1 - e^{-cS},

whose non-zero solution exists exactly when c>1c > 1. This is the phase transition: for c<1c<1 all components are of size O(log⁡n)O(\log n), for c>1c>1 a positive fraction of the vertices sits in one component. The next page derives this in detail; here we only check it experimentally.

<Figure size 600x400 with 1 Axes>

Lab: what a random graph looks like

Keeping nn fixed and varying the mean degree c=(n−1)pc=(n-1)p shows the three regimes: a dust of tiny components, a critical graph, and a graph dominated by one giant component.

<Figure size 1200x700 with 6 Axes>

What the model does not do

A single parameter cannot describe a real network. Three systematic mismatches motivate the models that come next in this course:

  1. Degrees. G(n,p)G(n,p) has Poisson degrees; web graphs, citations and social networks have heavy-tailed (power-law) degrees — a few hubs carry a large fraction of the edges.

  2. Clustering. Triangles are rare (E[Cv]≈p\mathbb{E}[C_v]\approx p); in real social networks your friends are friends much more often than chance would predict. The configuration model (random graph with a prescribed degree sequence) and the Watts–Strogatz small-world model are the two standard repairs.

  3. Geometry. Distance in G(n,p)G(n,p) is Θ(log⁡n/log⁡c)\Theta(\log n / \log c) — very small, but the graph has no notion of “close” nodes, which real data (images, cities, the web) usually have.

Still, the Erdős–Rényi graph is the reference point against which all of these are measured.

Exercises

  1. Derive E[M]\mathbb{E}[M] and Var(M)\mathrm{Var}(M) for G(n,p)G(n,p), and use Chebyshev’s inequality to show that M/(n2)→pM/\binom{n}{2} \to p in probability.

  2. Show that for p=c/np=c/n the number of isolated vertices converges in distribution to Poisson(e−c)\mathrm{Poisson}(e^{-c}) scaled by nn, and deduce the connectivity threshold c=log⁡nc=\log n.

  3. For fixed kk, compute the expected number of kk-cliques and conclude that kk-cliques appear around p≍n−2/(k−1)p\asymp n^{-2/(k-1)}.

  4. Generate G(n,m)G(n,m) and compare its degree distribution with G(n,p)G(n,p) at p=2m/(n(n−1))p = 2m/(n(n-1)); explain the small difference you observe.

  5. For n=500,1000,2000n=500,1000,2000, find empirically the smallest pp at which the graph is connected, and compare with log⁡n/n\log n / n. Reproduce the table of thresholds above.

  6. Optional. Repeat the giant-component experiment for the configuration model with a power-law degree sequence and describe how the transition changes.

References

  • P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960), 17–61.

  • A. Blum, J. Hopcroft and R. Kannan, Foundations of Data Science, Cambridge University Press, Ch. 4 (Random Graphs).

  • M. van Steen, Graph Theory and Complex Networks: An Introduction, Ch. 3.

  • NetworkX documentation: gnp_random_graph, gnm_random_graph, connected_components.