Title: Stopping the spread of infection in a social network with limited vaccination allowed during each step
Speaker: Michael Capalbo, DIMACS
Date: June 6, 2005 2:30 - 3:45 pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Consider the following model for the spread of an infection (or dangerous knowledge): A group U_0 of people in a social network are initially infected. Each infected person will spread the infection to all of his not-yet vaccinated neighbors in one time step (and once a person is infected, he stays infected forevermore). Our allowed response is to vaccinate a limited number of people in each time step (a person vaccinated cannot catch nor transmit the infection forevermore), and our desired outcome is to limit the number of people who will eventually catch the infection to as small a group as possible. In this talk, we present a bicriteria approximation algorithm for this problem, assuming that the underlying social network satisfies a certain (reasonable) structural property.