When Is a Network Epidemic Hard to Eliminate?
Open Access
- 1 January 2017
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 42 (1) , 1-14
Abstract
We consider the propagation of a contagion process (“epidemic”) on a network and study the problem of dynamically allocating a fixed curing budget to the nodes of the graph, at each time instant. For bounded degree graphs, we provide a lower bound on the expected time to extinction under any such dynamic allocation policy, in terms of a combinatorial quantity that we call the resistance of the set of initially infected nodes, the available budget, and the number of nodes n. Specifically, we consider the case of bounded degree graphs, with the resistance growing linearly in n. We show that if the curing budget is less than a certain multiple of the resistance, then the expected time to extinction grows exponentially with n. As a corollary, if all nodes are initially infected and the CutWidth of the graph grows linearly, while the curing budget is less than a certain multiple of the CutWidth, then the expected time to extinction grows exponentially in n. The combination of the latter with our prior work establishes a fairly sharp phase transition on the expected time to extinction (sublinear versus exponential) based on the relation between the CutWidth and the curing budget.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- An Efficient Curing Policy for Epidemics on GraphsIEEE Transactions on Network Science and Engineering, 2015
- Estimating Social Network Structure and Propagation Dynamics for an Infectious DiseaseLecture Notes in Computer Science, 2014
- Identifying Influential and Susceptible Members of Social NetworksScience, 2012
- How to distribute antidote to control epidemicsRandom Structures & Algorithms, 2010
- Distributing Antidote Using PageRank VectorsInternet Mathematics, 2009
- The dynamics of viral marketingACM Transactions on the Web, 2007
- Designing a contact process: the piecewise-homogeneous process on a finite set with applicationsStochastic Processes and their Applications, 2005
- Efficient Immunization Strategies for Computer Networks and PopulationsPhysical Review Letters, 2003
- Recontamination does not help to search a graphJournal of the ACM, 1993
- Monotonicity in graph searchingJournal of Algorithms, 1991