The study of spreading phenomena in networks, in particular the spread of disease, has attracted considerable research interest. Biological diseases spread through contacts between individuals, and the patterns of these contacts can be represented as networks. Similar phenomena are also observed in other kinds of networks, for example, computer viruses spreading on the Internet, rumors spreading in a social network, and financial attacks propagating among banks. Containing an epidemic early is important, since containment becomes difficult after an epidemic has spread to a large fraction of the population in the contact network. In this dissertation, we show that the outbreak of an epidemic can be effectively contained and suppressed in a small subnetwork by a combination of two measures: antidote distribution, providing antidotes to nodes in the subnetwork, and partial quarantine, which is equivalent to removing part of the boundary edges of the subnetwork. Our containment strategy improves over existing antidote distribution schemes based on personalized PageRank in two ways. First, we replace the constraint on the topology of this subnetwork described by Chung et al., that a large fraction of the value of the personalized PageRank vector must be contained in the local cluster, with a partial quarantine scheme. We obtain this result by using the properties of personalized PageRank to devise the partial quarantine scheme, which optimizes the tradeoff between successful containment and interference with the network topology. Second, we derive a new lower bound on the amount of antidote required to achieve successful containment. We prove that, under our antidote distribution scheme, the probability of the infection spreading to the whole network is bounded, and that the infection inside the subnetwork will disappear after a period that is proportional to the logarithm of the number of initially infected nodes. Thus, we find that an epidemic can be effectively contained and suppressed in the small subnetwork in which the outbreak was detected, under weaker conditions than those proposed in earlier research, after our containment strategy is implemented. We demonstrate the effectiveness of our strategy with numerical simulations of epidemics on benchmark networks. We also test our strategy on two examples of epidemics in real-world networks, one in a network of YouTube users, and another in a network of autonomous systems in the Internet. Our strategy is dependent only on the rate of infection, the rate of recovery, and the topology around the initially infected nodes, and is independent of the rest of the network.
If you are a member of the WashU community, login with your WUSTL Key to interact with events, personalize your calendar, and get recommendations.Login with WUSTL Key
If you are not a member of the WashU community, please login via one of the options below to interact with our calendar.