An Efficient Curing Policy for Epidemics on Graphs
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 <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> nodes. We show that if the budget <inline-formula><tex-math notation="LaTeX">$r$</tex-math></inline-formula> of curing resources available at each time is <inline-formula><tex-math notation="LaTeX">$\Omega (W)$</tex-math></inline-formula> , where <inline-formula> <tex-math notation="LaTeX">$W$</tex-math></inline-formula> is the CutWidth of the graph, and also of order <inline-formula> <tex-math notation="LaTeX">$\Omega (\log\; n)$</tex-math></inline-formula> , then the expected time until the extinction of the epidemic is of order <inline-formula><tex-math notation="LaTeX">$O(n/r)$</tex-math> </inline-formula> , 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 <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> , a sublinear expected time to extinction is possible with a sublinearly increasing budget <inline-formula><tex-math notation="LaTeX">$r$ </tex-math></inline-formula> .