Epidemic Spread in Networks
November 15, 2013, Webb 1100
Babak Hassibi
CalTech, Electrical Engineering
Abstract
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 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. This yields a Markov chain with 2^n states. Ostensibly, because analyzing this Markov chain is too complicated,
various n-dimensional linear and non-linear approximations have been proposed. Using the linear model, we use random matrix theory to quantify the "social cost" of an epidemic, a useful metric that can be used to control an epidemic with minimal cost. We show that the degree distribution of the underlying graph plays a key role in the social cost. For the nonlinear models, we provide the first complete global analysis of
the epidemic dynamics. 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 (where a constant fraction of the nodes remain infected). Finally, we tie in these results with the "true" underlying Markov chain model and show that the global stability of the n-dimensional pproximate models is related to whether the Markov chain is "fast-mixing" or not. We will discuss the implications of these results.
Joint work with Hyung-Jun Ahn, Subhonmesh Bode and Elizabeth Bodine-Baron
Speaker's Bio
Babak Hassibi is the Gordon M Binder/Amgen Professor and Executive Officer of Electrical Engineering at Caltech. He obtained his PhD from
Stanford University and prior to Caltech was with the Mathematical Sciences Research Center at Bell Laboratories. His research interests span communications, control and signal processing. Among other awards, he is the recipient of the Presidential Early Career Award for Scientists and Engineers and the David and Lucille Packard Fellowship in Science and Engineering.