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. We consider epidemic spread over a network using the SIS (susceptible-infected-susceptible) model which yields a Markov chain with 2^n states. Ostensibly, because analyzing this Markov chain is difficult, various n-dimensional linear and non-linear approximations have been proposed. We use the linear model to quantify the "social cost" of an epidemic. For the nonlinear models, we provide the first complete global analysis and show that there always exists a single stable fixed point. Finally, we tie in these results with the "true" underlying Markov chain and whether it is "fast-mixing" or not.