Data-Aware Vaccine Allocation Over Large Networks

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 to select thekbest nodes for immunization/quarantining immediately? Most previous works for controlling propagation (say via immunization) have concentrated on developing strategies for vaccinationpreemptivelybefore the start of the epidemic. While very useful to provide insights in to which baseline policies can best control an infection, they may not be ideal to makereal-timedecisions as the infection is progressing. In this paper, we study how to immunize healthy nodes, in the presence of already infected nodes. Efficient algorithms for such a problem can help public-health experts make more informed choices, tailoring their decisions to the actual distribution of the epidemic on the ground. First we formulate theData-Aware Vaccinationproblem, and prove it is NP-hard and also that it is hard to approximate. Secondly, we propose three effective polynomial-time heuristics DAVA, DAVA-prune and DAVA-fast, of varying degrees of efficiency and performance. Finally, we also demonstrate the scalability and effectiveness of our algorithms through extensive experiments on multiple real networks including large epidemiology datasets (containing millions of interactions). Our algorithms show substantial gains of up toten timesmore healthy nodes at the end against many other intuitive and nontrivial competitors.