# Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 16 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread](https://mlsanity.com/paper/1501.06614/) (2015)
- [Optimal Resource Allocation for Network Protection Against Spreading Processes](https://mlsanity.com/paper/1309.6270/) (2013)
- [Optimal Vaccine Allocation to Control Epidemic Outbreaks in Arbitrary Networks](https://mlsanity.com/paper/1303.3984/) (2013)
- [Optimal Containment of Epidemics in Temporal and Adaptive Networks](https://mlsanity.com/paper/1612.06832/) (2016)

## Abstract (arXiv)

The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinINF problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinINFNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of these problems remains generally open. In this paper, we present two bicriteria approximation algorithms for MinINF, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger citekarger:mathor99, and works when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results to tackle the MinINFNode problem.