A Caltech Library Service

Improved bounds on the epidemic threshold of exact SIS models on complex networks

Azizan Ruhi, Navid and Thrampoulidis, Christos and Hassibi, Babak (2016) Improved bounds on the epidemic threshold of exact SIS models on complex networks. In: IEEE 55th Conference on Decision and Control (CDC). IEEE , Piscataway, NJ, pp. 3560-3565. ISBN 978-1-5090-1837-6.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The SIS (susceptible-infected-susceptible) epidemic model on an arbitrary network, without making approximations, is a 2^n-state Markov chain with a unique absorbing state (the all-healthy state). This makes analysis of the SIS model and, in particular, determining the threshold of epidemic spread quite challenging. It has been shown that the exact marginal probabilities of infection can be upper bounded by an n-dimensional linear time-invariant system, a consequence of which is that the Markov chain is “fast-mixing” when the LTI system is stable, i.e. when β/δ < 1/(λ_(max)(A)) (where β is the infection rate per link, δ is the recovery rate, and λ_(max)(A) is the largest eigenvalue of the network's adjacency matrix). This well-known threshold has been recently shown not to be tight in several cases, such as in a star network. In this paper, we provide tighter upper bounds on the exact marginal probabilities of infection, by also taking pairwise infection probabilities into account. Based on this improved bound, we derive tighter eigenvalue conditions that guarantee fast mixing (i.e., logarithmic mixing time) of the chain. We demonstrate the improvement of the threshold condition by comparing the new bound with the known one on various networks with various epidemic parameters.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Azizan Ruhi, Navid0000-0002-4299-2963
Additional Information:© 2016 IEEE. This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
JPL President and Director's FundUNSPECIFIED
King Abdulaziz UniversityUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Subject Keywords:Markov processes, Silicon, Analytical models, Eigenvalues and eigenfunctions, Upper bound, Complex networks, Diseases
Record Number:CaltechAUTHORS:20170106-135044789
Persistent URL:
Official Citation:N. A. Ruhi, C. Thrampoulidis and B. Hassibi, "Improved bounds on the epidemic threshold of exact SIS models on complex networks," 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, USA, 2016, pp. 3560-3565. doi: 10.1109/CDC.2016.7798804 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73309
Deposited By: George Porter
Deposited On:06 Jan 2017 23:05
Last Modified:03 Oct 2019 16:26

Repository Staff Only: item control page