Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks

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

Abstract

Decision-making about pandemic mitigation often relies upon simulation modelling. Models of disease transmission through networks of contacts—between individuals or between population centres—are increasingly used for these purposes. Real-world contact networks are rich in structural features that influence infection transmission, such as tightly-knit local communities that are weakly connected to one another. In this paper, we propose a new flow-based edge-betweenness centrality method for detecting bottleneck edges that connect nodes in contact networks. In particular, we utilize convex optimization formulations based on the idea of diffusion with p-norm network flow. Using simulation models of COVID-19 transmission through real network data at both individual and county levels, we demonstrate that targeting bottleneck edges identified by the proposed method reduces the number of infected cases by up to 10% more than state-of-the-art edge-betweenness methods. Furthermore, the proposed method is orders of magnitude faster than existing methods.

Introduction: The Challenge of Targeted Containment

During a pandemic, effective mitigation requires identifying and severing the most critical connections in a contact network to maximize the reduction in disease spread with minimal disruption. Traditional approaches rely on global centrality measures like Shortest-Path (SP) betweenness or Current-Flow (CF) betweenness. However, these methods often fail to account for the "local" nature of human interactions, where individuals spend most of their time in small, tightly-knit clusters like families or workplaces. Global measures can overlook local bottlenecks that facilitate the "leakage" of infection from one community to another. Moreover, these traditional methods are computationally expensive, hindering their application to large-scale, real-world datasets.

Methods: Local-Flow (LF) Betweenness

To address these limitations, we introduce Local-Flow (LF) betweenness, a novel centrality measure grounded in $p$-norm flow diffusion. The core concept involves simulating the "diffusion" of a substance from a source node and measuring the resulting flow through specific edges.

Figure 1: Illustration of different edge targeting strategies on a modular network. Panel A shows a global bridge, while other panels highlight more localized bottlenecks.

A key innovation is the locality parameter ($\lambda$), which controls the spread of diffusion. A smaller $\lambda$ focuses the algorithm on identifying local bottlenecks, while a larger $\lambda$ approximates global behavior. By framing this as a convex optimization task, we can utilize efficient algorithms like randomized coordinate descent, enabling the processing of massive networks in minutes.

Datasets

The method was validated across three diverse network types:

  1. Facebook County Network: Inter-county social and physical interaction in the US.
  2. Wi-Fi Hotspots Montreal: Urban physical proximity proxy with over 100,000 nodes.
  3. Portland Synthetic Network: A high-fidelity model of 1.6 million individuals based on census data.

Key Results and Insights

The primary insight of this work is that local bottlenecks are more effective targets than global bridges. By isolating small clusters, we prevent the "seeding" of new outbreaks in neighboring communities. LF betweenness is particularly adept at identifying edges that, when removed, create "singletons"—isolated individuals who can no longer transmit the virus.

Performance and Efficiency

In simulations of COVID-19 transmission, LF betweenness consistently outperformed state-of-the-art methods. As shown in Figure 6, targeting edges identified by LF variants (with different $\lambda$ values) leads to a more significant reduction in the epidemic peak compared to Shortest-Path (SP) or Current-Flow (CF) betweenness.

Figure 6: Comparison of epidemic peak reduction across different edge-removal strategies. LF methods consistently achieve lower peaks than traditional SP and CF methods as the percentage of targeted edges increases.

Beyond containment efficacy, the LF method offers massive computational speedups. For instance, on the Montreal Wi-Fi network, calculating SP betweenness required four days, whereas the LF method completed the task in under ten minutes.

Conclusion and Future Directions

Targeted containment using local-flow betweenness provides a faster and more effective way to mitigate pandemic spread by focusing on the structural bottlenecks of human contact networks. While the current study demonstrates the power of this approach on static networks, future work will explore extending LF betweenness to dynamic, time-varying networks. Additionally, refining the selection of the optimal locality parameter $\lambda$ for different network topologies remains an area for further investigation.

Summary updated

Abstract

Decision-making about pandemic mitigation often relies upon simulation modelling. Models of disease transmission through networks of contacts--between individuals or between population centres--are increasingly used for these purposes. Real-world contact networks are rich in structural features that influence infection transmission, such as tightly-knit local communities that are weakly connected to one another. In this paper, we propose a new flow-based edge-betweenness centrality method for detecting bottleneck edges that connect nodes in contact networks. In particular, we utilize convex optimization formulations based on the idea of diffusion with p-norm network flow. Using simulation models of COVID-19 transmission through real network data at both individual and county levels, we demonstrate that targeting bottleneck edges identified by the proposed method reduces the number of infected cases by up to 10% more than state-of-the-art edge-betweenness methods. Furthermore, the proposed method is orders of magnitude faster than existing methods.
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},
}
Figure