Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models
Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models
复制标题
DOI：
10.1137/20m1377011
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Yuhao Yi;Liren Shan;Philip E. Par'e;K. Johansson
中科院分区：
文献类型：
--
作者：
Yuhao Yi;Liren Shan;Philip E. Par'e;K. Johansson
本文研究了易感-感染-恢复（SIR）流行病模型中有效减少感染人数的算法策略。我们考虑了马尔可夫链SIR模型及其在确定性SIR （D-SIR）模型和独立级联SIR （IC-SIR）模型中的两个实例。我们研究了在现实条件下通过限制接触来使感染人数最小化的问题。在对复制数的适度假设下，我们证明了大类别随机网络的D-SIR模型和IC-SIR模型中的感染数有超模函数有界。我们提出了具有近似保证的有效算法来最小化感染。数值模拟验证了理论结果。
This paper studies algorithmic strategies to effectively reduce the number of infections in susceptible-infected-recovered (SIR) epidemic models. We consider a Markov chain SIR model and its two instantiations in the deterministic SIR (D-SIR) model and the independent cascade SIR (IC-SIR) model. We investigate the problem of minimizing the number of infections by restricting contacts under realistic constraints. Under moderate assumptions on the reproduction number, we prove that the infection numbers are bounded by supermodular functions in the D-SIR model and the IC-SIR model for large classes of random networks. We propose efficient algorithms with approximation guarantees to minimize infections. The theoretical results are illustrated by numerical simulations.