Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
International Conference on Artificial Intelligence and Statistics, Vol 151
; 151, 2022.
Article
in English
| Web of Science | ID: covidwho-2083262
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 these problems remains generally open. In this paper, we present two bicriteria approximation algorithms for MININFEDGE, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger (1999), and works 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 to tackle the MININFNODE problem.
Search on Google
Collection:
Databases of international organizations
Database:
Web of Science
Language:
English
Journal:
International Conference on Artificial Intelligence and Statistics, Vol 151
Year:
2022
Document Type:
Article
Similar
MEDLINE
...
LILACS
LIS