An Efficient Curing Policy for Epidemics on Graphs

Author

Drakopoulos, Kimon ; Ozdaglar, Asuman ; Tsitsiklis, John N.

Author_Institution

Laboratory of Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA

Volume

1

Issue

2

fYear

2014

fDate

July-Dec. 1 2014

Firstpage

67

Lastpage

75

Abstract

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 $\\Omega (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 only sublinearly with $n$

, a sublinear expected time to extinction is possible with a sublinearly increasing budget $r$

.

Keywords

Contagious diseases; Curing rates; Diseases; Epidemics; Graph theory; Networks; Process control; Resource management; Time measurement; Networks; contagion; control; epidemics; influence minimization;

fLanguage

English

Journal_Title

Network Science and Engineering, IEEE Transactions on

Publisher

ieee

ISSN

2327-4697

Type

jour

DOI

10.1109/TNSE.2015.2393291

Filename

7010945