Skip to main content

Preferential Attachment

Module 5: Complex Networks

NoteReading
  • Compulsory: Barabasi and Albert (1999).
  • Recommended: Newman (2003), Section 7.2.
  • What the paper did and found: Barabási and Albert measured the degree distribution of three real networks and found power-law tails \(P(k) \sim k^{-\gamma}\): the film-actor collaboration graph with \(\gamma_{\text{actor}} = 2.3 \pm 0.1\), the World-Wide Web, and the western US power grid, whose distribution they fit with \(\gamma_{\text{power}} \simeq 4\) (the network has only 4941 vertices, so the scaling region is short). Their model combines growth with preferential attachment \(\Pi(k_i) = k_i / \sum_j k_j\), and simulations give \(\gamma_{\text{model}} = 2.9 \pm 0.1\). To show that both ingredients are needed, they studied two variants: model A (growth with uniform attachment) gives an exponential distribution, and model B (a fixed number of vertices and preferential attachment) shows power-law scaling only at early times, because it is not stationary and after \(T \simeq N^2\) steps all vertices are connected.

Neither the random graph nor the small-world model produces hubs. Many real networks have heavy-tailed degree distributions, sometimes close to a power law \(p_k \sim k^{-\gamma}\) (Barabasi and Albert 1999; Newman 2003, sec. 3.3). Barabási and Albert proposed that two ingredients generate such a distribution: growth and preferential attachment (Barabasi and Albert 1999).

The Barabási-Albert model

  1. Start with a small network of \(m_0 \ge m\) nodes.
  2. At each step add one new node with \(m\) edges.
  3. Each new edge goes to an existing node \(i\) with probability proportional to its degree, \[ \Pi(k_i) = \frac{k_i}{\sum_j k_j}. \]
  4. Repeat until the network has \(N\) nodes.

The mean degree tends to \(\langle k \rangle = 2m\).

Key results

  • In the limit of large \(N\), the degree distribution is \[ p_k = \frac{2m(m+1)}{k(k+1)(k+2)} \sim k^{-3}, \qquad k \ge m, \] so the exponent is \(\gamma = 3\) (Newman 2003, sec. 7.2; Newman 2018).
  • The degrees of the oldest nodes grow like \(\sqrt{t}\), so the largest degree grows like \(k_{\max} \sim m\sqrt{N}\) (Barabasi and Albert 1999; Newman 2018).
  • With \(\gamma = 3\) the second moment diverges logarithmically. Summing \(k^2 p_k\) up to \(k_{\max}\) gives \(\langle k^2 \rangle \approx m(m+1)\ln N\) for large \(N\). The degree variance \(\langle k^2 \rangle - \langle k \rangle^2\) therefore grows without bound as \(N\) grows, even though the mean stays at \(2m\).
  • The average path length is small, and the clustering is low and decreases with \(N\) (Newman 2003, sec. 7.2).

The divergence of \(\langle k^2 \rangle\) drives two results of this module: the robustness to random failure in Robustness and Percolation and the vanishing epidemic threshold in Epidemic Threshold. Keep in mind that the divergence is slow: at realistic sizes \(\langle k^2 \rangle\) is large but finite.

Why the exponent is 3: the continuum argument

The exponent follows with a continuum (mean-field) argument. Add one node per time step, each with \(m\) edges, so that the total degree at time \(t\) is \(\sum_j k_j = 2mt\). A node \(i\) born at time \(t_i\) receives each of the \(m\) new edges with probability \(\Pi_i = k_i/2mt\), hence

\[ \frac{dk_i}{dt} = m\,\frac{k_i}{2mt} = \frac{k_i}{2t} \quad\Longrightarrow\quad k_i(t) = m\left(\frac{t}{t_i}\right)^{1/2}. \tag{1}\]

Older nodes therefore have larger degree. A node has degree below \(k\) when \(t_i > m^2 t/k^2\), and the nodes are born uniformly in time, so the fraction of nodes with degree at least \(k\) is \(P(K \ge k) \approx m^2/k^2\) and \(p(k) \approx 2m^2/k^3 \sim k^{-3}\).

The argument is an approximation, and it is worth checking how good it is. The chunk compares the degree history of nodes born at different times with Equation 1 and the tail of the degree distribution with \(m^2/k^2\) and with the exact formula \(m(m+1)/\big(k(k+1)\big)\) obtained by summing the exact \(p_k\) above.

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

m, N_ba, runs = 3, 10_000, 10
windows = [(20, 40), (100, 200), (500, 1000), (2000, 4000)]
growth = {w: [] for w in windows}
ccdf = []
kmax_grid = np.unique(np.concatenate([np.logspace(np.log10(m), 2.3, 25).astype(int), [20, 40, 80]]))
for s in range(runs):
    G = nx.barabasi_albert_graph(N_ba, m, seed=s)
    for a, b in windows:
        k_final = G.degree(range(a, b))
        growth[(a, b)].append((np.mean([d for _, d in k_final]), np.mean([m * np.sqrt((N_ba - 1) / i) for i in range(a, b)])))
    deg = np.array([d for _, d in G.degree()])
    ccdf.append([(deg >= k).mean() for k in kmax_grid])

fig, axes = plt.subplots(1, 2, figsize=(9.5, 3.8))
meas = np.array([np.mean(growth[w], axis=0) for w in windows])
axes[0].loglog(meas[:, 1], meas[:, 0], "o", label="simulation")
lim = [meas.min() * 0.8, meas.max() * 1.2]
axes[0].loglog(lim, lim, "k--", lw=1, label="identity")
axes[0].set_xlabel(r"prediction $m\sqrt{t/t_i}$")
axes[0].set_ylabel("mean degree of the cohort")
axes[0].legend()
axes[1].loglog(kmax_grid, np.mean(ccdf, axis=0), "o", ms=4, label="simulation")
axes[1].loglog(kmax_grid, m**2 / kmax_grid**2, "--", label=r"$m^2/k^2$")
axes[1].loglog(kmax_grid, m * (m + 1) / (kmax_grid * (kmax_grid + 1)), "-", label=r"$m(m+1)/(k(k+1))$")
axes[1].set_xlabel("k")
axes[1].set_ylabel(r"$P(K \geq k)$")
axes[1].legend()
plt.tight_layout()
plt.show()

for w, (obs, pred) in zip(windows, meas):
    print(f"nodes born in {w}: mean degree {obs:.1f}, prediction {pred:.1f}")
for k in (20, 40, 80):
    i = list(kmax_grid).index(k)
    print(f"k = {k}: P(K >= k) = {np.mean(ccdf, axis=0)[i]:.5f}, m^2/k^2 = {m**2 / k**2:.5f}, exact = {m * (m + 1) / (k * (k + 1)):.5f}")
Figure 1: Test of the continuum argument for the Barabási-Albert model (m = 3, N = 10000, averages over 10 graphs). Left: mean degree at the final time of the nodes born in a window of times, against the prediction m sqrt(t / t_i) averaged over the same nodes. Right: complementary cumulative degree distribution, against the continuum approximation m^2 / k^2 and the exact discrete formula m(m+1) / (k(k+1)).
nodes born in (20, 40): mean degree 59.4, prediction 56.1
nodes born in (100, 200): mean degree 25.2, prediction 24.9
nodes born in (500, 1000): mean degree 11.2, prediction 11.1
nodes born in (2000, 4000): mean degree 5.6, prediction 5.6
k = 20: P(K >= k) = 0.02916, m^2/k^2 = 0.02250, exact = 0.02857
k = 40: P(K >= k) = 0.00745, m^2/k^2 = 0.00562, exact = 0.00732
k = 80: P(K >= k) = 0.00204, m^2/k^2 = 0.00141, exact = 0.00185

The growth law holds well: the mean degree of each cohort is within a few per cent of \(m\sqrt{t/t_i}\) (for the oldest cohort the prediction is 5% low), as the printed values show. The tail is a different matter. The continuum prefactor \(m^2\) underestimates the tail probability, by about 20 to 30% at \(m = 3\), while the exact formula with \(m(m+1)\) follows the simulation. The exponent is therefore right, and the amplitude of the continuum argument is only approximate: it replaces \(k(k+1)(k+2)\) by \(k^3\) and \(m(m+1)\) by \(m^2\).

Implementation

In NetworkX, nx.barabasi_albert_graph(n, m) adds nodes one at a time, each with m edges attached by preferential attachment.

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

SEED = 7

G_sf = nx.barabasi_albert_graph(n=200, m=2, seed=SEED)
pos = nx.spring_layout(G_sf, seed=SEED)
size = [5 * d for _, d in G_sf.degree()]
nx.draw(G_sf, pos=pos, node_size=size, node_color="lightgreen", edge_color="gray", alpha=0.8)
plt.title("Barabási-Albert graph, N = 200, m = 2")
plt.show()

Degree distribution and second moment

Figure 2 compares the empirical distribution with the exact formula. Use logarithmic bins or the complementary cumulative distribution for real data; here the formula lets you compare point by point.

Figure 2: Left: degree distribution of one Barabási-Albert graph (N = 20000, m = 2) against p_k = 2m(m+1)/(k(k+1)(k+2)). Right: second moment of the degree against N, with the approximation m(m+1) ln N (dashed).

The approximation \(m(m+1)\ln N\) follows the simulated values closely over two decades of \(N\). The small deviations come from the approximations in the sum (the lower limit \(k = m\) and the cutoff at \(k_{\max}\)) and from fluctuations of the largest degrees.

NoteExercise

Compute the mean and the variance of the degree for nx.barabasi_albert_graph(N, 2) with \(N = 10^3\) and \(N = 10^4\). Which one changes?

for N in [1_000, 10_000]:
    k = np.array([d for _, d in nx.barabasi_albert_graph(N, 2, seed=SEED).degree()])
    print(N, k.mean().round(2), k.var().round(1))

The mean stays close to \(2m = 4\). The variance grows with \(N\), as the logarithmic divergence of \(\langle k^2 \rangle\) predicts.

  • nx.powerlaw_cluster_graph(n, m, p, seed=...) adds a triangle-closing step to preferential attachment, which raises the clustering.
  • nx.scale_free_graph(n, seed=...) returns a directed multigraph.
  • nx.configuration_model(degree_sequence, seed=...) builds a random graph with any degree sequence you choose.

For this course, nx.barabasi_albert_graph is usually the best starting point.

Compare the three models

Generate the three models of this section with the parameters used in Comparing Graph Models. The readout gives the summary metrics of that page: mean degree, clustering, and the average path length of the largest component.

  1. Erdős–Rényi, \(N = 80\). Lower \(p\) from 0.06 towards 0.01 and watch the size of the largest component. Near which \(p\) does it collapse? Compare with \(\langle k \rangle = (N-1)p = 1\).
  2. Watts–Strogatz, \(N = 80\), \(k = 6\). Take the rewiring probability through \(p = 0\), \(0.08\) and \(1\). Clustering goes from 0.60 to about 0.47 and then to about 0.07, while \(L\) drops from about 7.1 to 3.5 and then 2.6. Which value of \(p\) gives a small world?
  3. Barabási–Albert, \(N = 200\), \(m = 2\). Switch to log–log axes and compare the points with \(p_k = 2m(m+1)/(k(k+1)(k+2))\). Then build an Erdős–Rényi graph with the same mean degree (\(N = 200\), \(p = 4/199 \approx 0.020\)). How do the largest degrees compare?
  4. With the same two graphs, compare the clustering coefficients. Does preferential attachment produce triangles?

Build this in Python. In the lab you write the code behind this figure: Comparing Graph Models. You will generate the three models with nx.erdos_renyi_graph, nx.watts_strogatz_graph and nx.barabasi_albert_graph and summarise each with the same metrics. Practice: Real Networks applies the same metrics to the Enron email and US flight networks.

What’s Next?

The next page compares the three models with the same summary metrics.

See also: Triadic Closure (Holme-Kim), a growth model that keeps preferential attachment but adds tunable clustering.

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.
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.