Fractional immunization in networks

B. Aditya Prakash, Lada Adamic, Theodore Iwashyna, Hanghang Tong, Christos Faloutsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Preventing contagion in networks is an important problem in public health and other domains. Targeting nodes to immunize based on their network interactions has been shown to be far more effective at stemming infection spread than immunizing random subsets of nodes. However, the assumption that selected nodes can be rendered completely immune docs not hold for infections for which there is no vaccination or effective treatment. Instead, one can confer fractional immunity to some nodes by allocating variable amounts of infection-prevention resource to them. We formulate the problem to distribute a fixed amount of resource across nodes in a network such that the infection rate is minimized, prove that it is NP-complete and derive a highly effective and efficient linear-time algorithm. We demonstrate the efficiency and accuracy of our algorithm compared to several other methods using simulation on real-world network datasets including US-MEDICARE and state-level interhospital patient transfer data. We find that concentrating resources at a small subset of nodes using our algorithm is up to 6 times more effective than distributing them uniformly (as is current practice) or using network-based heuristics. To the best of our knowledge, we are the first to formulate the problem, use truly nation-scale network data and propose effective algorithms.

Original languageEnglish (US)
Title of host publicationSIAM International Conference on Data Mining 2013, SMD 2013
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages9
ISBN (Print)9781627487245
StatePublished - 2013
Externally publishedYes
Event13th SIAM International Conference on Data Mining, SMD 2013 - Austin, United States
Duration: May 2 2013May 4 2013


Other13th SIAM International Conference on Data Mining, SMD 2013
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Signal Processing
  • Software


Dive into the research topics of 'Fractional immunization in networks'. Together they form a unique fingerprint.

Cite this