Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models

Autor:	Yi, Yuhao, Shan, Liren, Paré, Philip E., Johansson, Karl H.
Rok vydání:	2020
Předmět:	Mathematics - Optimization and Control Computer Science - Social and Information Networks
Druh dokumentu:	Working Paper
Popis:	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. Comment: 29 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2011.11087 Zobrazit plný text záznamu View this record from Arxiv