Epidemic Spread in Complex Networks

Thursday, October 22, 2015 - 3:15pm - 4:05pm
Keller 3-180
Babak Hassibi (California Institute of Technology)
Epidemic models have been extensively studied since a first mathematical formulation was introduced in 1927 by Kermack and McKendrick. Though initially proposed to understand the spread of contagious diseases, the study of epidemics applies to many other areas, such as network security, viral advertising, and information propagation. Questions of interest include the existence of fixed-points, stability (does the epidemic die out), transient behavior, the cost of an epidemic, how best to control an epidemic, etc.

We consider the spread of an epidemic over a network using the SIRS (susceptible-infected-recovered-susceptible) model where healthy nodes are susceptible and can be randomly and independently infected by their infected neighbors, where infected nodes can randomly recover with a certain probability per unit time, and where recovered nodes can again become susceptible after some independent random time. This yields a Markov chain with 3^n states. Ostensibly, because analyzing this Markov chain is too complicated, the O(n)-dimensional mean-field approximation, and its linearization, is often studied instead. We provide the first complete global analysis of the epidemic dynamics of the mean-field approximation. In particular, we show that depending on the largest eigenvalue of the underlying graph adjacency matrix and the ratio of the infection and recovery rates, the global dynamics takes on one of two forms: either the epidemic does out, or it converges to another unique fixed point called the endemic state (where a constant fraction of the nodes remain infected). We further tie in these results with the true underlying Markov chain model and show that the global stability of the mean-field model is related to whether the Markov chain is fast-mixing or not. We also investigate the effect of adding immunization to the SIRS epidemics by introducing two different models, depending on the efficacy of the vaccine. Our results indicate that immunization improves the threshold of epidemic eradication. Furthermore, the common threshold for fast-mixing of the Markov chain and global stability of the disease-free fixed point improves by the same factor for the vaccination-dominant model.
MSC Code: