EAGER: Immunization in Influence and Virus Propagation on Large Networks

给定一个图，如社交/计算机网络或博客圈，其中感染（或模因或病毒）已经传播了一段时间，如何选择k个最佳节点立即进行免疫/消除？该团队是第一个证明传播（特别是所谓的“流行病阈值”）取决于一个单一的数字，网络邻接矩阵的第一个特征值，对于任何图和文献中的几乎任何传播模型。该团队还通过最小化任意图上的特征值，给出了静态抢占节点/边删除的线性时间可证明的近优算法。他们也是第一个给出一个线性时间算法，在完美信息下自动检测可能的罪犯的数量和身份，仔细使用最小描述长度原则，再次在任意图上。 这个建议的主要目的是：给定一个图，一个病毒模型（SIR，SIS等），一组已经感染的节点，和一个固定预算的k个节点/边缘免疫或隔离，可以快速找到一个最佳或接近最佳的解决方案，以最好地遏制病毒？技术优点：这是第一个研究任意图上的短期免疫问题。这个问题在过去的文献中受到了有限的关注：目前的一些结果（除了PI过去的工作，见相关工作）都是在特定的图上，如随机图，而不是任意图。这项工作的重点是可扩展的技术（线性或次二次节点/边缘），可应用于大型graphs.Impact：这项工作有许多直接应用在公共卫生和流行病学，例如，利用弗吉尼亚生物信息学研究所最先进的模拟器，这项工作有助于进行逼真的模拟，以及为未来做出更明智的选择和政策决定。这项工作也有更广泛的影响，因为网络上的传播式过程出现在许多其他环境中，如病毒式营销，网络安全，Twitter和博客等社交媒体。教育：PI将把研究成果纳入研究生课程，在会议上提供辅导，旨在通过NSF REU和MAOP/VTURCS等项目，吸引来自代表性不足群体的本科生进入这一令人兴奋的研究领域（少数民族学术机会计划和VT本科生CS研究）。欲了解更多信息，请参阅项目网页：URL：http://www.cs.vt.edu/~badityap/NSF-PROJECTS/EAGER-13/

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 does one select the k best nodes for immunization/quarantining immediately? This team was the first to show that the propagation (specifically, the so-called "epidemic threshold") depends on a single number, the first eigenvalue of the adjacency matrix of the network, for any graph and almost any propagation model in the literature. This team also gave linear-time provably near-optimal algorithms for static pre-emptive node/edge removal, by minimizing the eigenvalue on arbitrary graphs. They were also the first to give a a linear-time algorithm to automatically detect the number and identity of possible culprits under perfect information, carefully using the Minimum Description Length principle, again on arbitrary graphs. The major thrust of this proposal is: Given a graph, a virus model (SIR, SIS etc.), a set of already infected nodes, and a fixedbudget of k nodes/edges to immunize or quarantine, can one quickly find an optimal or near-optimal solution to best contain the virus?Technical Merit: This is the first to study the short-term immunization problem on arbitrary graphs. The problem has received limited attention in past literature: the few current results (except the PI's past work, see related work) all are on specific graphs like random graphs, and not arbitrary graphs. The focus of this work is on scalable techniques (linear or sub-quadratic on nodes/edges) which can be applied to large graphs.Impact: The work has numerous immediate applications in public health and epidemiology, e.g., designing dynamic "what to do next" policies etc. Leveraging state-of-the-art simulators from the Virginia Bio-Informatics Institute, this work helps in realistic simulations, as well as in making more informed choices and policy decisions for future. The work also has high broader impact, as propagation-style processes on networks appear in many other settings like viral marketing, cyber security, social media like Twitter and blogs etc.Education: The PI will incorporate research findings in graduate level classes, give tutorials at conferences, and aim to engage undergraduate students from underrepresented groups into this exciting area of research through programs like NSF REU and MAOP/VTURCS (Minority Academic Opportunities Program and VT Undergraduate Research in CS) at VT.For further information, please see the project web page: URL: http://www.cs.vt.edu/~badityap/NSF-PROJECTS/EAGER-13/