M.Sc Thesis

M.Sc StudentTennenholtz Guy
SubjectSequential Vaccination of Epidemics in Networks
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Shie Mannor


The dynamics of infectious diseases spread is crucial in determining their risk and

offering ways to contain them. We study sequential vaccination of individuals in networks.

In the original (deterministic) version of the Firefighter problem, a fire breaks

out at some node of a given graph. At each time step, b nodes can be protected by

a firefighter and then the _re spreads to all unprotected neighbors of the nodes on

fire. The process ends when the fire can no longer spread. We extend the Firefighter

problem to a probabilistic setting, where the infection is stochastic. We devise a simple policy that only vaccinates neighbors of infected nodes and is optimal on regular trees and on general graphs for a sufficiently large budget. We derive methods for calculating upper and lower bounds of the expected number of infected individuals, as well as provide estimates on the budget needed for containment in expectation.

We calculate these explicitly on trees, d-dimensional grids, and Erdos Renyi graphs.

Finally, we construct a state-dependent budget allocation strategy and demonstrate

its superiority over constant budget allocation on real networks following a first order

acquaintance vaccination policy. Our work is a first step towards the design of networks that have built-in resilience by design.