Analysis of the survival time of the SIRS process via expansion.


We study the SIRS process—a continuous-time Markov chain modelling thespread of infections on graphs. In this model, vertices are eithersusceptible, infected, or recovered. Each infected vertex becomesrecovered at rate 1 and infects each of its susceptible neighbors independently at rate~$\lambda$, and each recovered vertex becomes susceptible at a rate~$\rho$, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behaviour of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph.

Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of~$\lambda$. This behaviour is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs $G$ with $n$ vertices, degree close to $d$, and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in $n$ when $\lambda \geq c/d$ for a constant $c > 1$. Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if $G$ is a subgraph. Notably, our result implies an almost-tight threshold for Erdos–Rényi graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.

Date: Jun 19, 2024 at 15:00:00 h
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Andreas Göbel
Affiliation: University of Potsdam, Alemania
Coordinator: José Verschae
More info at:
Event website

Posted on Jun 18, 2024 in ACGO, Seminars