Analysis and control of contagion processes on networks
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/105663 |
| _version_ | 1811097889136443392 |
|---|---|
| author | Drakopoulos, Kimon |
| author2 | Asuman Ozdaglar and John N. Tsitsiklis. |
| author_facet | Asuman Ozdaglar and John N. Tsitsiklis. Drakopoulos, Kimon |
| author_sort | Drakopoulos, Kimon |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T17:06:34Z |
| format | Thesis |
| id | mit-1721.1/105663 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:06:34Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1056632019-04-12T17:45:13Z Analysis and control of contagion processes on networks Drakopoulos, Kimon Asuman Ozdaglar and John N. Tsitsiklis. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. Cataloged from PDF version of thesis. Includes bibliographical references (pages 137-141). 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 Q(W), where W is the CutWidth of the graph, and also of order [omega](log n), 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 sublinearly with n, a sublinear expected time to extinction is possible with only a sublinearly increasing budget r. In contrast, we provide a lower bound on the expected time to extinction under any such dynamic allocation policy, for bounded degree graphs, 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 in n, 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. Finally, in the empirical part of the thesis, we analyze data on the evolution and propagation of influenza across the United States and discover that compartmental epidemic models enriched with environment dependent terms have fair prediction accuracy, and that the effect of inter-state traveling is negligible compared to the effect of intra-state contacts. by Kimon Drakopoulos. Ph. D. 2016-12-05T19:57:02Z 2016-12-05T19:57:02Z 2016 2016 Thesis http://hdl.handle.net/1721.1/105663 964446754 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 141 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Drakopoulos, Kimon Analysis and control of contagion processes on networks |
| title | Analysis and control of contagion processes on networks |
| title_full | Analysis and control of contagion processes on networks |
| title_fullStr | Analysis and control of contagion processes on networks |
| title_full_unstemmed | Analysis and control of contagion processes on networks |
| title_short | Analysis and control of contagion processes on networks |
| title_sort | analysis and control of contagion processes on networks |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/105663 |
| work_keys_str_mv | AT drakopouloskimon analysisandcontrolofcontagionprocessesonnetworks |