This proposal aimed to answer the following question: Given an infected snapshot of the network, what are the best nodes to immunize (vaccinate) in the network? Viruses or contagions like the flu spread on population contact networks. Similarly, online contagions like memes spread on social networks. There exist many stochastic models inspired by epidemiology which model these propagation processes. In this proposal, 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, and a virus propagation model (like SIR, SIS etc.), we want to select the k best nodes for immunization/quarantining immediately. We call this problem 'short-term immunization'. We proposed to develop new scalable algorithms for short­ term immunization on arbitrary graphs, under full information. We also proposed to test our techniques on basic as well more realistic simulations and datasets. The broader goal of this line of research is to investigate more such 'data-ware' approaches to immunization given both perfect or noisy data.

We were the first to study the short-term immunization problem on arbitrary graphs, as opposed to the vast majority of analytical work which focusses on 'pre-emptive' strategies. Further we were also the first to examine multiple natural uncertainty models of infection information and design robust immunization policies. We proposed DAVA, a novel scalable (sub-quadratic in size of the underlying network) algorithm to distribute vaccines over large-scale networks under a perfect data-aware environment, which outperforms well-known competitors, e.g, 'Netshield', 'Pagerank' etc., by up to 10 times in magnitude. We further provided a variant which does not reconstruct intermediate data structures from scratch upon each allocation. We also proposed two novel algorithms, SAMPLE-CAS and EXPECT-MAX, to allocate vaccines in large networks considering multiple natural uncertain environments, which outperform several state-of-the-art algorithms, getting substantial gains in both number of nodes saved and running time. We also proposed rigorous approximation algorithms for the pre-emptive immunization problem. We leveraged multiple techniques like dominator trees (from software flow theory) which were not commonly used in this area. We also tested all our algorithms on realistic city-wide epidemiological datasets. In short, this grant has resulted in four full research papers at leading venues (both conferences and journals) including SDM 2014, CIKM 2014, SDM 2015 and ACM TKDD 2015. 

This grant supported PhD. students, including a female graduate student. Material from this research appeared in graduate classes, invited talks at national labs, and companies, and in lectures at NSF REU summer schools for underrepresented undergraduate groups at VT by the PI. Further this research has enabled numerous follow-on work from natural realistic generalizations, to newer techniques for old problems, to the submission of larger proposals to study related problems using real diagnostic data, in collaboration with epidemiologists and computational biologists.

The immediate impact of the work is high due to applications in public health and epidemiology such as designing dynamic ‘what to do next’ policies. As we leverage state- of-the-art simulators, this also helps in making more informed choices and policy decisions for future. Further the broader impact is also high as propagation-style processes on networks appear in many other settings like viral marketing, cyber security (malware), social media like Twitter and blogs etc.

More information can be found at: http://people.cs.vt.edu/~badityap/NSF-PROJECTS/EAGER-13/

Last Modified: 12/07/2015
Modified by: B. Aditya Prakash