Time to Metastable State in SIS Epidemics on Graphs

Abstract

We define the spreading time in the SIS process as the average time between the start of the outbreak and the time that the number of infected nodes first reaches the average number of infected nodes in the metastable state. We show that the spreading time can be computed using a uniformised embedded Markov chain and give numerical results for the complete graph and the star graph. For the complete graph we derive, using the same method, an analytical expression for the spreading time starting from a single infected node. We show that the spreading time is only significantly larger for a single initially infected than when a few nodes are infected, and scales logarithmically as a function of the network size for a fixed fraction of infected nodes in the metastable state. We also show that mean-field methods predict that the spreading time in regular graphs is independent of the degree. For graphs with a high epidemic threshold, the spreading time is lower than for graphs with a low epidemic threshold. The spreading time seems to be related to the average hop count in the graph. For graphs that have a relatively low average hop count, the spreading time scales logarithmically, but for graphs with a high average hop count, such as the rectangular grid and the ring graph, this is not the case.