When is a network epidemic hard to eliminate?

DOI10.1287/MOOR.2016.0792MaRDI QIDQ2976137zbMATH OpenOpenAlexWikidataFDO

Authors Kimon Drakopoulos, Asuman Ozdaglar, John N. Tsitsiklis

Publication date 13 April 2017

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.06054, http://hdl.handle.net/1721.1/111028

zbMATH Keywords

networksepidemicscontact processcontagion process

Mathematics Subject Classification ID

Epidemiology (92D30) Applications of graph theory (05C90) Social networks; opinion dynamics (91D30)

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.

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

• An optimal control model for ebola virus disease
• Designing a contact process: the piecewise-homogeneous process on a finite set with applications
• Distributing antidote using PageRank vectors
• How to distribute antidote to control epidemics
• Identifying Influential and Susceptible Members of Social Networks
• Monotonicity in graph searching
• Recontamination does not help to search a graph

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)