Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework

Henry L. Carscadden, Chris J. Kuhlman, Madhav V. Marathe, S. S. Ravi, Daniel J. RosenkrantzNetw. Sci 2022 · DOI · OpenReview

Introduction

In contemporary network science, modeling the spread of a single contagion—be it a biological virus or a piece of information—is a well-established field. However, real-world scenarios often involve the simultaneous propagation of multiple, potentially interacting entities. Examples include the concurrent spread of two different viral strains or a disease spreading alongside related misinformation. This paper investigates the Vaccination Scheme to Minimize the Total Number of New Infections (VS-MTNNI), a resource allocation problem aimed at identifying the optimal set of nodes to "vaccinate" or block to minimize the cumulative impact of two simultaneous contagions.

Problem Formulation

The VS-MTNNI problem is defined within a network where a limited budget of blocking actions is available. The goal is to select a subset of nodes for vaccination such that the total number of new infections across both contagions is minimized over a fixed time horizon. The authors demonstrate that this optimization problem is NP-hard, necessitating the development of efficient heuristic solutions for large-scale applications.

Methodology

Graph Dynamical Systems Framework

The study employs a Synchronous Dynamical System (SyDS) framework utilizing a threshold model. In this model, a node transitions to an infected state if the number of its infected neighbors meets or exceeds a predefined threshold. This deterministic approach allows for precise modeling of propagation dynamics over discrete time steps.

A simple directed graph representing influence pathways in a synchronous dynamical system.

Optimization Approaches

Two primary methods were developed to address the VS-MTNNI problem:

  1. Integer Linear Programming (ILP): An exact mathematical formulation designed to find the optimal vaccination set. While providing a benchmark for accuracy, the ILP approach is computationally intensive and does not scale to large networks.
  2. MCICH-SMC Heuristic: The core contribution of this work is the "Multi-Contagion Influence-based Centrality Heuristic." By reframing the blocking problem as a Set Multicover (SMC) optimization, the heuristic identifies nodes that are likely to be infected in the immediate "next wave." It greedily selects the most influential neighbors to vaccinate, effectively "covering" at-risk nodes and preventing them from reaching their infection thresholds.

Experimental Evaluation

The proposed methods were evaluated on seven real-world networks, ranging from small collaboration networks to large social media communication graphs including the Jazz musician network, Facebook politician pages, and the Enron email network. These datasets provide a diverse set of topologies to test the robustness of the heuristic.

Results and Discussion

Performance and Scalability

The MCICH-SMC heuristic demonstrated near-optimal performance, yielding results closely matching the ILP solutions on smaller networks where the latter could be computed. Crucially, the heuristic achieved a massive computational speedup—often several orders of magnitude faster than the ILP—enabling its application to networks with tens of thousands of nodes in seconds.

Visualization of multi-contagion propagation across a network over successive time steps, illustrating the "waves" of infection.

Strategic Insights

  • Next-Wave Strategy: Focusing on the immediate frontier of the contagion is more effective than attempting to model the entire long-term spread at once.
  • Budget Allocation: A proportional split of the vaccination budget based on the initial threat level of each contagion proved to be a robust strategy.
  • Network Topology: The researchers found that clustered seeding (the "Centola" method) is significantly harder to block as thresholds increase, due to the reinforcing nature of high-clustering social structures.

Conclusion

This research provides a scalable and effective framework for managing simultaneous contagions in complex networks. By leveraging the Set Multicover paradigm, the MCICH-SMC heuristic offers a practical tool for public health and information security, capable of flattening the infection curve even under tight budget constraints. Future work will explore interacting contagions, stochastic propagation models, and non-uniform node thresholds.

Summary updated

Abstract

We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.
BibTeX
@article{carscadden2022techniques,
  author = {Henry L. Carscadden and Chris J. Kuhlman and Madhav V. Marathe and S. S. Ravi and Daniel J. Rosenkrantz},
  title = {{Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework}},
  journal = {Netw. Sci.},
  year = {2022},
  doi = {10.1017/nws.2022.18},
}
Figure