An efficient curing policy for epidemics on graphs

2014/07/07 by Kimon Drakopoulos, Asuman Ozdaglar, Drakopoulos, Kimon +3 · 3 citations
Mathematics · Physics and Astronomy · #COVID-19 epidemiological studies #Complex Network Analysis Techniques #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1407.2241

openalex publication_date 2014/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Ω(W), where W is the CutWidth of the graph, and also of order Ω(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.

Cited by

• A Quantum-Compliant Formulation for Network Epidemic Control
• A Quantum Approach for Optimal Transient Control in Network-Based Epidemic Models
• Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control

Related

• A lower bound on the performance of dynamic curing policies for epidemics on graphs
• When is a network epidemic hard to eliminate?
• Dynamic Curing and Network Design in SIS Epidemic Processes
• Curing Epidemics on Networks using a Polya Contagion Model
• Optimal curing policy for epidemic spreading over a community network\n with heterogeneous population