# Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread

arXiv: https://arxiv.org/abs/1501.06614 · HTML: https://mlsanity.com/paper/1501.06614/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2015.

## Built on by (most cited first, 8 of 8)

- [Active Screening for Recurrent Diseases: A Reinforcement Learning Approach](https://mlsanity.com/paper/2101.02766/) (2021)
- [Rewiring What-to-Watch-Next Recommendations to Reduce Radicalization Pathways](https://mlsanity.com/paper/2202.00640/) (2022)
- [Disentangling the Spectral Properties of the Hodge Laplacian: Not All Small Eigenvalues Are Equal](https://mlsanity.com/paper/2311.14427/) (2023)
- [Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting](https://mlsanity.com/paper/2402.18697/) (2024)
- [Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks](https://mlsanity.com/paper/2202.08296/) (2022)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control](https://mlsanity.com/paper/2506.15397/) (2025)
- [Network World Models as Environments for Algorithm Design on Complex Systems](https://mlsanity.com/paper/2610.01048/) (2026)

## Abstract (arXiv)

The largest eigenvalue of the adjacency matrix of a network (referred to as the spectral radius) is an important metric in its own right. Further, for several models of epidemic spread on networks (e.g., the `flu-like' SIS model), it has been shown that an epidemic dies out quickly if the spectral radius of the graph is below a certain threshold that depends on the model parameters. This motivates a strategy to control epidemic spread by reducing the spectral radius of the underlying network. In this paper, we develop a suite of provable approximation algorithms for reducing the spectral radius by removing the minimum cost set of edges (modeling quarantining) or nodes (modeling vaccinations), with different time and quality tradeoffs. Our main algorithm, textscGreedyWalk, is based on the idea of hitting closed walks of a given length, and gives an O(log2n)-approximation, where n denotes the number of nodes; it also performs much better in practice compared to all prior heuristics proposed for this problem. We further present a novel sparsification method to improve its running time. In addition, we give a new primal-dual based algorithm with an even better approximation guarantee (O(log n)), albeit with slower running time. We also give lower bounds on the worst-case performance of some of the popular heuristics. Finally we demonstrate the applicability of our algorithms and the properties of our solutions via extensive experiments on multiple synthetic and real networks.