Networks and Hubs

How Epidemics Spread

Chapter 7 · Networks and Hubs

Picture two towns where the average person has six close contacts. In the first, those contacts are scattered: a neighbour, a colleague in another street, a cousin across town. In the second, nearly everyone you know also knows each other, like a village where the same few families share every kitchen. In a third place, a handful of people (a barber, a bus driver, a teacher) know hundreds, while most people know three or four. The models in How Epidemics Spread 3, How Epidemics Spread 4 and How Epidemics Spread 5 treated all three places identically, because they assumed everyone mixes with everyone at random. How Epidemics Spread 6 added chance but kept that assumption. This chapter drops it and asks: if we keep the average number of contacts fixed, how much does the shape of the contact network change who gets infected, and does it change whom we should vaccinate?

What was run, and what to trust

Every Python snippet in this chapter and in the three exercise solutions was executed, and the output in the comments is what Python printed (random seeds are fixed, so you should get the same numbers with the same Python random generator). The history is from search-result summaries, which are often truncated or model-written, so check the originals before quoting: the small-world model is Watts and Strogatz, Nature 393 (1998); preferential attachment is Barabási and Albert, Science 286 (1999); the finding that epidemics on a wide range of scale-free networks show no threshold is Pastor-Satorras and Vespignani, Physical Review Letters 86 (2001), which concerns idealised, very large networks; the treatment of an SIR outbreak on a network as a percolation problem, with a critical transmissibility, is Newman, Physical Review E 66 (2002); and acquaintance immunisation is Cohen, Havlin and ben-Avraham, Physical Review Letters 91 (2003). I did not see the formulas inside those papers, so the quantities below (the “excess degree” and R = T × excess degree) are my own reasoning, checked only against my simulations; they are inferences, not quotations. Where my simulation disagrees with that reasoning (clustered networks), I say so. The network sizes, mean degrees, transmission chances T, vaccination shares, run counts and the 20-case fizzle threshold are all assumed or illustrative, not estimates for any real disease or population. No calculus is used.

Three Kinds of Network

A network (graph) is people, called nodes, joined by links that mean “could pass the infection to”. The number of links a person has is their degree. The code below builds three networks of 2,000 people, all with a mean degree of about 6, using only the standard library. A random network joins random pairs. A clustered network starts as a ring where everyone knows the three people on each side, then rewires 5 per cent of links to random far-away people, the recipe of the small-world model. A hub network grows one person at a time, each newcomer linking to three existing people with a bias towards those who already have many links (preferential attachment). The function describe reports the mean degree, the biggest hub, the clustering coefficient (the share of a person’s pairs of contacts who are also linked to each other), and the excess degree: the average number of further contacts that a randomly followed contact has. It is computed as (mean of degree squared − mean degree) divided by mean degree. The excess degree is larger than the mean degree whenever degrees vary, because following a link is more likely to land on a well-connected person (the so-called friendship paradox).

# Three kinds of contact network, built from scratch. Sizes and mean degree are assumed.
import random

def random_network(n, mean_degree):
    """Random network: pick random pairs until there are n * mean_degree / 2 links."""
    nbrs = [set() for _ in range(n)]
    links = 0
    while links < n * mean_degree // 2:
        a, b = random.randrange(n), random.randrange(n)
        if a != b and b not in nbrs[a]:
            nbrs[a].add(b)
            nbrs[b].add(a)
            links += 1
    return nbrs

def clustered_network(n, mean_degree, rewire):
    """Ring of neighbours (everyone knows the people nearby); each link is rewired at random with chance `rewire`."""
    nbrs = [set() for _ in range(n)]
    for i in range(n):
        for step in range(1, mean_degree // 2 + 1):
            j = (i + step) % n
            if random.random() < rewire:
                j = random.randrange(n)
                while j == i or j in nbrs[i]:
                    j = random.randrange(n)
            nbrs[i].add(j)
            nbrs[j].add(i)
    return nbrs

def hub_network(n, m):
    """Growth with preferential attachment: each newcomer links to m people, favouring the already well connected."""
    nbrs = [set() for _ in range(n)]
    pool = []                      # a person appears here once per link they have
    targets = list(range(m))
    for new in range(m, n):
        for t in set(targets):
            nbrs[new].add(t)
            nbrs[t].add(new)
        pool.extend(targets)
        pool.extend([new] * m)
        targets = [random.choice(pool) for _ in range(m)]
    return nbrs

def describe(nbrs):
    n = len(nbrs)
    degrees = [len(x) for x in nbrs]
    mean = sum(degrees) / n
    excess = (sum(d * d for d in degrees) / n - mean) / mean   # average number of *other* contacts a contact has
    tri, trip = 0, 0
    for i in range(n):
        d = degrees[i]
        if d >= 2:
            trip += d * (d - 1) / 2
            tri += sum(len(nbrs[i] & nbrs[j]) for j in nbrs[i]) / 2
    return mean, max(degrees), excess, tri / trip

random.seed(7)
n = 2000
networks = {
    "random":    random_network(n, 6),
    "clustered": clustered_network(n, 6, 0.05),
    "hubs":      hub_network(n, 3),
}
print("network     mean degree  biggest hub  excess degree  clustering")
for name, g in networks.items():
    mean, biggest, excess, clustering = describe(g)
    print(f"{name:10s} {mean:12.2f} {biggest:12d} {excess:14.2f} {clustering:11.3f}")
# network     mean degree  biggest hub  excess degree  clustering
# random             6.00           16           6.05       0.003
# clustered          6.00            9           5.05       0.507
# hubs               5.96          215          15.58       0.009
    

All three have a mean degree of 6, yet they look nothing alike. The random network has almost no clustering (0.003) and a biggest hub of only 16 contacts. The clustered network has clustering of 0.507: half of a person’s pairs of contacts know each other. The hub network has someone with 215 contacts, and its excess degree of 15.58 is far above its mean of 5.96, while the random network’s excess degree is 6.05, almost equal to its mean. The clustered network’s excess degree is 5.05, just below 6, because nearly everyone has exactly 6 contacts and, of those, one is the person who infected you.

	Random	Clustered	Hubs
How it is built	random pairs linked	ring of neighbours, 5% rewired	newcomers favour well-connected people
Mean degree	6.00	6.00	5.96
Biggest hub	16	9	215
Excess degree	6.05	5.05	15.58
Clustering	0.003	0.507	0.009
Rough everyday picture (an analogy, not data)	scattered acquaintances	village or school year	a few very busy people among many quiet ones

Spreading on a Network

Now we spread an infection. Pick a random person, infect them, and give them one chance to infect each of their contacts, each with probability T (the transmissibility: the chance an infection passes along one link during the whole infectious period). Newly infected people get their own chance, and the outbreak stops when no new cases appear. Each run reports how many people were ever infected, and many runs give a fizzle rate, as in How Epidemics Spread 6. Two numbers are printed for comparison. The “simple R” is T times the mean degree, which is what a model with no network structure would use. The “network R” is T times the excess degree, my reasoning being that a newly infected person was reached through one link, so what matters is how many other links they have. This reuses the three networks built above, so run it in the same file, below the previous snippet.

# Spread on each network: every infected person gets one chance to infect each neighbour.
import random

def outbreak(nbrs, T, blocked=frozenset()):
    """One outbreak from a random unblocked person; returns how many people were ever infected."""
    start = random.randrange(len(nbrs))
    while start in blocked:
        start = random.randrange(len(nbrs))
    reached, frontier = {start}, [start]
    while frontier:
        following = []
        for u in frontier:
            for v in nbrs[u]:
                if v not in reached and v not in blocked and random.random() < T:
                    reached.add(v)
                    following.append(v)
        frontier = following
    return len(reached)

def summarise(nbrs, T, runs, blocked=frozenset()):
    sizes = [outbreak(nbrs, T, blocked) for _ in range(runs)]
    big = [s for s in sizes if s > 20]
    fizzled = 1 - len(big) / runs
    share = sum(big) / len(big) / len(nbrs) if big else 0.0   # 0 if none took off
    return fizzled, share, sum(sizes) / runs / len(nbrs)

random.seed(8)
runs = 400
print("T      network     simple R=T*mean   network R=T*excess   fizzled   size if it takes off (0 = none)   average size")
for T in [0.10, 0.25]:
    for name, g in networks.items():
        mean, biggest, excess, clustering = describe(g)
        fizzled, share, average = summarise(g, T, runs)
        print(f"{T:4.2f}  {name:10s} {T * mean:15.2f} {T * excess:20.2f} {fizzled:9.1%} {share:32.1%} {average:14.1%}")
# T      network     simple R=T*mean   network R=T*excess   fizzled   size if it takes off (0 = none)   average size
# 0.10  random                0.60                 0.60     99.8%                             1.1%           0.1%
# 0.10  clustered             0.60                 0.50    100.0%                             0.0%           0.1%
# 0.10  hubs                  0.60                 1.56     88.5%                             5.8%           0.8%
# 0.25  random                1.50                 1.51     39.2%                            58.2%          35.4%
# 0.25  clustered             1.50                 1.26     77.2%                             2.1%           0.7%
# 0.25  hubs                  1.49                 3.89     42.8%                            57.9%          33.2%
    

With T = 0.25 and a simple R of 1.5, the random network behaves like the well-mixed model of How Epidemics Spread 6: 39.2 per cent of outbreaks fizzle (the branching-process figure for Poisson offspring would be a little higher, near 42 per cent, but the offspring here are binomial and the networks finite, so I do not expect an exact match) and the rest reach 58.2 per cent of the population. The network R of 1.51 matches. The hub network has the same simple R but a network R of 3.89, and the fizzle rate is similar (42.8 per cent). The size of those that take off (57.9 per cent) is also similar to the random network, which I did not expect. A plausible reason (an inference I did not test) is that most people in the hub network have only a few links, and these cap how far an infection can reach. The difference shows at low transmissibility. At T = 0.10 the simple R is 0.60 for every network, so a model without structure predicts a certain fizzle; in the random network the outbreak does fizzle in 99.8 per cent of runs, but in the hub network 11.5 per cent of runs take off, and the average share infected is 0.8 per cent, against 0.1 per cent. Hubs make an epidemic possible when the average contact count says it should not be.

The clustered network goes the other way. Its network R (1.26 at T = 0.25) predicts spread, but 77.2 per cent of outbreaks fizzle, and those that pass 20 cases infect only 2.1 per cent of the population on average. Here my formula fails. A plausible reason (again an inference, untested) is that when your contacts know each other, many of the people you might infect are already infected, or about to be, by someone else, and the infection can only creep around the ring. The formula assumes that a contact’s other contacts are new people, which is true in a random network and false in a clustered one. Exercise 1 explores this.

T = 0.25	Random	Clustered	Hubs
Simple R = T × mean degree	1.50	1.50	1.49
Network R = T × excess degree	1.51	1.26	3.89
Outbreaks that fizzle	39.2%	77.2%	42.8%
Average share infected, all runs	35.4%	0.7%	33.2%
Does the network R predict it?	yes	no (clustering breaks it)	partly (low T, yes; size, no)

Targeted Control

How Epidemics Spread 4 treated vaccination as a share of the population chosen at random. On a network we can choose whom. The code vaccinates 10 per cent of people, treated as removed from the network, by four rules: nobody; random people; the busiest people (most contacts); and acquaintance vaccination, where you pick random people and vaccinate one of their contacts, which needs no knowledge of who the hubs are. The idea is credited to the 2003 paper by Cohen, Havlin and ben-Avraham (per search summaries, which describe it as lowering the immunisation threshold a great deal). The numbers below are from my simulation, not theirs. The outbreak is T = 0.25 on the random and hub networks. As before, this continues the same file.

# Targeted control: vaccinate 10% of people and compare how they are chosen. T and the 10% are assumed.
import random

def choose_random(nbrs, count):
    return frozenset(random.sample(range(len(nbrs)), count))

def choose_busiest(nbrs, count):
    ranked = sorted(range(len(nbrs)), key=lambda i: len(nbrs[i]), reverse=True)
    return frozenset(ranked[:count])

def choose_acquaintance(nbrs, count):
    """Pick a random person, then vaccinate one of their contacts (no need to know who the hubs are)."""
    chosen = set()
    while len(chosen) < count:
        person = random.randrange(len(nbrs))
        if nbrs[person]:
            chosen.add(random.choice(sorted(nbrs[person])))
    return frozenset(chosen)

random.seed(9)
T, runs = 0.25, 400
count = len(networks["random"]) // 10
rules = [("nobody", lambda g, c: frozenset()), ("random", choose_random),
         ("busiest", choose_busiest), ("acquaintance", choose_acquaintance)]
print("average share infected, T = 0.25, 10% vaccinated")
print("network     " + "".join(f"{label:>14s}" for label, _ in rules))
for name in ["random", "hubs"]:
    g = networks[name]
    row = ""
    for label, rule in rules:
        fizzled, share, average = summarise(g, T, runs, rule(g, count))
        row += f"{average:14.1%}"
    print(f"{name:10s} {row}")
# average share infected, T = 0.25, 10% vaccinated
# network             nobody        random       busiest  acquaintance
# random              31.3%         18.3%          2.5%         15.5%
# hubs                35.9%         21.1%          0.1%          6.7%
    

Vaccinating 10 per cent at random cuts the average share infected from 31.3 to 18.3 per cent on the random network and from 35.9 to 21.1 per cent on the hub network. Vaccinating the busiest 10 per cent cuts it to 2.5 and 0.1 per cent. The hub network is the clearest case: removing the best-connected people takes away a large share of all the links at once. Acquaintance vaccination lands in between: 15.5 per cent on the random network and 6.7 per cent on the hub network, a better result than random vaccination, achieved without knowing who the hubs are. It works because a random contact is likelier to be a hub than a random person is (my explanation, consistent with the friendship paradox above). Exercise 3 asks how few people you need on the hub network.

Compare this with the herd-immunity threshold 1 − 1/R0 of How Epidemics Spread 4. That rule assumes random vaccination in a well-mixed population. On a hub network it overstates what is needed if you can find the hubs, and where you cannot find them it may not apply at all. The idea that a few well-chosen people can matter more than many random people is an inference from this model, not a claim about any real disease.

10% vaccinated, T = 0.25	Nobody	Random	Acquaintance	Busiest first
Random network	31.3%	18.3%	15.5%	2.5%
Hub network	35.9%	21.1%	6.7%	0.1%
Needs to know the hubs?	no	no	no	yes

Common mistakes

Treating the mean number of contacts as the whole story (two networks with the same mean can behave very differently); applying T × excess degree to a highly clustered network, where it overpredicts; quoting the “no epidemic threshold” result for scale-free networks as if it applied to every network with hubs (it concerns idealised, very large networks, and my 2,000-person hub network does show a gradual takeoff rather than none); assuming the busiest people are known in real life (finding them is the hard part, which is why acquaintance vaccination is interesting); forgetting that these networks are static, while real contacts change from day to day; reporting one run instead of a rate from many; and using the illustrative numbers here (T, 6 contacts, 2,000 people, 10 per cent vaccinated, the 20-case threshold) as if they were estimates for a real disease.

Exercise 1

Build clustered networks of 2,000 people with mean degree 6 and rewiring chances of 0, 0.01, 0.05, 0.2 and 1 (assumed), and spread an infection with T = 0.25 (assumed) through each, 300 runs. Print the clustering, the excess degree, the fizzle rate and the average share infected. Does the excess degree explain the differences?

📄 View solution

Exercise 2

For a random network and a hub network (2,000 people, mean degree 6), print the predicted threshold T = 1 / excess degree, then the average share infected for T from 0.03 up to 0.25 (assumed values). Roughly where does each network start to take off, and does it match the prediction?

📄 View solution

Exercise 3

On a hub network of 2,000 people with T = 0.25 (assumed), vaccinate 0, 1, 2, 3, 5, 8 and 10 per cent of people, chosen at random or busiest first. Print the average share infected for each. How small a share, chosen well, is enough to stop almost all spread?

📄 View solution

Quick Reference

Network: people as nodes, possible transmissions as links; degree = number of links
Random / clustered / hub: scattered links; neighbours who know each other; a few people with very many links
Excess degree: (mean of degree squared − mean degree) / mean degree; the further contacts of a contact
Transmissibility T: chance of passing the infection along one link; simple R = T × mean degree, network R = T × excess degree (my reasoning)
Hubs: lower the threshold; make outbreaks possible when the mean contact count says no
Clustering: wastes transmissions on people already infected, so the excess-degree rule overpredicts
Targeted control: busiest-first beats random; acquaintance vaccination beats random without finding the hubs
Assumes: static networks, equal T on every link, illustrative numbers

Coming next

How Epidemics Spread 8 is about measuring and estimating: estimating R from data, serial intervals, case-control and cohort studies, bias in testing.