Data-Aware Vaccine Allocation Over Large Networks
Data-Aware Vaccine Allocation Over Large Networks
复制标题
DOI：
10.1145/2803176
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
Yao Zhang;B. Prakash;Virginia Tech
中科院分区：
文献类型：
--
作者：
Yao Zhang;B. Prakash;Virginia Tech
给出一个图，比如社交/计算机网络或博客圈，其中的感染(或模因或病毒)已经传播了一段时间，如何立即选择k个最佳节点进行免疫/隔离？以前大多数控制传播的工作(例如通过免疫)都集中在制定在疫情开始之前先发制人接种疫苗的战略。虽然提供关于哪些基线策略可以最好地控制感染的见解非常有用，但它们对于在感染进展时做出实时决策可能并不理想。在本文中，我们研究如何在已经感染的节点存在的情况下对健康节点进行免疫。解决此类问题的有效算法可以帮助公共卫生专家做出更明智的选择，使他们的决定符合当地疫情的实际分布。首先，我们建立了数据感知疫苗接种问题的数学模型，并证明了它是NP难的，也是很难逼近的。其次，我们提出了三种有效的多项式时间启发式算法DAVA、DAVA-PRUNE和DAVA-FAST，它们的效率和性能各不相同。最后，我们还通过在包括大型流行病学数据集(包含数百万个交互)在内的多个真实网络上的广泛实验，证明了我们的算法的可扩展性和有效性。我们的算法显示，与许多其他直观和非平凡的竞争对手相比，我们的算法最终可以获得高达十倍的健康节点。
Given a graph, like a social/computer network or the blogosphere, in which an infection (or meme or virus) has been spreading for some time, how to select the k best nodes for immunization/quarantining immediately? Most previous works for controlling propagation (say via immunization) have concentrated on developing strategies for vaccination preemptively before the start of the epidemic. While very useful to provide insights in to which baseline policies can best control an infection, they may not be ideal to make real-time decisions as the infection is progressing. In this paper, we study how to immunize healthy nodes, in the presence of already infected nodes. Efficient algorithms for such a problem can help public-health experts make more informed choices, tailoring their decisions to the actual distribution of the epidemic on the ground. First we formulate the Data-Aware Vaccination problem, and prove it is NP-hard and also that it is hard to approximate. Secondly, we propose three effective polynomial-time heuristics DAVA, DAVA-prune and DAVA-fast, of varying degrees of efficiency and performance. Finally, we also demonstrate the scalability and effectiveness of our algorithms through extensive experiments on multiple real networks including large epidemiology datasets (containing millions of interactions). Our algorithms show substantial gains of up to ten times more healthy nodes at the end against many other intuitive and nontrivial competitors.