Epidemic Spread in Networks

Abstract:

We consider the spread of an epidemic over a network using the SIS (susceptible-infected-susceptible) model where healthy nodes are susceptible and can be randomly and independently infected by their infected neighbors, and where infected nodes can randomly recover with a certain probability per unit time, independent of the state of their neighbors. In a network with n nodes, this yields a Markov chain with 2n states. Various n-dimensional approximations to this model have been proposed, where nonlinear state evolution equations are given for the probability that a given node is infected at any given time For these approximate models, we give necessary and sufficient conditions for the epidemic to eventually die out. We also give a formula for the social cost of an epidemic, in terms of the adjacency matrix of the graph and the parameters of the epidemic. Random matrix theory is used to evaluate the social cost for various graph models, such as Erdos-Renyi graphs and random graphs with heavy-tail degree distribution. When the epidemic does not die out, we show that there is a unique fixed point that attracts all points in the state-space except for the origin (i.e., the "all-healthy" state). Finally, we study the true 2n-dimensional Markov-chain and show that the unique stationary point is the all-healthy state. This means that, irrespective of the graph topology and epidemic parameters, the epidemic always dies out. To reconcile this with the results obtained for the approximate models, we show that the approximate models provide an upper bound on the true probability of a node being infected. As a result we show that, when the approximate models are stable and the epidemic dies out, the Markov chain is fast mixing to its stationary state. Conversely, we conjecture that, when the approximate models are unstable, the Markov chain mixes in exponential time, so that for the true model convergence to the all-healthy state is not observed in any reasonable amount of time.