# Chapter 21. Epidemics

[TOC]

> The arrival of Europeans in the Americas(Smallpox)[^130]
> Bubonic plague(Black Death)[^293]

[^130]: 123
[^293]: 123

## 21.1 Diseases and the Networks That Transmit Them

### Contact Network
- nodes as person
- edges as the spread of disease between two nodes

> travel patterns within a city[^149][^295]
> worldwide airline network[^119]
> the 2001 foot-and-mouth outbreak in the United Kingdom[^211]
> plant disease[^139]
> computer viruses[^241]
> computer viruses between nearby mobile devices[^251]

[^149]:
[^295]:
[^119]:
[^211]:
[^139]:
[^241]:
[^251]:

## 21.2 Branching Processes
- $T$ be a tree with infinite depth
- each node has $k$ children
- initially, mark root as infected
- for each step, a infected node will infect its each children with probability $p$

| Initial |  |
| -------- | -------- |
| Example | |
| Terminate||

:::success
**Definition.**
The *basic reproductive number*, denoted by $R_0$ is the expected number of new cases of the disease caused by a single individual
:::
In this case, $R_0=pk$.
:::info
**Theorem.**
If $R_0<1$, then the probability that the disease dies out before wave $t$ increases to $1$ as $t\to\infty$. If $R_0>1$, then the probability that the disease goes forever is greater than $0$
:::
## 21.3 The SIR Epidemic Model
SIR stands for
- *Susceptible*. susceptible to infection from its neighbors
- *Infectious*. has some probability of infecting each of its susceptible neighbors
- *Removed*. After an infectious period, remove from consideration

The process is
- initially, some nodes are in **I** state, and the other in **S** state
- node $v$ in **I** has porbability $p$ to infect neighbor $w$ in **S**
- after $t_I$ steps in **I**, $v$ turns into **R**

Some extension
- more detailed states
- probability varies, $p_{v,w}$
- probability $q$ to recover before $t_I$ steps

# Percolation
- static view of the process
- assume $t_I=1$
- decide $p$ for each edge first

> static view of SIR process[^44][^173]

[^44]:
[^173]: 1

## 21.4 The SIS Epidemic Model
- for node $v$ in **I**, after $t_I$ steps, turn into $S$ again

- probability that the disease dies out before step $t$ tends to $1$ as $t\to\infty$

> knife-edge between die-out quickly and persistence[^52][^278]

[^52]:
[^278]:

### Time-Expanded Contact Network
- SIS as a special case of SIR
- assume $t_I=1$
- create infinite copy of origin graph for time $t=0,1,2,\ldots$
- create edges from $t$ to $t+1$


## 21.5 Synchronization

> measles[^196][^213]
> the prevalence of syphilis across the United States[^195]
> oscillations and synchronization[^195][^267]

[^196]:
[^213]:
[^195]:
[^267]:

### SIRS Model
After $t_I$ in **I**, recover to be **R** for $t_R$ steps, and turn into **S** again

> small-world properties to synchronization[^411][^267]

[^411]:

> syphilis and gonorrhea[^195]
> out-of-phase synchronization[^196]
> more rule to explain such properties[^213]

## 21.6 Transient Contacts and the Dangers of Concurrency
- HIV/AIDS
- progresses over many years
- very few contacts at any single point in time

> sociology[^182][^305][^258]
> epidemiology[^307][^406]
> mathematics[^106]
> computer science[^53][^239]

### Concurrency
- overlap of time interval

> average number and duration of partnerships matters[^307]

[^182]:
[^305]:
[^258]:
[^307]:
[^406]:
[^106]:
[^53]:
[^239]:
## 21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve

> Mitochondrial Eve[^94]

- Wright–Fisher model
- each node in generation $g$, uniformly connect with a node in generation $g-1$


[^94]:

## 21.8 Advanced Material: Analysis of Branching and Coalescent Processes
### A. Analysis of Branching Processes
- *basic reproductive number* $R_0=pk$
- $q_n$: Probability that the epidemic survives for at least $n$ waves
- $q^∗$: limit of $q_n$ as $n$ goes to infinity
- Claim: (a) If $R_0 < 1$ then $q^∗ = 0$. (b) If $R_0 > 1$ then $q^∗ > 0$.
#### The Expected Number of Infected Individuals
- The number of individuals at level $n$ is $k^n$
- Let $X_n$ be a random variable equal to the number of infected individuals at level $n$.
- $X_n = Y_{n1} + Y_{n2} + · · · + Y_{nm}$
- For each individual $j$ at level $n$, $Y_{nj}$ equals to $1$ if $j$ is infected, and equals to $0$ otherwise.
- $m = k^n$
- $E[X_n]= E [Y_{n1}] + E [Y_{n2}] + · · · + E [Y_{nm}]$
- $E[Y_{nj}] = 1 × Pr [Y_{nj} = 1] + 0 × Pr [Y_{nj} = 0] =Pr [Y_{nj} = 1]$
- Individual $j$ at depth $n$ is infected with probability $p^n$ $\Rightarrow E[Y_{nj}] = p^n$
- 
- Therefore, $E[X_n]= p^nk^n = (pk)^n = {R_0}^n.$
#### From Expected Values to Probabilities of Persistence
- Proof of (a) If $R_0 < 1$ then $q^∗ = 0$
- $E [X_n] = 1 × Pr [X_n = 1] + 2 × Pr [X_n = 2] + 3 × Pr [X_n = 3] + · · ·$$=Pr [X_n ≥ 1] + Pr [X_n ≥ 2] + Pr [X_n ≥ 3] + · · ·$$\Rightarrow E [X_n] ≥ Pr [X_n ≥ 1]=q_n$
- $E [X_n] = {R_0}^n$, which is converging to $0$ as n grows
- Hence, $q_n$ must also be converging to $0$.
- This shows that $q^∗ = 0$ when $R_0 < 1$.
#### A Formula for $q_n$
- $1 − q_n = (1 − pq_{n−1})^k$$\Rightarrow q_n = 1 − (1 − pq_{n−1})^k$
- $q_0 = 1$

#### Following the Values $q_n$ to a Limit
- Define $f (x) = 1 − (1 −px)^k \Rightarrow q_n = f (q_{n−1})$
- sequence of values $1, f (1), f (f (1)), . . .$ = sequence $q_0, q_1, q_2, . . .$
- plot function $f$
- $f (0) = 0$ and $f (1) = 1 − (1 − p)k < 1$.
- $f^{'} (x) = pk(1 − px)k$<br> $f^{'} (x)$ is positive but monotonically decreasing as $x$ ranges between $0$ and $1$.
- $f^{'}(0) = pk = R_0$.<br>When $R_0 > 1$, $f$ starts out above $y = x$.
- Thus, $y = f (x)$ must cross $y = x$ somewhere in the interval between $0$ and $1$, at a point $x^∗ > 0$.
- 
- When $R_0 > 1$, the probability that the epidemic persists for $n$ levels converges to a positive value as $n$ goes to infinity.
- 
- 

### B. Analysis of Coalescent Processes
- Focus on a small sample of $k$ individuals in a large population of size $N$.
- Consider the time until the lineages of these $k$ individuals merge into a common ancestor.
- Example
- $N=27$
- $k=6$
- 
#### The Probability That Lineages Collide in One Step.
- We have a set of $j$ distinct lineages
- Estimate the probability of colliding
- Compute the probability that no two lineages collide = $(1 − \frac1N)(1 − \frac2N)(1 − \frac3N)\cdot \cdot \cdot (1 − \frac{j-1}N)$$=1 − (\frac{1 + 2 + 3 + · · · + j − 1}{N}) +\frac{g(j)}{N^2}$$\approx 1 − (\frac{1 + 2 + 3 + · · · + j − 1}{N})$$=1 −\frac{j(j − 1)}{2N}$
- If two lineages collide
- Collision between two of the lineages
- More than two lineages collide in a single generation
- A collision among three lineages
- For a set of 3 lineages, the probability this happens is $\frac{1}{N^2}$
- Since there are fewer than $j^3$ sets of three lineages, the probability $\lt \frac{j^3}{N^2}$.
- Two different pairs of lineages each have a separate, two-way collision
- Suppose that $A$ collides with $B$, and $C$ collides with $D$
- Both of the probability of two collision events is $\frac1N$
- For this particular choice of four lineages, both collisions happen with probability $\frac{1}{N^2}$
- Since there are fewer than $j^4$ ways of choosing $A, B, C,$ and $D$, the probability $< \frac{j^4}{N^2}$

#### The Expected Time Until Coalescence.
- Approx. view of the process
- Starting with $k$ distinct lineages.
- In each generation, probability of colliding $= \frac{k(k−1)}{2N}$.
- Once a collision happens, we have $k − 1$ distinct lineages.
- Repeat until $k$ becomes $1$
- Example of $k=6$
- 
- $X = X_k + X_{k−1} + X_{k−2} + · · · + X_2$
- $X_j$: Beginning with $j$ lineages, the number of steps until this number of lineages is reduced to $j − 1$
- $E[X] = E [X_k] + E [X_{k−1}] + · · · + E [X_2]$
- $E[X_j] = Pr[X_j≥ 1] + Pr [X_j ≥ 2] + Pr [X_j ≥ 3] + · · ·$$=1 + (1 − p) + {(1 − p)}^2 + {(1 − p)}^3 + · · ·$$=\frac{1}{1 − (1 − p)} = \frac1p$$=\frac{2N}{j(j − 1)}$
- $E[X]=\frac{2N}{2\times 1}+\frac{2N}{3\times 2}+\frac{2N}{4\times 3}+\cdot \cdot \cdot+\frac{2N}{k(k-1)}$$=2N[ \frac{1}{2\times 1}+\frac{1}{3\times 2}+\frac{1}{4\times 3}+\cdot \cdot \cdot+\frac{1}{k(k-1)}]$$=2N[(\frac11-\frac12)+(\frac12-\frac13)+\cdot \cdot \cdot+(\frac{1}{k-1}-\frac1k)]$$=2N(1-\frac1k)$
- observations
- Once $k$ becomes large, the expected time to coalescence depends only very weakly on $k$; it is roughly $2N$ as $k$ grows.
- The breakdown of $X$ lets us appreciate where most of the time is being spent.