*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Control of contagion processes on networks
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. We provide a dynamic policy for the rapid containment of a contagion process modeled as an SIS epidemic on a bounded degree undirected graph with n nodes. We show that if the budget r of curing resources available at each time is Ω(W), where W is the CutWidth of the graph, and also of order Ω(logn), then the expected time until the extinction of the epidemic is of order O(n/r), which is within a constant factor from optimal, as well as sublinear in the number of nodes. Furthermore, if the CutWidth increases only sublinearly with n, a sublinear expected time to extinction is possible with a sublinearly increasing budget r.
In contrast, 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 these two results 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.
Bio
Kimon Drakopoulos (M’13) received the diploma in electrical and computer engineering from the National Technical University of Athens, Athens, Greece, in 2009 and the M.Sc. degree in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, MA, in 2011. From 2011 to present, he is a Ph.D. candidate at the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge,
MA. His current research interests include social network analysis, network science,
applied probability, game theory and network economics.
