Multi-scale Local Network Structure Critically Impacts Epidemic Spread and Interventions

Omar Eldaghar, Michael W. Mahoney, David F. Gleich

Abstract

Network epidemic simulation holds the promise of enabling fine-grained understanding of epidemic behavior, beyond that which is possible with coarse-grained compartmental models. Key inputs to these epidemic simulations are the networks themselves. However, empirical measurements and samples of realistic interaction networks typically display properties that are challenging to capture with popular synthetic models of networks. Our empirical results show that epidemic spread behavior is very sensitive to a subtle but ubiquitous form of multi-scale local structure that is not present in common baseline models, including (but not limited to) uniform random graph models (Erdos-Renyi), random configuration models (Chung-Lu), etc. Such structure is not necessary to reproduce very simple network statistics, such as degree distributions or triangle closing probabilities. However, we show that this multi-scale local structure impacts, critically, the behavior of more complex network properties, in particular the effect of interventions such as quarantining; and it enables epidemic spread to be halted in realistic interaction networks, even when it cannot be halted in simple synthetic models. Key insights from our analysis include how epidemics on networks with widespread multi-scale local structure are easier to mitigate, as well as characterizing which nodes are ultimately not likely to be infected. We demonstrate that this structure results from more than just local triangle structure in the network, and we illustrate processes based on homophily or social influence and random walks that suggest how this multi-scale local structure arises.

Introduction

Epidemiologists often rely on two extremes: simple "compartmental" models that assume uniform mixing, or synthetic network models (like Erdős–Rényi) that lack the hierarchical clustering found in real-world interactions. This paper identifies a critical gap: real-world interaction networks possess "bottlenecks" at many different scales. Because standard models miss this multi-scale local structure, they often overestimate the difficulty of stopping a virus. This research investigates how these structural bottlenecks impact the success of interventions and why real networks behave differently from common simulations.

Methods

The researchers combined network science with epidemic simulation across 15 diverse datasets, including human mobility (Mexico City, US commuting), social networks (Facebook, email), and online platforms (Slashdot, Flickr).

Key techniques included:

  • SEIR Simulations with Local Quarantine: A discrete-time model where detected cases trigger a "local quarantine" of the infected node and its immediate neighbors.
  • Network Rewiring: Real networks were "rewired" by randomly swapping edges to destroy local structure while preserving basic statistics like degree distribution.
  • Network Community Profile (NCP): This tool measures conductance—a metric of how "trapped" a process like a virus stays within a cluster—across all size scales.
  • AANCP (Area Above the NCP): A new metric introduced to quantify the diversity of local structure in a network.
Multi-scale local structure and the Network Community Profile (NCP) metric.

Key Insights: The "Firebreak" Effect

The study reveals that multi-scale structure acts like a series of natural firebreaks. Local quarantines exploit these existing bottlenecks to snuff out outbreaks before they jump between communities.

Contrary to standard theory, where "stronger" epidemics (higher $\lambda_1$) are harder to stop, real networks often have higher $\lambda_1$ but are much easier to control because the virus gets "stuck" in local clusters. This effect goes beyond simple "clustering" (triangles); even when triangles were randomized, the epidemic behavior changed significantly, proving the structure is more complex and multi-scale. Groups with low conductance (tightly knit communities with few outside links) are naturally protected, as the virus struggles to enter or exit these clusters.

Results

The effectiveness of interventions is highly sensitive to network topology. The new AANCP metric showed a strong positive correlation (Spearman $\rho = 0.78$) with quarantine impact, whereas traditional metrics like average degree or $\lambda_1$ showed little correlation with how effective an intervention would be.

Impact of network rewiring and quarantine interventions on epidemic spread.

In the Mexico City network, a small quarantine budget could almost entirely halt an epidemic. However, as the network was rewired toward a random model, the fraction of infected nodes spiked dramatically, even with the same quarantine budget. Furthermore, the study demonstrated that nodes in low-conductance sets are significantly less likely to be infected, providing a structural explanation for community-level resilience.

Discussion and Limitations

While these findings suggest that epidemics are more controllable in realistic networks than previously thought, several limitations remain. The model assumes 100% adherence to quarantine, ignoring network-mediated behavioral influences. Additionally, high-quality, fine-grained human mobility data remains scarce.

Future policy choices should be grounded in models that explicitly account for structural bottlenecks. Further research is also needed to understand how misinformation might spread over these same structures, potentially undermining the very interventions they facilitate.

Summary updated

Abstract

Network epidemic simulation holds the promise of enabling fine-grained understanding of epidemic behavior, beyond that which is possible with coarse-grained compartmental models. Key inputs to these epidemic simulations are the networks themselves. However, empirical measurements and samples of realistic interaction networks typically display properties that are challenging to capture with popular synthetic models of networks. Our empirical results show that epidemic spread behavior is very sensitive to a subtle but ubiquitous form of multi-scale local structure that is not present in common baseline models, including (but not limited to) uniform random graph models (Erdos-Renyi), random configuration models (Chung-Lu), etc. Such structure is not necessary to reproduce very simple network statistics, such as degree distributions or triangle closing probabilities. However, we show that this multi-scale local structure impacts, critically, the behavior of more complex network properties, in particular the effect of interventions such as quarantining; and it enables epidemic spread to be halted in realistic interaction networks, even when it cannot be halted in simple synthetic models. Key insights from our analysis include how epidemics on networks with widespread multi-scale local structure are easier to mitigate, as well as characterizing which nodes are ultimately not likely to be infected. We demonstrate that this structure results from more than just local triangle structure in the network, and we illustrate processes based on homophily or social influence and random walks that suggest how this multi-scale local structure arises.
BibTeX
@misc{eldaghar2023multi,
  author = {Omar Eldaghar and Michael W. Mahoney and David F. Gleich},
  title = {{Multi-scale Local Network Structure Critically Impacts Epidemic Spread and Interventions}},
  year = {2023},
  eprint = {2312.17351},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.17351},
}
Figure