Immunization in Influence and Virus Propagation on Large Networks

 
B. Aditya Prakash Phone: 540-231-0906
Department of Computer Science Fax : 540-231-4240
Virginia Tech Email: badityap@cs.vt.edu
Blacksburg, VA 24061 Website: http://people.cs.vt.edu/~badityap

This material is based upon work supported by the National Science Foundation under Grant No. IIS-1353346. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

1. GENERAL INFORMATION

1.1. Abstract

Link to NSF abstract

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?

1.2. Keywords

Graph mining, Virus Propagation, Immunization, Social Networks.

1.3. Funding agency

2. PEOPLE INVOLVED

In addition to the PI, the following people have worked on the project.

3. RESEARCH

3.1. Project goals

The goal of the project is to develop fast near-optimal immunization strategies to best contain the virus on large-scale networks.

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.

3.2. Current Results

Our main results are as given below. 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.
  • We proposed DAVA, a novel scalable (sub-quadratic) algorithm to distribute vaccines over large-scale networks under the data-aware environment, which outperforms well-known competitors, e.g, 'Netshield', 'Pagerank' etc., by up to 10 times in magnitude.
  • 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.

3.3. Publications

  1. DAVA: Distributing Vaccines over Networks under Prior Information [PDF] [SLIDES] [CODE]
    Yao Zhang and B. Aditya Prakash
    in SIAM Conference on Data Mining (SDM 2014), April 2014, Philadelphia
    Received SDM student travel award

  2. Scalable Vaccine Distribution in Large Graphs given Uncertain Data [PDF][SLIDES][CODE]
    Yao Zhang and B. Aditya Prakash
    in 23rd ACM International Conference on Information and Knowledge Management (CIKM 2014), November 2014, Shanghai, China

  3. Data-Aware Vaccine Allocation over Large Networks [PDF][CODE]
    Yao Zhang and B. Aditya Prakash
    in ACM Transactions on Knowledge Discovery from Data (TKDD), October 2015.

  4. Approximation Algorithms for Reducing the Spectral Radius to control Epidemic Spread [PDF][CODE]
    Sudip Saha, Abhijin Adiga, B. Aditya Prakash and Anil Vullikanti
    in SIAM Conference on Data Mining (SDM 2015), May 2015, Vancouver.

  5. Controlling Propagation at Group Scale on Networks [PDF][CODE]
    Yao Zhang, Abhijin Adiga, Anil Vullikanti and B. Aditya Prakash
    in IEEE International Conference on Data Mining (ICDM 2015), November 2015, Atlantic City
    Received ICDM student travel award

4. EDUCATION

The PI has already added material from this research in graduate classes (CS 6604), in invited talks at national labs (ORNL) and symposium (like MIT GraphEx 2014) and in lectures at summer schools for underrepresented undergraduate groups at VT.
Last updated: December 7, 2015, by B. Aditya Prakash and Yao Zhang