  We study the spread of discrete-time epidemics over arbitrary networks for
well-known propagation models, namely SIS (susceptible-infected-susceptible),
SIR (susceptible-infected-recovered), SIRS
(susceptible-infected-recovered-susceptible) and SIV
(susceptible-infected-vaccinated). Such epidemics are described by $2^n$- or
$3^n$-state Markov chains. Ostensibly, because analyzing such Markov chains is
too complicated, their $O(n)$-dimensional nonlinear "mean-field" approximation,
and its linearization, are often studied instead. We provide a complete global
analysis of the epidemic dynamics of the nonlinear mean-field approximation. In
particular, we show that depending on the largest eigenvalue of the underlying
graph adjacency matrix and the rates of infection, recovery, and vaccination,
the global dynamics takes on one of two forms: either the epidemic dies out, or
it converges to another unique fixed point (the so-called endemic state where a
constant fraction of the nodes remain infected). A similar result has also been
shown in the continuous-time case. We tie in these results with the "true"
underlying Markov chain model by showing that the linear model is the tightest
upper-bound on the true probabilities of infection that involves only
marginals, and that, even though the nonlinear model is not an upper-bound on
the true probabilities in general, it does provide an upper-bound on the
probability of the chain not being absorbed. As a consequence, we also show
that when the disease-free fixed point is globally stable for the mean-field
model, the Markov chain has an $O(\log n)$ mixing time, which means the
epidemic dies out quickly. We compare and summarize the results on different
propagation models.
