Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework
Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework
复制标题
DOI：
10.1017/nws.2022.18
复制
发表时间：
2022-08-30
期刊：
影响因子：
1.7
通讯作者：
Rosenkrantz，Daniel J.
中科院分区：
文献类型：
--
作者：
Carscadden，Henry L.;Kuhlman，Chris J.;Rosenkrantz，Daniel J.
我们考虑两种传染病在一个社会网络上同时传播。我们假设了两个传染病传播的阈值模型，并使用离散动力系统的形式框架。特别地，我们研究了一个优化问题，其目标是在对传染病可用疫苗总数的预算约束下使新感染总数最小化。虽然这一问题在文献中被认为是单一传染，但我们的工作考虑了两种传染的同时传播。这个优化问题是np困难的。我们提出了两种主要的解决方法，即整数线性规划（ILP）公式来获得最优解和基于集合覆盖问题推广的启发式方法。我们使用许多现实世界的网络对我们的解决方案方法进行了全面的实验评估。实验结果表明，我们的启发式算法产生的解接近最优解，并且比基于ilp的方法获得最优解的速度快几个数量级。我们还对我们的启发式算法进行了敏感性研究。
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.