Targeted pandemic containment through identifying local contact network bottlenecks

Shenghao Yang, Priyabrata Senapati, Di Wang, Chris T. Bauch, Kimon Fountoulakis

TL;DR

Targeted physical distancing is essential for pandemic containment, but standard network strategies focus heavily on global "bridges" that fail to stop intra-community transmission. This paper introduces Local-Flow (LF) betweenness, an edge-centrality metric based on $p$-norm flow diffusion that isolates local transmission bottlenecks. LF betweenness reduces total COVID-19 infections by up to 10% more than state-of-the-art methods while running orders of magnitude faster.

What Problem Does This Paper Address?

Non-pharmaceutical interventions (NPIs) like social distancing, travel restrictions, and quarantines are socially and economically disruptive. Minimizing these costs requires precision: public health officials must identify and sever only the most critical transmission bottlenecks.

Classical graph theory relies on global centrality measures such as Shortest-Path (SP) and Current-Flow/Random-Walk (CF) betweenness. However, these metrics have two critical shortcomings:

  1. Global blind spots: Human interactions naturally cluster within local communities (families, workplaces, neighborhoods). Once an infection enters these clusters, cutting global bridges across distant cities does little to stop spread within or between neighboring sub-communities.
  2. Computational intractability: Calculating CF or SP betweenness on large contact networks requires $O(|V|^2)$ to $O(|V||E|)$ operations or matrix inversions, making them unusable on metropolitan- or national-scale networks.

Methods

The authors propose Local-Flow (LF) betweenness, formulated via $\ell_2$-norm ($p=2$) flow diffusion:

  • Diffusion Model: For each node $s \in V$, one unit of mass is diffused to nearby nodes. The objective minimizes total squared flow $\sum_{(u,v)} f(u,v)^2$ subject to conservation constraints where sink capacities are capped at $T(u) = \frac{d(u)}{\lambda \cdot \text{vol}(G)}$.
  • Locality Parameter ($\lambda \in (0, 1]$): Parameter $\lambda$ acts as a zoom lens. When $\lambda \to 1$, LF betweenness recovers global Current-Flow betweenness. When $\lambda$ is small (e.g., $1/10$ or $1/50$), mass settles rapidly near the source node, prioritizing local community cuts.
  • Dual Optimization: The dual problem is solved using randomized coordinate descent. On sparse networks with small $\lambda$, computation per node is bounded, reducing total runtime to nearly linear time $O(|V| \log(1/\epsilon))$.
  • Epidemiological Modeling: Performance is evaluated across two SEIR models:
  • Population-based ODE SEIR (nodes = geographic areas; edges = inter-region mobility).
  • Agent-based discrete-time SEIR (nodes = individuals; edges = physical co-location). Interventions reduce targeted edge weights (transmission probabilities) by 90% or 99%.
   Low λ (Local focus)                High λ (Global focus)
[Cluster A] -- local edge -- [A']    [Cluster A] === bridge === [Cluster B]
      ↓                                    ↓
Captures tightly-knit sub-clusters    Recovers standard Current-Flow (CF)

Datasets

The authors evaluated LF betweenness on three empirical contact networks with distinct Network Community Profiles (NCP):

  1. Facebook County Network: 3,142 US counties and 22,138 edges reflecting geographic proximity ($<500$ miles) and Facebook social connectedness (downward-sloping NCP).
  2. Wi-Fi Hotspots Montreal: 103,425 individuals and 630,893 edges capturing concurrent public Wi-Fi usage; dominated by low-degree nodes (flat NCP).
  3. Portland, Oregon Synthetic Network: Colocation network derived from census and activity diaries. Tested on both a sub-sampled graph (10,000 nodes, 199,168 edges) and the full graph (1.6 million nodes, 31 million edges; upward-sloping NCP).

Key Insights and Ideas

  • Local Clustering Bias Prevents Seeding: On the Facebook network, targeting the top 5% of edges selected by LF captured 100% of out-link cut edges surrounding an initially infected cluster, effectively boxing in the outbreak without prior knowledge of the seed location.
  • Exploiting Degree Irregularities: In networks with many low-degree nodes (such as the Montreal dataset), LF betweenness strategically isolated low-degree individuals, shutting down peripheral transmission chains far more efficiently than SP betweenness.
  • Unified Framework: Theoretical analysis proves that global CF betweenness is simply a special case of general $\ell_2$-flow betweenness when source and sink distributions are chosen uniformly.

Key Results

  • Higher Infection Reduction: Across datasets, targeting edges with high LF betweenness cut final epidemic sizes by up to 10% more than SP or CF betweenness, consistently achieving lower and delayed epidemic peaks.
  • Extreme Computational Speedups:
  • On the Montreal network, SP betweenness took over 4 days to compute, and CF was computationally infeasible. LF betweenness ($\lambda = 1/50$) completed in under 10 minutes.
  • LF was the only betweenness measure capable of scaling to the full 1.6-million-node Portland graph.
  • Broad Robustness: Outperformance held true under alternate reproduction numbers ($R_0$ parameterized for 55%, 70%, and 85% final attack rates), when interventions were deployed mid-outbreak, under 99% transmission cuts, and when adapted for node immunization.

Limitations and Future Work

  • Parameter Tuning: The optimal $\lambda$ depends on graph topology and epidemic parameters; determining the best $\lambda$ currently requires parameter sweeps or grid search on sub-sampled networks.
  • Static Interventions: The study focuses on static, one-shot contact reductions. Integrating LF betweenness into dynamic policies (e.g., rolling local lockdowns guided by digital contact tracing) remains open.
  • Proxy Limitations: Co-location and social media proxies omit certain transmission pathways, such as long-haul cargo transport or populations without digital footprints.

Summary updated

Abstract

Author summary During the COVID-19 pandemic decision makers frequently face questions like where to impose a lockdown, which traffic to close, and whom to quarantine, all required to be carried out at minimal costs. Establishing cost-effective pandemic control policies requires identifying good targets. New computational models from network theory and epidemic simulations over real contact networks provide a valuable tool for finding the right bottlenecks to target upon. Here we study a computationally efficient network centrality measure that enables us to detect local transmission bottlenecks, i.e., contact edges that are especially important for the spread of disease among small communities or local network structures inside large networks. We find that pandemic intervention strategies that target at local network structures significantly outperform interventions that solely focus on the entire network structure as a whole, which are traditionally believed to be the most effective.
BibTeX
@article{yang2021targeted,
  author = {Shenghao Yang and Priyabrata Senapati and Di Wang and Chris T. Bauch and Kimon Fountoulakis},
  title = {{Targeted pandemic containment through identifying local contact network bottlenecks}},
  journal = {PLOS Computational Biology},
  year = {2021},
  url = {https://openreview.net/forum?id=rKL-E_fTJbq},
}

Loading related content...

Figure