Optimal link removal for epidemic mitigation: A two-way partitioning approach

Eva A. Enns, Jeffrey J. Mounzer, Margaret L. Brandeau

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


The structure of the contact network through which a disease spreads may influence the optimal use of resources for epidemic control. In this work, we explore how to minimize the spread of infection via quarantining with limited resources. In particular, we examine which links should be removed from the contact network, given a constraint on the number of removable links, such that the number of nodes which are no longer at risk for infection is maximized. We show how this problem can be posed as a non-convex quadratically constrained quadratic program (QCQP), and we use this formulation to derive a link removal algorithm. The performance of our QCQP-based algorithm is validated on small Erdo{doubleacute}s-Renyi and small-world random graphs, and then tested on larger, more realistic networks, including a real-world network of injection drug use. We show that our approach achieves near optimal performance and out-performs other intuitive link removal algorithms, such as removing links in order of edge centrality.

Original languageEnglish (US)
Pages (from-to)138-147
Number of pages10
JournalMathematical Biosciences
Issue number2
StatePublished - Feb 2012

Bibliographical note

Funding Information:
The authors thank Dr. John Wylie for providing access to the Winnipeg network dataset. This research was funded by the National Institute on Drug Abuse , Grant No. R01-DA15612 . Eva Enns is supported by a National Defense Science and Engineering Graduate Fellowship , a National Science Foundation Graduate Fellowship , and a Rambus Inc. Stanford Graduate Fellowship . Jeffrey Mounzer is supported by a Cisco Systems Stanford Graduate Fellowship .


  • Epidemic control
  • Link removal
  • Networks
  • Optimization
  • Partitioning
  • Quarantine


Dive into the research topics of 'Optimal link removal for epidemic mitigation: A two-way partitioning approach'. Together they form a unique fingerprint.

Cite this