Article ID: | iaor2017613 |
Volume: | 42 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 14 |
Publication Date: | Jan 2017 |
Journal: | Mathematics of Operations Research |
Authors: | Ozdaglar Asuman, Tsitsiklis John N, Drakopoulos Kimon |
Keywords: | security, simulation, graphs, health services, medicine |
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