Network Propagation

Disease, information, behavior, and opinion propagate through social Networks.

Susceptible-Infected (SI)

We abstract the propagation model as a infection process, though it applies beyond epidemiology. A node can be in one of the two states:

• Susceptible: does not have the disease yet, but could catch it if it comes into contact with an infected node.
• infected: has the disease and can potentially pass it on if it comes into contact with a susceptible node.

Typical questions of interest

• Under what conditions will an initial outbreak spread to a nontrivial portion of the population?
• What percentage of the population will eventually become infected?
• What is the effect of immunization policies?

Fully Mixed

Suppose first there is no contact network (or the network is complete). We use such fully mixed models as baselines. Let $x(t)$ denote the fraction of infected nodes at time $t$ and $\beta$ be the infection rate. Then the dynamics are given by

$$x(t+1)=x(t)+\beta \underset{\text{encounter frequency}}{\underbrace{x(t)(1-x(t))}}.$$

The derivative is $\beta x(1-x)\ge 0$, which has two stationary points: $x=0$ and $x=1$; the former is unstable while the latter is stable. More accurately, we can solve the difference equation to get $x(t)=\frac{x(0)\exp (\beta t)}{1-x(0)+x(0)\exp (\beta t)}$, which gives an S-shaped curve.

Incorporating spontaneous infections with rate $\alpha$ gives the Bass model, modeled by the following difference equation:

$$x(t+1)=x(t)+\alpha (1-x(t))+\beta x(t)(1-x(t)).$$

The solution to the corresponding differential equation is $x(t)=\frac{1-\exp (-(\alpha +\beta )t)}{1+\frac{\beta }{\alpha }\exp (-(\alpha +\beta )t)}$. When $\alpha <\beta$, we again get an S-shaped curve; when $\alpha \ge \beta$, the curve is more concave.

Volume

Now suppose there is a contact network but $\beta =1$. Then a node will infect its component. For a sparse ER model $\mathrm{ER}(n,\lambda /n)$, if $\lambda <1$, then there is no giant component, so the disease dies out (number of infected nodes is $o(n)$). If $\lambda >1$, we know the unique giant component is of size $(1-\eta (\lambda ))n$, where $\eta$ satisfying $\eta =\exp (\lambda (\eta -1))$ is the extinction probability of a Branching process with $\mathrm{Poisson}(\lambda )$ offspring distribution. Then, with probability $\eta$, the node is in a small component and the disease dies out; with probability $1-\eta$, the disease spreads to a nontrivial portion of the population $(1-\eta )n$.

We can also incorporate immunization. Suppose the probability of node not being immune is $\phi$. For a Configuration Model with degree distribution $(p_d{)}_{d\in \mathbb{N}}$, again, by the local branching approximation, we know the expected number of infected offsprings of a node is $\phi ⟨\tilde{d}⟩$, where $⟨\tilde{d}⟩=\frac{⟨d^2⟩-⟨d⟩}{⟨d⟩}$ is the mean excess degree. Let ${\phi }_c:=\frac{⟨d⟩}{⟨d^2⟩-⟨d⟩}$. Then, the contagion spread with a positive probability if $\phi >{\phi }_c$ and dies out with probability 1 if $\phi <{\phi }_c$.

Rate

With a general infection rate $\beta \le 1$, let $x(t)=(x_1(t),\dots ,x_n(t))$ denote the infection status (probability of being infected) of all nodes. Then the propagation dynamics are given by

$$x_i(t+1)=x_i(t)+\beta (1-x_i(t))\left(1-\prod _{j\in N_i}(1-\beta x_j(t))\right)$$

When $\beta \ll 1$, we have the approximation ${\prod }_{j\in N_i}(1-\beta x_j(t))\approx 1-\beta {\sum }_{j\in N_i}{x}_j(t)$. Let $A$ be the adjacency matrix of the contact network. Then, we have

$$x(t+1)=x(t)+\beta (I-\mathrm{diag}(x(t)))Ax(t).$$

Consider only the first-order term, we have

$$x(t+1)=(I+\beta A)x(t)\to ⟨x(0),v_1⟩(I+\beta {\lambda }_1{)}^t{v}_1,$$

where ${\lambda }_1$ and $v_1$ are the largest eigenvalue and its corresponding eigenvector of $A$, respectively.¹ The propagation is dominated by the eigenvector centrality.

Susceptible-Infected-Recovered (SIR)

Consider an additional state:

• Recovered: recovered from the disease, immunized, and can’t pass it on anymore if it comes into contact with a susceptible node.

Fully Mixed

Let $s(t)$, $x(t)$, and $r(t)$ denote the fraction of susceptible, infected, and recovered nodes at time $t$, respectively. Let $\gamma$ be the recovery rate. Then the fully mixed continuous dynamics are

$$\begin{array}{rl}\dot{s}(t)& =-\beta s(t)x(t),\\ \dot{x}(t)& =\beta s(t)x(t)-\gamma x(t),\\ \dot{r}(t)& =\gamma x(t),\\ r(0)& =0,s(t)+x(t)+r(t)=1.\end{array}$$

The first and third condition give $s(t)=s(0)\exp (-\frac{\beta }{\gamma }r(t))$. Together with $x(t)=1-s(t)-r(t)$, we get

$$\dot{r}(t)=\gamma \left(1-s(0)\exp \left(-\frac{\beta }{\gamma }r(t)\right)-r(t)\right).$$

When $s(0)=1$, the stationary point of $r$ satisfies $r=1-\exp (-\frac{\beta }{\gamma }r)$. When $\beta \le \gamma$, the unique stationary point is $r=0$, i.e., infected nodes recover faster than susceptible nodes get infected, so the disease dies out; when $\beta >\gamma$, there is another nontrivial stationary point $r>0$, i.e., the disease spreads to a nontrivial portion of the population. $\beta =\gamma$ is called the epidemic threshold/transition.

Networked

Start with one infected node. Each node, once infected, stays infected for $\tau$ units of time, and then recovers. For each $\mathrm{d}t$ unit of time, an infected node infects each of its susceptible neighbors with probability $\beta \mathrm{d}t+o(\mathrm{d}t)$. Suppose node $i$ gets infected from node $i_0$. Let $T_i$ be the time of infection of $i$ after $i_0$ gets infected. Then, we know $T_i\stackrel{d}{\sim }\mathrm{Exp}(\beta )$ (see Exponential Distribution and Poisson Distribution). Thus,

$$P(i_0\text{ infects }i)=P(T_i<\tau )=1-\exp (-\beta \tau ).$$

Let $\varphi :=1-\exp (-\beta \tau )$. We get a Branching process with rate $\varphi$.

Susceptible-Infected-Susceptible (SIS)

Consider a recovered node, instead of being removed, can be infected again.

Fully Mixed

Let $x(t)$ denote the fraction of infected nodes at time $t$. Then, the fully mixed continuous dynamics are

$$\dot{x}(t)=\beta x(t)(1-x(t))-\gamma x(t),$$

whose solution is $x(t)=\frac{(\beta -\gamma )x(0)\exp ((\beta -\gamma )t)}{\beta -\gamma -\beta x(0)+\beta x(0)\exp ((\beta -\gamma )t)}$. When $\beta >\gamma$, the steady state is $x=1-\frac{\gamma }{\beta }$, referred to as the endemic disease state.

Networked

Similarly, for a infimum $\mathrm{d}t$ unit of time, an infected node recovers (but not immunized) with probability $\gamma \mathrm{d}t+o(\mathrm{d}t)$, and a susceptible node gets infected with probability $\beta k\mathrm{d}t+o(\mathrm{d}t)$, where $k$ is the number of infected neighbors. The resulting system is a giant Markov Chain with a state space $\{0,1{\}}^n$.

Susceptible-Infected-Recovered-Susceptible (SIRS)

Consider not all recovered nodes are immunized or can be infected again. Let $\delta$ be the rate of losing immunity and becoming susceptible again. Again, let $s(t)$, $x(t)$, and $r(t)$ denote the fraction of susceptible, infected, and recovered nodes at time $t$, respectively. Then, the fully mixed continuous dynamics are

$$\begin{array}{rl}\dot{s}(t)& =\delta r(t)-\beta s(t)x(t),\\ \dot{x}(t)& =\beta s(t)x(t)-\gamma x(t),\\ \dot{r}(t)& =\gamma x(t)-\delta r(t),\\ r(0)& =0,s(t)+x(t)+r(t)=1.\end{array}$$

Voter Model

Consider a binary opinion $\{-1,1\}$ held by each agent on a network. Agent $i$ switches its opinion after time $\mathrm{d}t$ with probability

$$\mathrm{d}t\cdot \underset{\text{adoption rate}}{\underbrace{\beta }}\cdot \underset{\#\text{neighbors with different opinion}}{\underbrace{N_i^{(-x_i(t))}(t+\mathrm{d}t)}}\cdot d_i^{-1}.$$

Equivalently, each agent has a “Poisson clock” $T_i\sim \mathrm{Exp}(\beta )$ such that it switches its opinion to a randomly chosen neighbor’s opinion at time $T_i$. Suppose $x_i(0)=-1$; then

$$\begin{array}{rl}P(x_i(\mathrm{d}t)=& 1\mid x_i(0)=-1)=P(T_i\le \mathrm{d}t)N_i^{(1)}(\mathrm{d}t)/d_i\\ =& (1-e^{-\beta \mathrm{d}t})N_i^{(1)}(\mathrm{d}t)\approx \beta N_i^{(1)}(\mathrm{d}t)/d_i\mathrm{d}t.\end{array}$$

Interestingly, the opinion goes through a reverse Random Walk: when the process runs for a while, an agent must get its final opinion from some neighbor, who in turn gets that opinion from some neighbor, and so on. When two random walks meet, they coalesce and move together (an agent persuades two neighbors). Then, if a consensus is reached, all random walks must start from a set of nodes holding the same opinion initially. For a connected graph, if the time is sufficiently long, all random walks will coalesce into one, and the “source” of the final opinion is distributed according to the stationary distribution, i.e., $d_i/(2m)$. The probability of reaching a consensus $+1$ or $-1$ can be calculated accordingly.

Footnotes

1. If $A$ is primitive (the graph is strongly connected and aperiodic), then by Perron-Frobenius theorem, ${\lambda }_1$ is real, positive, strictly larger than the magnitude of any other eigenvalue, and $v_1$ is element-wise positive. ↩