Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks

Amy E. Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:11641-11654, 2022.

Abstract

The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInfEdge problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinInfNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of this problem remains generally open. In this paper, we present two bicriteria approximation algorithms for the MinInfEdge problem, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result technique of Karger, which works for any graph, when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results for the MinInfNode problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-babay22a, title = { Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks }, author = {Babay, Amy E. and Dinitz, Michael and Srinivasan, Aravind and Tsepenekas, Leonidas and Vullikanti, Anil}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {11641--11654}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/babay22a/babay22a.pdf}, url = {https://proceedings.mlr.press/v151/babay22a.html}, abstract = { The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInfEdge problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinInfNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of this problem remains generally open. In this paper, we present two bicriteria approximation algorithms for the MinInfEdge problem, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result technique of Karger, which works for any graph, when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results for the MinInfNode problem. } }
Endnote
%0 Conference Paper %T Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks %A Amy E. Babay %A Michael Dinitz %A Aravind Srinivasan %A Leonidas Tsepenekas %A Anil Vullikanti %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-babay22a %I PMLR %P 11641--11654 %U https://proceedings.mlr.press/v151/babay22a.html %V 151 %X The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInfEdge problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinInfNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of this problem remains generally open. In this paper, we present two bicriteria approximation algorithms for the MinInfEdge problem, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result technique of Karger, which works for any graph, when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results for the MinInfNode problem.
APA
Babay, A.E., Dinitz, M., Srinivasan, A., Tsepenekas, L. & Vullikanti, A.. (2022). Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:11641-11654 Available from https://proceedings.mlr.press/v151/babay22a.html.

Related Material