On an epidemic model on finite graphs

Itai Benjamini, Luiz Renato Fontes, Jonathan Hermon, Fabio Prates Machado

Published 2016-10-14Version 1

We study a system of random walks, known as the frog model, starting from an independent Poisson($\lambda$) particle's profile with one additional active particle planted at some vertex $\mathbf{o}$ of a finite connected simple graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Initially, only the particles occupying $\mathbf{o}$ are active. Active particles perform $t \in \mathbb{N} \cup \{\infty \}$ steps of the walk they picked before vanishing and activate all inactive particles they hit. This system is often taken as a model for the spread of an epidemic over a population. Let $\mathcal{R}_t$ be the set of vertices which are visited by the process, when active particles vanish after $t$ steps. We study the susceptibility of the process on the underlying graph, defined as the random quantity $\mathcal{S}(\mathcal{G}):=\inf \{t:\mathcal{R}_t=\mathcal{V} \}$, the time it takes for the entire population get infected. We consider the cases that the underlying graph is either a regular expander or a $d$-dimensional torus of side length $n$ (for all $d \ge 1$) and determine asymptotic bounds for $\mathcal{S} $ up to a constant factor.