skip to main content
10.1145/1963192.1963194acmotherconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
poster

Toward optimal vaccination strategies for probabilistic models

Published: 28 March 2011 Publication History

Abstract

Epidemic outbreaks such as the recent H1N1 influenza show how susceptible large communities are toward the spread of such outbreaks. The occurrence of a widespread disease transmission raises the question of vaccination strategies that are appropriate and close to optimal. The seemingly different problem of viruses disseminating through email networks, shares a common structure with disease epidemics. While it is not possible to vaccinate every individual during a virus outbreak, due to economic and logistical constraints, fortunately, we can leverage the structure and properties of face-to-face social networks to identify individuals whose vaccination would result in a lower number of infected people.
The models that have been studied so far [3, 4] assume that once an individual is infected all its adjacent individuals would be infected with probability 1. However, this assumption is not realistic. In reality, if an individual is infected by a virus, the neighboring individuals would get infected with some probability (depending on the type of the disease and the contact). This modification to the model makes the problem more challenging as the simple version is already NP-complete [3].
Here we consider the following epidemiological model computationally: A number of individuals in the community get vaccinated which makes them immune to the disease. The disease then outbreaks and a number of nodes that are not vaccinated get infected at random. These nodes can transmit the infection to their friends with some probability. In this work we consider the optimization problem in which the number of nodes that get vaccinated is limited to k and our objective is to minimize the number of infected people overall. We design various algorithms that take into account the properties of social networks to select k nodes for vaccination in order to achieve the goal. We perform experiments on a real dataset of 34,546 vertices and 421,578 edges and assess their effectiveness and scalability.

References

[1]
www.cs.columbia.edu/~zeinab/poster.pdf
[2]
D. Kempe, J. Kleinberg, É. Tardos, Maximizing the Spread of Influence through a Social Network, KDD'03.
[3]
J. Aspnes, K. Chang, A. Yampolskiy, Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem, Journal of Computer and System Sciences, 2006.
[4]
P. Chen, M. David, D. Kempe, Better Vaccination Strategies for Better People, EC'10.
[5]
M. Newman. The structure of scientific collaborationnetworks. Proc. Natl. Acad. Sci. 98(2001).
[6]
J. Gehrke, P. Ginsparg, J. M. Kleinberg. Overview of the 2003 KDD Cup. SIGKDD Explorations 2003.

Cited By

View all
  • (2015)Formation of Stable Strategic Networks with Desired TopologiesStudies in Microeconomics10.1177/23210222155888733:2(158-213)Online publication date: 23-Dec-2015
  • (2015)Node Immunization over Infectious PeriodProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806522(831-840)Online publication date: 17-Oct-2015

Index Terms

  1. Toward optimal vaccination strategies for probabilistic models

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    WWW '11: Proceedings of the 20th international conference companion on World wide web
    March 2011
    552 pages
    ISBN:9781450306379
    DOI:10.1145/1963192

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 28 March 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. SIR
    2. probabilistic model
    3. social networks
    4. vaccination
    5. virus propagation

    Qualifiers

    • Poster

    Conference

    WWW '11
    WWW '11: 20th International World Wide Web Conference
    March 28 - April 1, 2011
    Hyderabad, India

    Acceptance Rates

    Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 07 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2015)Formation of Stable Strategic Networks with Desired TopologiesStudies in Microeconomics10.1177/23210222155888733:2(158-213)Online publication date: 23-Dec-2015
    • (2015)Node Immunization over Infectious PeriodProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806522(831-840)Online publication date: 17-Oct-2015

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media