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.
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:
- Facebook County Network: Inter-county social and physical interaction in the US.
- Wi-Fi Hotspots Montreal: Urban physical proximity proxy with over 100,000 nodes.
- 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.
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