Skip to main content

Epidemic Threshold

Module 5: Complex Networks

NoteReading
  • Compulsory: Pastor-Satorras et al. (2015), Sections IV.B (degree-based mean field), V.A (SIS) and V.B (SIR).
  • Recommended: Newman (2002).
  • What the review states: For the SIS model, the degree-based mean-field theory gives the threshold \(\lambda_c = \langle k \rangle / \langle k^2 \rangle\) (their Eq. 28), which tends to zero for degree exponents \(2 < \gamma \le 3\) in the limit of infinite size. For SIR, the mapping to bond percolation gives for tree-like uncorrelated networks the exact threshold in transmissibility \(T_c = \langle k \rangle / (\langle k^2 \rangle - \langle k \rangle)\) (their Eq. 60), and for exponentially distributed infectious periods, where the mean transmissibility is \(\lambda/(1+\lambda)\), the threshold in the rate ratio \(\lambda_c = \langle k \rangle / (\langle k^2 \rangle - 2\langle k \rangle)\) (their Eq. 62). The expression \(\langle k \rangle / (\langle k^2 \rangle - \langle k \rangle)\) also appears in their Eq. 53 as a threshold in \(\lambda\) from a modified degree-based mean field, which they call an approximation of the exact result. They warn that the individual-based mean-field threshold \(1/\Lambda_1\), applied to SIR, is qualitatively wrong for \(\gamma > 3\).

In the well-mixed SIS model of Compartmental Models, an infection persists only if \(R_0 > 1\). On a network, the corresponding condition depends on the degree distribution. This page derives it and states exactly when the threshold vanishes.

Setup

Use the continuous-time SIS model: each S-I edge transmits at rate \(\beta\) and each infected node recovers at rate \(\mu\). The spreading rate is \(\lambda = \beta/\mu\). In the discrete-time simulations of SIS Simulation, \(\lambda \approx \beta/\mu\) when both probabilities are small.

Homogeneous mean field

If every node had exactly \(\langle k \rangle\) neighbours, the infected density \(\rho\) would obey \(\dot\rho = -\rho + \lambda\langle k \rangle \rho(1-\rho)\) (time in units of \(1/\mu\)). The threshold is \(\lambda_c = 1/\langle k \rangle\) (Pastor-Satorras et al. 2015).

Heterogeneous mean field

Now group nodes by degree. Let \(\rho_k\) be the fraction of infected nodes among nodes of degree \(k\). Assume an uncorrelated network: an edge leads to a node of degree \(k'\) with probability \(k' p_{k'}/\langle k \rangle\). Then (Pastor-Satorras and Vespignani 2001; Pastor-Satorras et al. 2015)

\[ \frac{d\rho_k}{dt} = -\rho_k + \lambda k (1 - \rho_k)\,\Theta, \qquad \Theta = \frac{1}{\langle k \rangle}\sum_{k'} k' p_{k'} \rho_{k'} . \]

Linearize around \(\rho_k = 0\). Multiply by \(k p_k / \langle k \rangle\) and sum over \(k\): \(\dot\Theta = \left(\lambda \langle k^2 \rangle / \langle k \rangle - 1\right)\Theta\). The disease-free state becomes unstable when

\[ \lambda > \lambda_c = \frac{\langle k \rangle}{\langle k^2 \rangle}. \]

For a Poisson degree distribution, \(\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle\) and \(\lambda_c = 1/(\langle k \rangle + 1)\), close to the homogeneous result. For SIR the analogous result is a critical transmissibility \(T_c = \langle k \rangle / (\langle k^2 \rangle - \langle k \rangle)\) (Newman 2002). Note that this is a threshold in the transmissibility \(T\), the probability that an infected node transmits to a given neighbour before recovering, and not in the rate ratio \(\lambda\). With exponentially distributed infectious periods \(T = \lambda/(1+\lambda)\), so \(T_c = 1/(\kappa - 1)\) with \(\kappa = \langle k^2 \rangle / \langle k \rangle\) corresponds to \(\lambda_c = 1/(\kappa - 2) = \langle k \rangle / (\langle k^2 \rangle - 2\langle k \rangle)\) (Pastor-Satorras et al. 2015, Eq. 62). For a Poisson graph with \(\langle k \rangle = 6\) this gives \(T_c = 1/6\) and \(\lambda_c = 1/5\). SIR as Bond Percolation derives the relation.

When does the threshold vanish?

For a scale-free distribution \(p_k \sim k^{-\gamma}\) with \(2 < \gamma \le 3\), \(\langle k^2 \rangle\) diverges as \(N \to \infty\), so \(\lambda_c \to 0\) (Pastor-Satorras and Vespignani 2001). Read this result with its assumptions:

  • It is an asymptotic result for an idealized infinite scale-free network with \(2 < \gamma \le 3\).
  • It relies on the heterogeneous mean-field approximation, which ignores degree correlations and the fixed structure of the contacts.
  • Every finite network has a largest degree \(k_{\max}\), so \(\langle k^2 \rangle\) is finite and the threshold is small but nonzero (Pastor-Satorras and Vespignani 2002). For the Barabási-Albert model, \(\langle k^2 \rangle \approx m(m+1)\ln N\) (see Preferential Attachment), so the formula gives \(\lambda_c \approx 2/\big((m+1)\ln N\big)\), which decreases only logarithmically with \(N\).
  • Other approximations give other finite-size thresholds. The quenched mean-field theory, which keeps the full adjacency matrix, predicts \(\lambda_c = 1/\Lambda_{\max}\), where \(\Lambda_{\max}\) is the largest eigenvalue of \(A\) (Castellano and Pastor-Satorras 2010; Pastor-Satorras et al. 2015).

Figure 1 computes both predictions on generated graphs.

Figure 1: Epidemic threshold predictions against network size for Barabási-Albert (m = 3) and Erdős-Rényi graphs with the same mean degree. Solid: heterogeneous mean field /<k^2>. Dashed: quenched mean field 1/Lambda_max. One graph per size.
BA HMF: [0.079 0.076 0.062 0.054 0.051]
ER HMF: [0.141 0.144 0.143 0.143 0.143]

For the ER graphs the threshold stays near \(1/(\langle k \rangle + 1) = 1/7 \approx 0.14\). For the BA graphs it decreases slowly with \(N\) but stays well above zero at every size you can simulate.

Spread it yourself

The simulation uses the discrete-time update of the lab: a susceptible node with \(m\) infected neighbours is infected with probability \(1 - (1-\beta)^m\), and an infected node recovers with probability \(\mu\). Both networks have mean degree close to 6, as in Figure 1. Vaccinated nodes start immune.

  1. Choose SIS, keep \(\mu = 0.1\) and set \(\beta = 0.015\), so \(\lambda = 0.15\). Run several times on the Barabási–Albert graph, then on the Erdős–Rényi graph. On which network does the infection survive? Compare \(\lambda\) with \(\langle k \rangle / \langle k^2 \rangle\) in the readout.
  2. Back to SIR with \(\beta = 0.05\), \(\mu = 0.1\) on the Barabási–Albert graph. Vaccinate 10% of the nodes at random, then 10% of the hubs first. How much smaller is the final epidemic?
  3. Press Compare strategies over g on each network. Why does vaccinating hubs help so much more on the Barabási–Albert graph than on the Erdős–Rényi graph?
  4. Acquaintance vaccination uses only local information. Where does its curve fall between the other two, and why does a random neighbour tend to be a hub?

Build this in Python. In the lab you write the code behind this figure: SIR Simulation and Vaccination Strategies. You will code the synchronous SIS/SIR update on a NetworkX graph, run it on generated and real networks, and compare random, acquaintance and targeted immunization.

NoteExercise

A BA network with \(m = 3\) has \(N = 10^9\) nodes. Estimate \(\lambda_c\) from the heterogeneous mean-field formula. Compare it with an ER graph with the same mean degree.

\(\lambda_c \approx 2/\big((m+1)\ln N\big) = 2/(4 \times 20.7) \approx 0.024\). The ER graph gives \(\lambda_c = 1/(\langle k \rangle + 1) = 1/7 \approx 0.14\) at any size. Even for a network the size of a large country the BA threshold is small but clearly positive.

Optional extension

NoteExercise

Use amlab.networks_spreading.run_sis_fast on a BA graph with \(N = 2000\). Fix \(\mu = 0.05\), vary \(\beta\), and plot the long-time prevalence against \(\lambda = \beta/\mu\). Locate the value of \(\lambda\) where the prevalence leaves zero and compare it with both predictions.

Start from 50 infected nodes, run 1000 steps and average the last 200 steps over 3 runs.

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from amlab.networks_spreading import run_sis_fast

rng = np.random.default_rng(7)
G = nx.barabasi_albert_graph(2000, 3, seed=7)
mu = 0.05
lams = np.linspace(0.02, 0.2, 10)
prevalence = [
    np.mean([run_sis_fast(G, lam * mu, mu, steps=1000, initial_infected=50, rng=rng)[-200:].mean() for _ in range(3)])
    for lam in lams
]
k = np.array([d for _, d in G.degree()], dtype=float)
plt.plot(lams, prevalence, "o-")
plt.axvline(k.mean() / (k**2).mean(), color="grey", ls=":", label="<k>/<k²>")
plt.xlabel(r"$\lambda = \beta/\mu$")
plt.ylabel("long-time prevalence")
plt.legend()
plt.show()

For this graph both predictions give \(\lambda_c \approx 0.059\). The simulated prevalence is still zero at \(\lambda = 0.08\) and becomes positive between \(0.08\) and \(0.10\). The mean-field theories ignore dynamical correlations: a newly infected node cannot pass the infection back to the neighbour that infected it while that neighbour is still infected, so part of the infection attempts are wasted and the true threshold is higher. On a finite graph, fluctuations also end outbreaks that are just above threshold within the simulated time.

See also: SIR as Bond Percolation, which derives the threshold from the transmissibility of the epidemic.

References

Castellano, Claudio, and Romualdo Pastor-Satorras. 2010. “Thresholds for Epidemic Spreading in Networks.” Physical Review Letters 105 (21): 218701. https://doi.org/10.1103/PhysRevLett.105.218701.
Newman, M. E. J. 2002. “Spread of Epidemic Disease on Networks.” Physical Review E 66 (1): 016128. https://doi.org/10.1103/PhysRevE.66.016128.
Pastor-Satorras, Romualdo, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. “Epidemic Processes in Complex Networks.” Reviews of Modern Physics 87 (3): 925–79. https://doi.org/10.1103/RevModPhys.87.925.
Pastor-Satorras, Romualdo, and Alessandro Vespignani. 2001. “Epidemic Spreading in Scale-Free Networks.” Physical Review Letters 86 (14): 3200–3203. https://doi.org/10.1103/PhysRevLett.86.3200.
Pastor-Satorras, Romualdo, and Alessandro Vespignani. 2002. “Epidemic Dynamics in Finite Size Scale-Free Networks.” Physical Review E 65 (3): 035108. https://doi.org/10.1103/PhysRevE.65.035108.