Static graph approximations of dynamic contact networks for epidemic forecasting

Razieh Shirzadkhani, Shenyang Huang, Abby Leung, Reihaneh RabbanyScientific 2024 · DOI

Abstract

Epidemic modeling is essential in understanding the spread of infectious diseases like COVID-19 and devising effective intervention strategies to control them. Recently, network-based disease models have integrated traditional compartment-based modeling with real-world contact graphs and shown promising results. However, in an ongoing epidemic, future contact network patterns are not observed yet. To address this, we use aggregated static networks to approximate future contacts for disease modeling. The standard method in the literature concatenates all edges from a dynamic graph into one collapsed graph, called the full static graph. However, the full static graph often leads to severe overestimation of key epidemic characteristics. Therefore, we propose two novel static network approximation methods, DegMST and EdgeMST, designed to preserve the sparsity of real world contact network while remaining connected. DegMST and EdgeMST use the frequency of temporal edges and the node degrees respectively to preserve sparsity. Our analysis show that our models more closely resemble the network characteristics of the dynamic graph compared to the full static ones. Moreover, our analysis on seven real-world contact networks suggests EdgeMST yield more accurate estimations of disease dynamics for epidemic forecasting when compared to the standard full static method.

Introduction

To predict the trajectory of infectious diseases, researchers increasingly rely on contact networks—mathematical representations of human interactions. While real-world interactions are inherently dynamic, forecasting requires approximating future contact patterns that have not yet occurred. The conventional approach involves collapsing historical dynamic data into a "full static graph," where an edge is created if two individuals interacted at any point.

However, this "all-edges" approach creates a dense "hairball" network that significantly overestimates the speed and scale of an epidemic. Because the model assumes everyone is constantly in contact with every past acquaintance, it predicts an immediate explosion of cases that fails to materialize in reality.

Visual comparison of infection spread across different network approximation methods. The full static graph (right) creates a dense "hairball" that overestimates spread compared to the ground truth dynamic network (left).

Methodology: Preserving Sparsity and Connectivity

The core challenge is creating a static approximation that is simple enough for forecasting but sparse enough to be realistic. We propose two algorithms that prioritize the structural integrity of the network over raw edge count:

  1. EdgeMST (Edge Minimum Spanning Tree): This method focuses on "loyalty" or recurring connections. It identifies the most frequent edges in the dynamic data. By first building a Minimum Spanning Tree (MST), it ensures the graph remains fully connected, then adds the most frequent edges until the graph matches the average density (degree) of the original dynamic snapshots.
  2. DegMST (Degree Minimum Spanning Tree): This method prioritizes "hubs" or potential super-spreaders. Like EdgeMST, it starts with an MST but populates the remaining edges based on node degrees, focusing on individuals with the highest total number of contacts.

Experimental Results

We validated these models across seven diverse real-world contact datasets, ranging from university Bluetooth data (Copenhagen) to large-scale mobility data (SafeGraph).

Infection curves across seven real-world datasets. The proposed EdgeMST and DegMST methods (dashed lines) closely track the dynamic ground truth (black solid line), whereas the full static baseline (red solid line) consistently overestimates infection rates.

Accuracy and Peak Prediction

In forecasting scenarios, EdgeMST and DegMST produced infection curves that were 3 to 4 times more accurate than the full static baseline. While the full static graph overestimated the maximum fraction of infected individuals by an average of 18.5%, EdgeMST reduced this error to just 5.4%.

Structural Fidelity

EdgeMST proved particularly effective at mimicking the "Global Efficiency" of the true dynamic graph. This suggests that the "skeleton" of an epidemic is formed by stable, recurring contacts rather than just high-traffic individuals. Furthermore, because these proposed graphs are significantly sparser, simulations run on them are computationally faster than those using dense full static models.

Conclusion

Our findings demonstrate that in epidemic modeling, "less is more." By focusing on the most frequent or central connections and maintaining network connectivity through MSTs, we can create static approximations that far outperform traditional dense baselines. While these models currently assume past patterns predict future ones, future work will explore augmenting EdgeMST and DegMST with predictive algorithms to account for evolving social behaviors.

Summary updated

Abstract

Epidemic modeling is essential in understanding the spread of infectious diseases like COVID-19 and devising effective intervention strategies to control them. Recently, network-based disease models have integrated traditional compartment-based modeling with real-world contact graphs and shown promising results. However, in an ongoing epidemic, future contact network patterns are not observed yet. To address this, we use aggregated static networks to approximate future contacts for disease modeling. The standard method in the literature concatenates all edges from a dynamic graph into one collapsed graph, called the full static graph. However, the full static graph often leads to severe overestimation of key epidemic characteristics. Therefore, we propose two novel static network approximation methods, DegMST and EdgeMST, designed to preserve the sparsity of real world contact network while remaining connected. DegMST and EdgeMST use the frequency of temporal edges and the node degrees respectively to preserve sparsity. Our analysis show that our models more closely resemble the network characteristics of the dynamic graph compared to the full static ones. Moreover, our analysis on seven real-world contact networks suggests EdgeMST yield more accurate estimations of disease dynamics for epidemic forecasting when compared to the standard full static method.
BibTeX
@inproceedings{shirzadkhani2024static,
  author = {Razieh Shirzadkhani and Shenyang Huang and Abby Leung and Reihaneh Rabbany},
  title = {{Static graph approximations of dynamic contact networks for epidemic forecasting}},
  booktitle = {Scientific},
  year = {2024},
  doi = {10.1038/s41598-024-62271-0},
}
Figure