Epidemic extinction in networks: insights from the 12 110 smallest graphs

We investigate the expected time to extinction in the susceptible-infectious-susceptible model of disease spreading. Rather than using stochastic simulations, or asymptotic calculations in network models, we solve the extinction time exactly for all connected graphs with three to eight vertices. This approach enables us to discover descriptive relations that would be impossible with stochastic simulations. It also helps us discovering graphs and configurations of S and I with anomalous behaviors with respect to disease spreading. We find that for large transmission rates the extinction time is independent of the configuration, just dependent on the graph. In this limit, the number of vertices and edges determine the extinction time very accurately (deviations primarily coming from the fluctuations in degrees). We find that the rankings of configurations with respect to extinction times at low and high transmission rates are correlated at low prevalences and negatively correlated for high prevalences. The most important structural factor determining this ranking is the degrees of the infectious vertices.

• Publication year

  2018

• Venue

  New Journal of Physics

• Publication date

  2018-02-24

• Fields of study

  Biology, Mathematics, Physics, Environmental Science

• Identifiers
  DOI 10.1088/1367-2630/aaf016arXiv 1802.08849
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Time to Extinction for the SIS Epidemic Model: New Bounds on the Tail Probabilities

  2019cited by this paper
• Corrigendum to “Random walks and diffusion on networks” [Phys. Rep. 716–717 (2017) 1–58]

  2018cited by this paper
• Mathematics of Epidemics on Networks: From Exact to Approximate Models

  2017cited by this paper
• Three faces of node importance in network epidemiology: Exact results for small graphs

  2017cited by this paper
• Ranking of Nodal Infection Probability in Susceptible-Infected-Susceptible Epidemic

  2017cited by this paper
• Epidemic extinction paths in complex networks.

  2017cited by this paper
• The transmission process: A combinatorial stochastic process for the evolution of transmission trees over networks.

  2016cited by this paper
• Building blocks of the basin stability of power grids.

  2016cited by this paper
• Random walks and diffusion on networks

  2016cited by this paper
• Effective distances for epidemics spreading on complex networks

  2016cited by this paper
• Shadows of the susceptible-infectious-susceptible immortality transition in small networks.

  2015cited by this paper
• Epidemic processes in complex networks

  2014cited by this paper
• What is network science?

  2013cited by this paper
• Practical graph isomorphism, II

  2013cited by this paper
• - Electronic Supplementary Material-Optimizing surveillance for livestock disease spreading through animal movements

  2012cited by this paper
• First passage time for random walks in heterogeneous networks.

  2012cited by this paper
• Exact epidemic models on graphs using graph-automorphism driven lumping

  2010cited by this paper
• Networks: An Introduction

  2010cited by this paper
• Fast Library for Number Theory: An Introduction

  2010cited by this paper
• Stochastic models of population extinction.

  2010cited by this paper
• Predicting extinction rates in stochastic epidemic models

  2009cited by this paper
• Directionality of contact networks suppresses selection pressure in evolutionary dynamics.

  2008cited by this paper
• Asymptotics of rare events in birth–death processes bypassing the exact solutions

  2007cited by this paper
• The igraph software package for complex network research

  2006cited by this paper
• Centrality Indices

  2004cited by this paper
• An Improved Algorithm for Matching Large Graphs

  2001cited by this paper
• Extinction and quasi-stationarity in the Verhulst logistic model.

  2001cited by this paper
• The Mathematics of Infectious Diseases

  2000cited by this paper
• Epidemic Modelling: An Introduction

  1999cited by this paper
• Determinants and current flows in electric networks

  1992cited by this paper
• The exact solution of systems of linear equations with polynomial coefficients

  1971cited by this paper
• The theory of matrices

  1969cited by this paper
• A Computer Method for Calculating Kendall's Tau with Ungrouped Data

  1966cited by this paper

• Analysis of continuous-time Markovian ɛ-SIS epidemics on networks.

  2022cites this paper
• Susceptible-infected-susceptible model of disease extinction on heterogeneous directed population networks.

  2022cites this paper
• Mean Extinction Times of Epidemics with State-Dependent Infectiousness

  2021cites this paper
• Statistical analysis of tipping pathways in agent-based models

  2021cites this paper
• Influence of individual nodes for continuous-time Susceptible-Infected-Susceptible dynamics on synthetic and real-world networks

  2021cites this paper
• Dimension-reduction of dynamics on real-world networks with symmetry

  2021cites this paper
• Expected Extinction Times of Epidemics With State-Dependent Infectiousness

  2021cites this paper
• How network properties and epidemic parameters influence stochastic SIR dynamics on scale-free random networks

  2020cites this paper
• Degree Dispersion Increases the Rate of Rare Events in Population Networks

  2019cites this paper
• Influential spreaders for recurrent epidemics on networks

  2019cites this paper
• Exact analysis of summary statistics for continuous-time discrete-state Markov processes on networks using graph-automorphism lumping

  2019cites this paper
• A General Model of Dynamics on Networks with Graph Automorphism Lumping

  2018cites this paper