Chapter 4 Scale-Free Networks, Preferential Attachment and Robustness

Degree distributions

The number of a person’s contacts is called his or her degree. In the random graphs studied by Erdős and Rényi, every pair is connected with the same probability, so degrees cluster around the mean and people far above it are extremely rare (Erdős and Rényi 1960). Many real networks do not look like this: a few nodes have a very large number of connections and most have very few.

Evidence

Preferential attachment. In 1999 Barabási and Albert reported that the tails of the degree distributions of the film-actor collaboration network, the World Wide Web and the power grid of the western United States roughly follow a power law $P(k) \sim k^{-\gamma}$ , with estimated exponents of about 2.3, 2.1 and 4 respectively. They proposed a model with two mechanisms to explain it: the network keeps growing, and new nodes attach preferentially to nodes that already have many connections (with probability proportional to their degree). The model produces a power-law degree distribution with a theoretical exponent of 3; their simulations gave $\gamma = 2.9 \pm 0.1$ (Barabási and Albert 1999). A power-law distribution has no characteristic scale, hence the term “scale-free”.

Volume 6 of 5D Library, The Economics of Attention, has already implemented this model and estimated an exponent of about 2.91. This chapter does not repeat it, but takes up two follow-up questions: how to decide whether a set of data follows a power law, and what scale-free structure implies for a network’s robustness.

“Scale-free networks are rare”

The most common way of judging a power law is to plot the degree distribution on log–log axes, see whether it looks like a straight line, and fit its slope by least squares. Clauset, Shalizi and Newman showed that this procedure is badly biased: many distributions that are not power laws also look nearly straight on log–log axes, and least-squares slope estimates are biased too. They recommended estimating the exponent by maximum likelihood, choosing the lower bound $k_{\min}$ above which the power law holds by goodness of fit, and comparing the power law with alternatives such as the log-normal by likelihood-ratio tests (Clauset, Shalizi, and Newman 2009).

Evidence

A test on nearly a thousand networks. Broido and Clauset applied this methodology to nearly a thousand real networks from social, biological, technological, information and transport domains. Of several levels they defined, only about 4 % of the networks showed the “strongest” evidence of scale-free structure, and 52 % only the “weakest”; for most networks a log-normal distribution fitted the tail of the degree distribution as well as or better than a power law. Social networks were at best weakly scale-free, while a handful of technological and biological networks showed stronger evidence (Broido and Clauset 2019).

Evidence

A dispute about definitions. The paper set off a lively debate. In a commentary published alongside it, Holme concluded that much of the disagreement stems from different understandings of “scale-free”: if it means a strict power-law distribution, it is indeed rare; if it means that the degree distribution has a long right tail and a few hubs are structurally and functionally decisive, it is almost everywhere; hence his title, “Rare and everywhere” (Holme 2019).

Calculation

Two synthetic samples of “degrees” illustrate the statistical problem. BA: a Barabási–Albert network of 20,000 nodes (each new node links to 2 old ones), whose tail is in theory a power law with exponent 3. LN: 20,000 rounded log-normal random numbers, which are not a power law. For each sample we estimate the exponent by maximum likelihood for several values of $k_{\min}$ (discrete approximation), and at $k_{\min} = 8$ we run a likelihood-ratio test of power law against log-normal (continuous approximation, log-normal fitted by grid search; Vuong’s normalised ratio $z$ and a two-sided $p$ value are reported).

# Is it a power law? Maximum-likelihood exponent and a likelihood-ratio test
# against a log-normal (in the spirit of Clauset, Shalizi & Newman 2009 and
# Broido & Clauset 2019). Two synthetic degree samples of 20,000 nodes:
#   BA: a Barabasi-Albert network with m = 2 (true tail exponent 3);
#   LN: rounded log-normal values exp(Normal(1.0, 0.8)), not a power law.
# Exponent: alpha = 1 + n / sum ln(k / (kmin - 0.5)) (discrete approximation).
# LR test: continuous approximation above kmin - 0.5; the log-normal is fitted
# by grid search (mu -24 to 4, sigma 0.2 to 4; the tail mass uses erfc, which
# stays accurate far out in the tail); Vuong's normalised ratio z and
# two-sided p are reported.
import math, random
from statistics import NormalDist
rng, PHI = random.Random(9), NormalDist().cdf
N, M = 20000, 2
targets, deg = [], [0] * N
for i in range(M + 1):
    for j in range(i):
        targets += [i, j]; deg[i] += 1; deg[j] += 1
for new in range(M + 1, N):
    chosen = set()
    while len(chosen) < M:
        chosen.add(rng.choice(targets))
    for t in chosen:
        targets += [t, new]; deg[t] += 1; deg[new] += 1
samples = {"BA": deg,
           "LN": [max(1, round(math.exp(rng.gauss(1.0, 0.8)))) for _ in range(N)]}

def alpha_hat(ks, kmin):
    tail = [k for k in ks if k >= kmin]
    a = 1 + len(tail) / sum(math.log(k / (kmin - 0.5)) for k in tail)
    return a, (a - 1) / math.sqrt(len(tail)), len(tail)

def lr_test(ks, kmin):
    x = [k for k in ks if k >= kmin]; xm = kmin - 0.5; n = len(x)
    a = 1 + n / sum(math.log(v / xm) for v in x)
    lp = [math.log((a - 1) / xm) - a * math.log(v / xm) for v in x]
    lx = [math.log(v) for v in x]
    def ln_ll(mu, s):
        tailp = 0.5 * math.erfc((math.log(xm) - mu) / (s * math.sqrt(2)))
        if tailp < 1e-300: return None
        c = -math.log(s * math.sqrt(2 * math.pi)) - math.log(tailp)
        return [c - l - (l - mu) ** 2 / (2 * s * s) for l in lx]
    best = None
    grid = [(mu / 4, s / 10) for mu in range(-96, 17) for s in range(2, 41)]
    for mu, s in grid:
        ll = ln_ll(mu, s)
        if ll is not None and (best is None or sum(ll) > best[0]):
            best = (sum(ll), mu, s, ll)
    d = [p - q for p, q in zip(lp, best[3])]
    R = sum(d); sd = math.sqrt(sum((v - R / n) ** 2 for v in d) / n)
    z = R / (sd * math.sqrt(n))
    return R, z, 2 * PHI(-abs(z)), best[1], best[2]

for name, ks in samples.items():
    print(f"{name}: max value {max(ks)}")
    for kmin in (2, 4, 8, 16):
        a, se, n = alpha_hat(ks, kmin)
        print(f"   kmin {kmin:2d}: alpha = {a:.2f} +/- {se:.2f} (n tail = {n})")
    R, z, p, mu, sig = lr_test(ks, 8)
    if p >= 0.1:
        verdict = "cannot tell them apart"
    else:
        verdict = "power law favoured" if z > 0 else "log-normal favoured"
    print(f"   kmin 8, power law vs log-normal: R = {R:+.1f}, z = {z:+.2f},"
          f" p = {p:.3f}")
    print(f"      -> {verdict}; best log-normal mu = {mu:.2f}, sigma = {sig:.1f}")
# BA: max value 418
#    kmin  2: alpha = 2.40 +/- 0.01 (n tail = 20000)
#    kmin  4: alpha = 2.69 +/- 0.02 (n tail = 6002)
#    kmin  8: alpha = 2.80 +/- 0.04 (n tail = 1630)
#    kmin 16: alpha = 2.77 +/- 0.09 (n tail = 431)
#    kmin 8, power law vs log-normal: R = -0.8, z = -0.63, p = 0.531
#       -> cannot tell them apart; best log-normal mu = -12.00, sigma = 2.9
# LN: max value 57
#    kmin  2: alpha = 2.09 +/- 0.01 (n tail = 15408)
#    kmin  4: alpha = 2.77 +/- 0.02 (n tail = 7504)
#    kmin  8: alpha = 3.60 +/- 0.06 (n tail = 2062)
#    kmin 16: alpha = 4.56 +/- 0.21 (n tail = 301)
#    kmin 8, power law vs log-normal: R = -32.0, z = -5.73, p = 0.000
#       -> log-normal favoured; best log-normal mu = 1.00, sigma = 0.8

Three points stand out. First, even when the data really do come from a preferential-attachment model, the estimated exponent changes with $k_{\min}$ : 2.40 at $k_{\min} = 2$ and 2.80 at $k_{\min} = 8$ , both below the theoretical value of 3, because in a finite network the tail has not fully formed. Second, at $k_{\min} = 4$ the log-normal data also give an “exponent” of 2.77, almost the same as the BA data; only by raising $k_{\min}$ step by step does one see its “exponent” keep growing (3.60, 4.56), revealing that it is not a power law. Third, the likelihood-ratio test gives a clear verdict for the log-normal data ( $z = -5.73$ , favouring the log-normal); but for the genuine BA data the test cannot tell the power law from the log-normal ( $z = -0.63$ , $p = 0.53$ ), and the best-fitting log-normal parameters ( $\mu = -12$ , $\sigma = 2.9$ ) show it imitating a power law with an extremely broad distribution. In other words, with about 1,600 data points in the tail, “the power law cannot be rejected” is not the same as “it has been shown to be a power law”; this is part of the reason why so many of Broido and Clauset’s networks fall into the “weak evidence” levels.

Random failure and targeted attack

An important consequence of scale-free structure concerns robustness.

Evidence

Failure and attack. In 2000 Albert, Jeong and Barabási compared how scale-free networks and random networks with exponentially decaying degree distributions behave when nodes are removed. When nodes were removed at random (simulating failures), scale-free networks, including the real topologies of the World Wide Web and the Internet, showed great tolerance, their diameter remaining almost unchanged; but when the most connected nodes were removed first (simulating an attack), scale-free networks broke apart quickly. The exponential random networks behaved similarly in both cases (Albert, Jeong, and Barabási 2000).

Calculation

A BA network with 2,000 nodes ( $m = 2$ ) and a random (ER) network with the same numbers of nodes and ties. Nodes are removed step by step, either at random (averaged over 10 random orders) or in order of initial degree from highest to lowest (attack), and we record the share $S$ of the original nodes in the largest connected component.

# Error and attack tolerance (after Albert, Jeong & Barabasi 2000).
# A Barabasi-Albert network (N = 2000, each newcomer links to m = 2 existing
# nodes with probability proportional to degree) and an Erdos-Renyi network
# with the same number of nodes and ties. Nodes are removed either at random
# (failures; mean of 10 orders) or in order of initial degree, highest first
# (attack). S = share of the ORIGINAL nodes in the largest connected component.
import random
N, M = 2000, 2

def ba(rng):
    edges, targets = set(), []
    for i in range(M + 1):                       # small complete seed graph
        for j in range(i):
            edges.add((j, i)); targets += [i, j]
    for new in range(M + 1, N):
        chosen = set()
        while len(chosen) < M:
            chosen.add(rng.choice(targets))
        for t in chosen:
            edges.add((t, new)); targets += [t, new]
    return list(edges)

def er(n_edges, rng):
    edges = set()
    while len(edges) < n_edges:
        a, b = rng.randrange(N), rng.randrange(N)
        if a != b: edges.add((min(a, b), max(a, b)))
    return list(edges)

def giant(edges, removed):
    par = list(range(N))
    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]; x = par[x]
        return x
    for a, b in edges:
        if a not in removed and b not in removed:
            ra, rb = find(a), find(b)
            if ra != rb: par[ra] = rb
    size = {}
    for x in range(N):
        if x not in removed:
            r = find(x); size[r] = size.get(r, 0) + 1
    return max(size.values(), default=0) / N

def curves(edges, fracs, rng, orders=10):
    deg = [0] * N
    for a, b in edges: deg[a] += 1; deg[b] += 1
    attack = sorted(range(N), key=lambda v: (-deg[v], rng.random()))
    rand = [rng.sample(range(N), N) for _ in range(orders)]
    out = []
    for f in fracs:
        k = int(f * N)
        r = sum(giant(edges, set(o[:k])) for o in rand) / orders
        out.append((f, r, giant(edges, set(attack[:k]))))
    return out, deg

if __name__ == "__main__":
    rng = random.Random(8)
    fracs = (0, 0.05, 0.1, 0.15, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, 0.9)
    g_ba = ba(rng); g_er = er(len(g_ba), rng)
    res_ba, d_ba = curves(g_ba, fracs, rng)
    res_er, d_er = curves(g_er, fracs, rng)
    for name, d in (("BA", d_ba), ("ER", d_er)):
        k1 = sum(d) / N; k2 = sum(x * x for x in d) / N
        print(f"{name}: {len(g_ba)} ties, mean degree {k1:.2f},"
              f" max degree {max(d)}, <k^2>/<k> = {k2 / k1:.1f}")
    print("removed   BA random  BA attack   ER random  ER attack")
    for (f, a, b), (_, c, e) in zip(res_ba, res_er):
        print(f"  {f:4.0%}      {a:5.2f}     {b:5.2f}       {c:5.2f}     {e:5.2f}")
# BA: 3997 ties, mean degree 4.00, max degree 104, <k^2>/<k> = 11.6
# ER: 3997 ties, mean degree 4.00, max degree 13, <k^2>/<k> = 5.0
# removed   BA random  BA attack   ER random  ER attack
#     0%       1.00      1.00        0.98      0.98
#     5%       0.95      0.86        0.93      0.92
#    10%       0.89      0.63        0.87      0.85
#    15%       0.84      0.04        0.82      0.78
#    20%       0.78      0.01        0.76      0.69
#    30%       0.65      0.00        0.65      0.37
#    40%       0.52      0.00        0.53      0.06
#    60%       0.24      0.00        0.25      0.00
#    70%       0.11      0.00        0.08      0.00
#    80%       0.03      0.00        0.01      0.00
#    90%       0.01      0.00        0.00      0.00

Largest connected component of a scale-free (BA) and a random (ER) network under random failure and targeted attack (2,000 nodes, mean degree 4). Solid lines: BA; dashed lines: ER. Attack breaks the BA network once about 15 % of its nodes are gone, the ER network only at about 40 %; under random failure the two are similar over most of the range.

Under attack the difference is stark: after the 10 % of nodes with the highest degree are removed, the BA network’s largest component still holds 63 % of the nodes, and after 15 % only 4 %; the same attack does much less damage to the ER network, which keeps 78 % after 15 % of its nodes are removed and only falls to 6 % after 40 %. The highest-degree node in the BA network has 104 connections, in the ER network at most 13: attacking a scale-free network means first taking out the hubs that hold it together.

Under random failure the result may be surprising: at this size the two networks behave almost identically. After 40 % of the nodes are removed at random, the BA network keeps 52 % and the ER network 53 %; only beyond 70 % does the BA network do slightly better (0.11 against 0.08 at 70 %). A classical criterion from random-graph theory explains why.

Calculation

For a network whose nodes are connected at random with a given degree distribution, a giant connected component exists if $\kappa = \langle k^2 \rangle / \langle k \rangle > 2$ . Removing a share $f$ of the nodes at random shrinks $\kappa – 1$ by the factor $(1-f)$ , which gives the critical share

$f_c = 1 – \frac{1}{\kappa – 1}$

For the ER network $\kappa = 5.0$ and $f_c = 0.75$ ; for this BA network $\kappa = 11.6$ and $f_c \approx 0.91$ . The difference between the two lies mainly at the high-removal end. For infinitely large scale-free networks with exponent $\gamma \le 3$ , $\langle k^2 \rangle$ diverges and $f_c$ tends to 1: this is the source of the “extreme robustness to random failure”; but it is an asymptotic result, and in finite networks with a limited maximum degree the advantage is much smaller.

So the second half of the statement “scale-free networks are robust to failure and fragile under attack” is highly reliable in finite networks, while the first half depends heavily on the size of the network and the shape of the tail of its degree distribution. Albert and colleagues mainly measured robustness by the network diameter, and the samples of the Web and the Internet they studied were much larger than the simulation here.

Note

When applied to people. In a social network, “removing a node” means a person leaving, being shut out or being banned. The model shows that a few very well connected people contribute disproportionately to the connectedness of the whole network; this conclusion has clear uses in public health (for instance, vaccinating the most connected people first) and in protecting infrastructure. But it could also be used to design strategies for breaking up a community. This book discusses the model to understand the fragility of networks, not to provide a method aimed at any person or group.

Chapter summary

Preferential attachment can produce power-law degree distributions, but deciding whether real data follow a power law requires maximum-likelihood estimation and comparison with other distributions; a test on nearly a thousand networks found strong scale-free evidence to be uncommon, and part of the dispute stems from different definitions of “scale-free”. The programs show that even when data really do come from preferential attachment, at moderate sizes a power law is hard to distinguish from a log-normal. Scale-free networks are very fragile under targeted attack; their advantage in robustness against random failure is an asymptotic result and small at finite sizes. The next chapter turns to another family of position measures, which look not only at how many connections a person has but at whom they connect to.

References

Albert, Réka, Hawoong Jeong, and Albert-László Barabási. 2000. “Error and Attack Tolerance of Complex Networks.” Nature 406 (6794): 378–82. https://doi.org/10.1038/35019019.

Barabási, Albert-László, and Réka Albert. 1999. “Emergence of Scaling in Random Networks.” Science 286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509.

Broido, Anna D., and Aaron Clauset. 2019. “Scale-Free Networks Are Rare.” Nature Communications 10: 1017. https://doi.org/10.1038/s41467-019-08746-5.

Clauset, Aaron, Cosma Rohilla Shalizi, and M. E. J. Newman. 2009. “Power-Law Distributions in Empirical Data.” SIAM Review 51 (4): 661–703. https://doi.org/10.1137/070710111.

Erdős, Paul, and Alfréd Rényi. 1960. “On the Evolution of Random Graphs.” Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5: 17–61.

Holme, Petter. 2019. “Rare and Everywhere: Perspectives on Scale-Free Networks.” Nature Communications 10: 1016. https://doi.org/10.1038/s41467-019-09038-8.

Fan, Y. (2026). Social Network Topology, Structural Holes and Complex Contagion: From the Strength of Weak Ties and Preferential Attachment to Information Cascades, Read Beside Classical Chinese Diplomacy [社会网络拓扑、结构洞与复杂传染的数学模型] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23764990 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).