When is a network epidemic hard to eliminate?
From MaRDI portal
Publication:2976137
DOI10.1287/MOOR.2016.0792zbMATH Open1362.92073arXiv1510.06054OpenAlexW2227599708WikidataQ111475515 ScholiaQ111475515MaRDI QIDQ2976137FDOQ2976137
Authors: Kimon Drakopoulos, Asuman Ozdaglar, John N. Tsitsiklis 
Publication date: 13 April 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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. 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 the latter with our prior work establishes a fairly sharp phase transition on the expected time to extinction (sub-linear versus exponential) based on the relation between the CutWidth and the curing budget.
Full work available at URL: https://arxiv.org/abs/1510.06054
Recommendations
- Optimal curing policy for epidemic spreading over a community network with heterogeneous population
- How to distribute antidote to control epidemics
- Optimal curing resource allocation for epidemic spreading processes
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
Cites Work
- Recontamination does not help to search a graph
- Monotonicity in graph searching
- An optimal control model for ebola virus disease
- Identifying Influential and Susceptible Members of Social Networks
- How to distribute antidote to control epidemics
- Distributing antidote using PageRank vectors
- Designing a contact process: the piecewise-homogeneous process on a finite set with applications
Cited In (9)
- How to distribute antidote to control epidemics
- An efficient dynamic allocation mechanism for security in networks of interdependent strategic agents
- Diffusion in Random Networks: Impact of Degree Distribution
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Termination of the ice bucket challenge
- Optimal curing rate allocation in the SIS epidemic model
- A Metric Space for Point Process Excitations
- Initialization and curing policies for Pólya contagion networks
This page was built for publication: When is a network epidemic hard to eliminate?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976137)
