Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinINF 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 MinINF, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger \cite{karger:mathor99}, 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.
Code (0)
등록된 구현이 없습니다.
Tasks
EpidemiologySimilar Papers 제목 키워드 기반
Diffusion Model for Graph Inverse Problems: Towards Effective Source Localization on Complex Networks
Information diffusion problems, such as the spread of epidemics or rumors, are widespread in society. The inverse problems of graph diffusion, which involve locating the sources and identifying the paths of diffusion bas…
Group Sparse Bayesian Learning for Active Surveillance on Epidemic Dynamics
Predicting epidemic dynamics is of great value in understanding and controlling diffusion processes, such as infectious disease spread and information propagation. This task is intractable, especially when surveillance r…
Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks
We consider the problem of controlling a partially-observed dynamic process on a graph by a limited number of interventions. This problem naturally arises in contexts such as scheduling virus tests to curb an epidemic; t…
Marketingreinforcement-learningReinforcement LearningReinforcement Learning (RL)+1Predicting the diversity of early epidemic spread on networks
The interplay of biological, social, structural and random factors makes disease forecasting extraordinarily complex. The course of an epidemic exhibits average growth dynamics determined by features of the pathogen and …
DiversityImpact of density-dependent migration flows on epidemic outbreaks in heterogeneous metapopulations
We investigate the role of migration patterns on the spread of epidemics in complex networks. We enhance the SIS-diffusion model on metapopulations to a nonlinear diffusion. Specifically, individuals move randomly over t…