Fractional Immunization in Networks
Fractional Immunization in Networks
复制标题
DOI：
10.1137/1.9781611972832.73
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
B. Aditya Prakash;Lada A. Adamic;T. Iwashyna;Hanghang Tong;C. Faloutsos
中科院分区：
文献类型：
--
作者：
B. Aditya Prakash;Lada A. Adamic;T. Iwashyna;Hanghang Tong;C. Faloutsos
预防网络传播是公共卫生等领域的一个重要问题。已经证明，根据节点的网络相互作用来针对节点进行免疫在阻止感染传播方面比对节点的随机子集进行免疫要有效得多。然而，可以使选定的节点完全免疫的假设不适用于没有接种疫苗或有效治疗的感染。相反，人们可以通过向某些节点分配不同数量的感染预防资源来授予部分免疫力。我们将问题描述为在网络中的节点之间分配固定数量的资源，使感染率最小，证明了该问题是NP完全的，并推导出一个高效的线性时间算法。与其他几种方法相比，我们在真实世界的网络数据集(包括美国医疗保险和州级医院间患者转移数据)上的模拟实验证明了我们的算法的有效性和准确性。我们发现，使用我们的算法将资源集中在一小部分节点上比均匀分布资源(按照当前的做法)或使用基于网络的启发式算法的效率高达6倍。据我们所知，我们是第一个制定问题的人，使用真正全国性的网络数据，并提出有效的算法。
Preventing contagion in networks is an important problem in public health and other domains. Targeting nodes to immunize based on their network interactions has been shown to be far more effective at stemming infection spread than immunizing random subsets of nodes. However, the assumption that selected nodes can be rendered completely immune does not hold for infections for which there is no vaccination or effective treatment. Instead, one can confer fractional immunity to some nodes by allocating variable amounts of infection-prevention resource to them. We formulate the problem to distribute a fixed amount of resource across nodes in a network such that the infection rate is minimized, prove that it is NP-complete and derive a highly effective and efficient linear-time algorithm. We demonstrate the efficiency and accuracy of our algorithm compared to several other methods using simulation on realworld network datasets including US-MEDICARE and state-level interhospital patient transfer data. We find that concentrating resources at a small subset of nodes using our algorithm is up to 6 times more effective than distributing them uniformly (as is current practice) or using network-based heuristics. To the best of our knowledge, we are the first to formulate the problem, use truly nation-scale network data and propose effective algorithms.