The behavior of epidemics under bounded susceptibility

Subhashini Krishnasamy, Siddhartha Banerjee, Sanjay Shakkottai

TL;DR

Standard epidemic models assume that the more infected neighbors you have, the faster you get sick—but real-world "attention spans" and bandwidth are limited. This paper proves that capping infection rates (bounded susceptibility) fundamentally flips our understanding of network vulnerability, turning influential "hubs" into bottlenecks and dramatically slowing down information spread in dense networks.

What Problem Does This Paper Address?

In classical epidemic modeling (like the SI or SIS models), a susceptible node's risk of infection scales linearly with the number of its infected neighbors. If you have 1,000 infected friends, the model assumes you are 1,000 times more likely to get sick than if you had only one.

While mathematically convenient, this is often unrealistic. In social networks, users have limited "attention spans" and only consume content from a few neighbors regardless of how many are broadcasting. In distributed computing, nodes have limited download bandwidth. The authors address this gap by introducing bounded susceptibility: a constraint where the infection rate is capped by a maximum value, regardless of the neighborhood size. They investigate how this realistic constraint changes the behavior of epidemics across different network topologies.

Methods

The authors formalize the problem by introducing an "infection-profile" function $\Phi(\cdot)$ that is concave and bounded. They then analyze two primary dynamics:

  1. $SI_{bs}$ (Susceptible-Infected): Nodes stay infected forever. The focus is on spreading time (how long to infect the whole network).
  2. $SIS_{bs}$ (Susceptible-Infected-Susceptible): Nodes can recover. The focus is on extinction time (how long until the disease dies out).

They categorize networks into two broad classes:

  • Clique-like: Dense networks with high connectivity and good expansion properties (e.g., Erdős-Rényi graphs).
  • Star-like: Sparse networks with a small, dense core and a large, sparse periphery (e.g., engineered infrastructure or hub-and-spoke models).

The analysis uses tools from stochastic processes, specifically Continuous-Time Markov Chains (CTMC), coupling arguments, and isoperimetric (Cheeger) constants to bound transition times.

Datasets

The paper relies on theoretical analysis and simulations using synthetic graph models rather than empirical datasets. The models evaluated include:

  • Complete Graphs (Cliques): $K_n$.
  • Star Graphs: A single hub with $n-1$ leaves.
  • Erdős-Rényi Graphs: $G(n, p)$ in the connected regime.
  • Power-law Graphs: Generated via the Chung-Lu model to represent scale-free social networks.

Key Insights and Ideas

  • The Hub Paradox: In standard SIS models, high-degree "hubs" are the engines of persistence, keeping the infection alive. Under bounded susceptibility, these hubs become bottlenecks. Because their infection rate is capped, they cannot "keep up" with the recovery rate of their many neighbors, leading to much faster extinction in star-like networks.
  • Topological Sensitivity: The impact of the bound is "reversed" between the two models.
  • For SI dynamics, dense clique-like networks are highly sensitive (spreading slows down significantly), while star-like networks are unaffected.
  • For SIS dynamics, clique-like networks are robust (infection remains persistent), while star-like networks exhibit a sharp transition from exponential to polynomial extinction times.
  • Persistence in Scale-Free Networks: Interestingly, power-law networks still experience long-lasting SIS epidemics under bounded susceptibility. This isn't because of the hubs, but because these networks naturally contain large, dense "clique-like" subgraphs that can sustain the infection locally.

Key Results

  • SI Spreading Time: In a clique, the expected spreading time switches from vanishingly small ($O(\frac{\log n}{n})$) to scaling with the network size ($\Omega(\log n)$) once susceptibility is bounded. This dramatic shift is illustrated in Figure 1.
Figure 1: Spreading time in a clique. Under standard SI, spreading time vanishes as $n$ grows; under bounded susceptibility ($SI_{bs}$), it increases logarithmically.
  • SIS Extinction Time: In star networks, the extinction time drops from being exponentially large to being merely polynomial (sub-exponential) in $n$. Figure 2 shows this transition, where the $SIS_{bs}$ curve becomes linear on a log-log plot, indicating polynomial scaling.
Figure 2: Extinction time in a star network. Bounded susceptibility ($SIS_{bs}$) causes a sharp drop from exponential to polynomial duration.
  • Quarantine Policy: The results suggest that "partial quarantine" (reducing but not eliminating susceptibility) is highly effective in star-like networks (like air transportation hubs) but almost useless in dense, clique-like networks (like local social circles).

Limitations and Future Work

  • Graph Classification: The authors acknowledge that their "clique-like" vs. "star-like" dichotomy is not exhaustive; many real-world networks are complex mixtures that may fall into a "gap" between these two behaviors.
  • Model Scope: The study focuses on SI and SIS models. The authors suggest that extending these techniques to the SIR (Recovered/Immune) model would be a valuable next step.
  • Dynamic Networks: The current work assumes a static graph topology. Investigating how bounded susceptibility interacts with networks that evolve over time remains an open question.

Summary updated

Abstract

We investigate the sensitivity of epidemic behavior to a bounded susceptibility constraint -- susceptible nodes are infected by their neighbors via the regular SI/SIS dynamics, but subject to a cap on the infection rate. Such a constraint is motivated by modern social networks, wherein messages are broadcast to all neighbors, but attention spans are limited. Bounded susceptibility also arises in distributed computing applications with download bandwidth constraints, and in human epidemics under quarantine policies. Network epidemics have been extensively studied in literature; prior work characterizes the graph structures required to ensure fast spreading under the SI dynamics, and long lifetime under the SIS dynamics. In particular, these conditions turn out to be meaningful for two classes of networks of practical relevance -- dense, uniform (i.e., clique-like) graphs, and sparse, structured (i.e., star-like) graphs. We show that bounded susceptibility has a surprising impact on epidemic behavior in these graph families. For the SI dynamics, bounded susceptibility has no effect on star-like networks, but dramatically alters the spreading time in clique-like networks. In contrast, for the SIS dynamics, clique-like networks are unaffected, but star-like networks exhibit a sharp change in extinction times under bounded susceptibility. Our findings are useful for the design of disease-resistant networks and infrastructure networks. More generally, they show that results for existing epidemic models are sensitive to modeling assumptions in non-intuitive ways, and suggest caution in directly using these as guidelines for real systems.
BibTeX
@inproceedings{krishnasamy2014behavior,
  author = {Subhashini Krishnasamy and Siddhartha Banerjee and Sanjay Shakkottai},
  title = {{The behavior of epidemics under bounded susceptibility}},
  booktitle = {SIGMETRICS},
  year = {2014},
  url = {https://openreview.net/forum?id=YRgUxJ0LLo},
}

Loading related content...

Figure