Skip to main content

Erdős-Rényi Random Graphs

Module 5: Complex Networks

NoteReading
  • Compulsory for the session: Watts and Strogatz (1998); Barabasi and Albert (1999) (see the Reading boxes of the next two pages).
  • For this page: Newman (2003), Section 4.1 (Poisson random graphs).
  • Recommended: Newman (2018); Newman (2003), Sections 6 and 7.

Real networks have short paths, high clustering and, often, hubs (Newman 2003). This page builds three models that reproduce some of these features. The first one is the simplest random graph: it serves as the null model against which you compare the others.

The model

In the Gilbert model \(G(N, p)\) every pair of nodes is joined independently with probability \(p\) (Gilbert 1959). The closely related Erdős-Rényi model \(G(N, E)\) picks a graph uniformly among all graphs with exactly \(E\) edges (Erdos and Renyi 1959). For large \(N\) the two behave the same, and both go by the name “random graph”.

Let \(c = (N-1)p\) be the mean degree. Key properties, for large \(N\) with \(c\) fixed (Newman 2003, sec. 4.1; Newman 2018):

  • The degree distribution is binomial and tends to a Poisson distribution, \(p_k = e^{-c} c^k / k!\). So \(\langle k^2 \rangle = c^2 + c\).
  • The clustering coefficient is \(C = p = c/(N-1)\), which tends to zero as \(N\) grows.
  • A giant component exists if and only if \(c > 1\). This agrees with the Molloy-Reed criterion of Robustness and Percolation: \(\kappa = \langle k^2 \rangle / \langle k \rangle = c + 1 > 2\).
  • The fraction \(S\) of nodes in the giant component solves \(S = 1 - e^{-cS}\).
  • The typical distance grows like \(\ell \approx \ln N / \ln c\).

The same results can be written with \(\langle k \rangle = p(N-1)\) in place of \(c\), calling the average path length \(L\) and using \(p(k)\) for the degree distribution:

\[ p(k) = \binom{N-1}{k} p^k (1-p)^{N-1-k} \approx e^{-\langle k \rangle}\frac{\langle k \rangle^k}{k!}, \qquad L \sim \frac{\log N}{\log \langle k \rangle}, \qquad C = p \approx \frac{\langle k \rangle}{N}. \]

Two remarks complete this summary. First, for large mean degree the Poisson distribution is approximately Gaussian with mean and variance \(\langle k \rangle\) (Stirling’s formula for \(k!\)), so the degree distribution of a random graph is narrow, without hubs. A direct comparison gives a largest pointwise difference between the Poisson and the Gaussian densities of 0.021 at \(\langle k \rangle = 5\) (the peak of the Poisson is 0.176) and 0.0019 at \(\langle k \rangle = 50\) (peak 0.056). Second, the formula for \(L\) is an estimate that holds for \(\langle k \rangle > 1\), where a giant component exists; Scaling of Path Length and Clustering tests it numerically. In the summary table, the random graph gets a tick for short paths, and crosses for clustering and for hubs.

Implementation

NetworkX provides nx.erdos_renyi_graph(n, p) for \(G(N,p)\) and nx.gnm_random_graph(n, m) for \(G(N,E)\). The algorithm behind \(G(N,p)\) is short:

  1. Select a pair of nodes \(i\) and \(j\).
  2. Draw a random number \(r\) in \([0, 1)\). If \(r < p\), add the edge \((i, j)\).
  3. Repeat for all pairs.
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

SEED = 7

G_random = nx.erdos_renyi_graph(n=80, p=0.06, seed=SEED)
pos = nx.spring_layout(G_random, seed=SEED)
nx.draw(G_random, pos=pos, node_size=60, node_color="lightgray", edge_color="gray")
plt.title("Erdős-Rényi random graph, N = 80, p = 0.06")
plt.show()

k = np.array([d for _, d in G_random.degree()])
print(f"<k> = {k.mean():.2f} (expected {(80 - 1) * 0.06:.2f})")
print(f"C = {nx.average_clustering(G_random):.3f} (expected p = 0.06)")
print(f"components = {nx.number_connected_components(G_random)}")

<k> = 5.28 (expected 4.74)
C = 0.078 (expected p = 0.06)
components = 1

With \(N = 80\) a single realization fluctuates around the expected values. Increase \(N\) and watch the measured values approach the predictions.

In \(G(N, E)\) you fix the number of edges instead of an edge probability. In NetworkX:

  • nx.gnm_random_graph(n, m) implements \(G(N, E)\) with \(E = m\);
  • nx.erdos_renyi_graph(n, p) (alias nx.gnp_random_graph) implements \(G(N, p)\).

With \(N = 80\) and \(E = 180\) the mean degree is \(2E/N = 4.5\), close to the \(4.74\) of \(G(80, 0.06)\). The degree histogram has the same binomial shape.

G_gnm = nx.gnm_random_graph(n=80, m=180, seed=SEED)
k_gnm = [d for _, d in G_gnm.degree()]
print(f"E = {G_gnm.number_of_edges()}, <k> = {2 * 180 / 80:.2f}")

plt.figure(figsize=(5, 3))
plt.hist(k_gnm, bins=range(min(k_gnm), max(k_gnm) + 2), align="left", rwidth=0.9)
plt.xlabel("Degree k")
plt.ylabel("Count")
plt.title("G(N, E): degree distribution")
plt.tight_layout()
plt.show()
E = 180, <k> = 4.50

The giant component

Figure 1 compares simulated graphs with the self-consistency equation \(S = 1 - e^{-cS}\).

Figure 1: Fraction of nodes in the largest component of G(N, p) with N = 2000 (dots, one graph per value) and the theoretical giant component S = 1 - exp(-cS) (line).

Near \(c = 1\) the finite graph has a largest component of size \(o(N)\) that is still visible, so the dots do not drop exactly to zero.

NoteExercise

Watts and Strogatz measured \(C = 0.79\) in the collaboration network of film actors, against \(C = 0.00027\) for a random graph of the same size and mean degree (Watts and Strogatz 1998, Table 1). Estimate \(C\) for a random graph with \(N = 10^6\) people and mean degree \(c = 100\). What does this say about random graphs as models of social networks?

\(C = c/(N-1) \approx 10^{-4}\). A random graph has almost no triangles, so it cannot reproduce the clustering of social networks. It does reproduce short paths: \(\ell \approx \ln 10^6 / \ln 100 = 3\). The small-world model keeps both.

References

Barabasi, Albert-Laszlo, and Reka Albert. 1999. “Emergence of Scaling in Random Networks.” Science 286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509.
Erdos, Paul, and Alfred Renyi. 1959. “On Random Graphs i.” Publicationes Mathematicae 6: 290–97.
Gilbert, Edgar N. 1959. “Random Graphs.” The Annals of Mathematical Statistics 30 (4): 1141–44. https://doi.org/10.1214/aoms/1177706098.
Newman, M. E. J. 2003. “The Structure and Function of Complex Networks.” SIAM Review 45 (2): 167–256. https://doi.org/10.1137/S003614450342480.
Newman, Mark. 2018. Networks. 2nd ed. Oxford University Press.
Watts, Duncan J., and Steven H. Strogatz. 1998. “Collective Dynamics of ’Small-World’ Networks.” Nature 393 (6684): 440–42. https://doi.org/10.1038/30918.