Dataset accompanying Multiscale-Local Structure Preprint - Part 1 of 2

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

In the early days of a pandemic, modelers scramble to predict how fast a virus will spread and how much effort is needed to stop it. Traditionally, they look at things like the "average number of contacts" or the "dominant eigenvalue" of a network. But according to a new paper by Omar Eldaghar, Michael W. Mahoney, and David F. Gleich, these standard metrics might be leading us to overestimate the "unstoppability" of an epidemic.

The secret lies in a subtle, ubiquitous feature of real-world interaction networks: multi-scale local structure.

TL;DR

Standard epidemic models often fail because they use synthetic networks that lack the "bottlenecks" found in real-world human interactions. By measuring "Area Above the NCP" (AANCP), the authors show that real networks have a multi-scale structure that makes local interventions, like quarantining, far more effective than traditional theory predicts.

What Problem Does This Paper Address?

Most network science relies on "random" models (like Erdős–Rényi or Configuration Models) to simulate epidemics. These models are great at matching a network's degree distribution (how many friends people have), but they are terrible at matching how people actually cluster.

In real life, you don't just have 10 friends; you have a family of 4, a work pod of 5, and a hobby group of 8. These small groups form larger "meso-scale" communities. This creates a "multi-scale" architecture full of structural bottlenecks. Standard models "smear out" these clusters, creating a "well-mixed" soup where a virus can jump anywhere instantly. This paper addresses the gap between these overly simplistic models and the complex, bottleneck-heavy reality of empirical interaction data.

Methods

The authors employ several sophisticated tools to probe this structure:

  • Epidemic NCP (Network Community Profile): They use the concept of conductance—the ratio of edges leaving a group to the total edges within it. By plotting conductance against the size of the group, they create a "profile" of the network's bottlenecks.
  • AANCP (Area Above the NCP): A novel quantitative measure introduced to calculate the "diversity" of these bottlenecks across all scales.
  • Rewiring Experiments: To prove their point, the authors took real networks and "rewired" them—randomly swapping edges to destroy local structure while keeping the degree distribution the same. They then compared how an SEIR (Susceptible-Exposed-Infectious-Recovered) model performed on the original vs. the rewired versions.
  • Generative Modeling: They developed two new synthetic models, GeometricCommunities and RandomWalkCommunities, which successfully replicate the multi-scale bottlenecks found in real data.

Datasets

The study is grounded in a diverse array of 15 empirical and synthetic networks:

  • Human Mobility: US Commuting data, Mexico City contact traces, and US cellular mobility flows.
  • Social Interactions: Sparsified Facebook friendship networks from colleges (UIUC, Penn, Wisconsin), Email-Enron, and Collaboration networks.
  • Information Networks: Citation graphs, Slashdot, and Flickr.
  • Synthetic Benchmarks: Purely geometric graphs and the authors' own multi-scale generative models.

Key Insights and Ideas

  • The Eigenvalue Paradox: In standard theory, a higher "dominant eigenvalue" ($\lambda_1$) means a more explosive epidemic. However, the authors found that real-world networks often have higher $\lambda_1$ than their random counterparts, yet they are easier to control. As they put it: $\lambda_1$ measures how easy a material is to ignite, not how hard it is to extinguish.
  • Bottlenecks as Firewalls: Low-conductance sets (tight-knit communities with few outside links) act as natural barriers. If an intervention can "plug" the few exit points of a small community, the virus gets trapped.
  • Triangles Aren't Enough: You might think "local structure" just means "lots of triangles" (friends of friends being friends). The authors used hypergraph models to show that even if you preserve the number of triangles but shuffle their locations, the network becomes harder to control. The structure is deeper than just 3-node cliques; it's about how those cliques are nested.

Key Results

  • Quarantine Success: In the Mexico City network, a small amount of local quarantine could halt an epidemic. Once that same network was rewired to be "random," even massive quarantine efforts failed to stop the spread.
  • Predictive Power of AANCP: The new AANCP metric showed a strong positive correlation (0.78) with the effectiveness of quarantine. Traditional metrics like average degree or $\lambda_1$ showed little to no correlation.
  • The "U-Shape" of Infections: When plotting total infections against "Rewiring Percent," the authors found a distinct U-shape. The original empirical network (at the center) always had the lowest infection rate under intervention compared to the "randomized" versions on either side.

Limitations and Future Work

The authors acknowledge a few key hurdles for real-world application:

  • Adherence: The model assumes 100% adherence to quarantine, which we know from COVID-19 is rarely the case. Future work could model how "information epidemics" (misinformation) affect quarantine adherence.
  • Data Sparsity: Real-world contact data is often "noisy." The authors had to "sparsify" some social networks to reveal the underlying structural bottlenecks, suggesting that our raw data collection methods might need refinement.
  • Dynamic Networks: The study uses static snapshots. In reality, networks change as people react to a disease, a layer of complexity yet to be fully integrated with multi-scale analysis.

Final Thought: This research suggests that our social "bubbles" aren't just a sociological phenomenon—they are a critical structural defense. By understanding the multi-scale bottlenecks of human interaction, we can design interventions that work with the grain of society, rather than against it.

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{eldaghar2023dataset,
  author = {Omar Eldaghar and Michael W. Mahoney and David F. Gleich},
  title = {{Dataset accompanying Multiscale-Local Structure Preprint - Part 1 of 2}},
  year = {2023},
  eprint = {2312.17351},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.17351},
}
Figure