论文标题
使用网络上的概率扩散模型来控制流行病的传播
Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
论文作者
论文摘要
流行病的传播通常是通过社交网络图上的SIR随机过程对其进行建模的。最佳社会距离的矿物质问题涉及最大程度地减少预期的感染次数，当我们被允许最多$ b $边缘中断时；同样，MinInfnode问题涉及最多删除$ B $顶点。这些是流行病学和网络科学中的基本问题。尽管已经考虑了许多启发式方法，但这些问题的复杂性通常仍然开放。在本文中，我们提出了MinInf的两种双晶格近似算法，这些算法给出了此问题的第一个非平地近似值。首先是基于Karger \ cite {Karger：Mathor99}的剪切稀疏结果，并且当传输概率不太小时起作用。第二个是基于样本的平均近似值（SAA）算法，我们为Chung-Lu随机图模型进行了分析。我们还扩展了一些结果来解决Mininfnode问题。
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.
