---
title: "Preferential Attachment"
subtitle: "Module 5: Complex Networks"
format: html
---
::: {.callout-note}
## Reading
- **Compulsory:** @barabasi1999emergence.
- **Recommended:** @newman2003structure, 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}$ [@barabasi1999emergence; @newman2003structure, Section 3.3]. Barabási and Albert proposed that two ingredients generate such a distribution: **growth** and **preferential attachment** [@barabasi1999emergence].
## 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$ [@newman2003structure, Section 7.2; @newman2018networks].
- The degrees of the oldest nodes grow like $\sqrt{t}$, so the largest degree grows like $k_{\max} \sim m\sqrt{N}$ [@barabasi1999emergence; @newman2018networks].
- 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$ [@newman2003structure, Section 7.2].
The divergence of $\langle k^2 \rangle$ drives two results of this module: the robustness to random failure in [Robustness and Percolation](robustness-percolation.qmd) and the vanishing epidemic threshold in [Epidemic Threshold](epidemic-threshold.qmd). 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}.
$$ {#eq-ba-growth}
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 @eq-ba-growth 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.
```{python}
#| label: fig-ba-continuum
#| fig-cap: "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))."
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}")
```
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.
```{python}
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
@fig-ba-degree 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.
```{python}
#| label: fig-ba-degree
#| fig-cap: "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)."
#| echo: false
m = 2
G = nx.barabasi_albert_graph(20_000, m, seed=SEED)
deg = np.array([d for _, d in G.degree()])
ks, counts = np.unique(deg, return_counts=True)
fig, axes = plt.subplots(1, 2, figsize=(8, 3.5))
axes[0].loglog(ks, counts / counts.sum(), "o", ms=3, label="simulation")
k_th = np.arange(m, ks.max() + 1)
axes[0].loglog(k_th, 2 * m * (m + 1) / (k_th * (k_th + 1) * (k_th + 2)), label="exact formula")
axes[0].set_xlabel("k")
axes[0].set_ylabel("p_k")
axes[0].legend()
Ns = np.array([300, 1000, 3000, 10_000, 30_000])
k2 = [np.mean(np.array([d for _, d in nx.barabasi_albert_graph(n, m, seed=SEED).degree()]) ** 2) for n in Ns]
axes[1].semilogx(Ns, k2, "o-", label=r"$\langle k^2 \rangle$")
axes[1].semilogx(Ns, m * (m + 1) * np.log(Ns), "k--", label=r"$m(m+1)\ln N$")
axes[1].set_xlabel("N")
axes[1].legend()
plt.tight_layout()
plt.show()
```
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.
::: {.callout-note}
## Exercise
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?
:::
::: {.callout-tip collapse="true"}
## Solution
```python
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.
:::
::: {.callout-tip collapse="true"}
## Other scale-free generators in NetworkX
- `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](comparing-models.qmd). The readout gives the summary metrics of that page: mean degree, clustering, and the average path length of the largest component.
::: {.viz data-viz="network-models"}
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?
:::
::: {.python-next}
**Build this in Python.** In the lab you write the code behind this figure: [Comparing Graph Models](comparing-models.qmd). 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](practice-real-networks.qmd) 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)](triadic-closure.qmd), a growth model that keeps preferential attachment but adds tunable clustering.