EAGER: Immunization in Influence and Virus Propagation on Large Networks

给出一个图表，比如社交/计算机网络或博客圈，其中的感染(或模因或病毒)已经传播了一段时间，如何立即选择k个最佳节点进行免疫/隔离？这个团队首次证明，对于任何图和几乎所有文献中的传播模型，传播(具体地说，所谓的“流行病阈值”)取决于单个数字，即网络的邻接矩阵的第一个特征值。该团队还通过最小化任意图上的特征值，给出了静态抢占式节点/边去除的线性时间可证明接近最优的算法。他们也是第一个给出一个线性时间算法，在完全信息下自动检测可能的罪犯的数量和身份，同样是在任意图上，仔细地使用最小描述长度原则。这个建议的主要目的是：给定一个图、一个病毒模型(SIR、SIS等)、一组已感染的节点以及用于免疫或隔离的k个节点/边的固定预算，能否快速找到最优或接近最优的解决方案以最好地遏制病毒？技术优点：这是第一次在任意图上研究短期免疫问题。这个问题在过去的文献中得到的关注有限：目前的少数结果(除了PI过去的工作，见相关工作)都是在特定的图上，如随机图，而不是任意图。这项工作的重点是可扩展技术(节点/边上的线性或次二次)，可应用于大型图形。影响：该工作在公共卫生和流行病学中有许多即时应用，例如，设计动态的“下一步要做什么”政策等。利用弗吉尼亚生物信息学研究所最先进的模拟器，这项工作有助于进行真实的模拟，以及为未来做出更明智的选择和政策决策。这项工作也具有高度广泛的影响，因为网络上的传播风格过程出现在许多其他环境中，如病毒营销、网络安全、社交媒体，如推特和博客等。教育：PI将在研究生水平的课堂上纳入研究成果，在会议上提供教程，旨在通过VT的NSF REU和MAOP/VTURCS(少数族裔学术机会计划和VT本科生研究)等项目吸引来自未被充分代表的群体的本科生进入这一令人兴奋的研究领域。有关更多信息，请参阅项目网页：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/