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 fixed budget 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: www.cs.vt.edu/~badityap/NSF-PROJECTS/EAGER-13/
