We study epidemic spreading according to a emph{Susceptible-Infectious-Recovered} (for short, emph{SIR}) network model known as the {em Reed-Frost} model, and we establish sharp thresholds for two generative models of {em one-dimensional small-world graphs}, in which graphs are obtained by adding random edges to a cycle. In $3$-regular graphs obtained as the union of a cycle and a random perfect matching, we show that there is a sharp threshold at $.5$ for the contagion probability along edges. In graphs obtained as the union of a cycle and of a $mathcal{G}_{n,c/n}$ ErdH{o}s-Renyi random graph with edge probability $c/n$, we show that there is a sharp threshold $p_c$ for the contagion probability: the value of $p_c$ turns out to be $sqrt 2 -1approx .41$ for the sparse case $c=1$ yielding an expected node degree similar to the random $3$-regular graphs above. In both models, below the threshold we prove that the infection only affects $mathcal{O}(log n)$ nodes, and that above the threshold it affects $Omega(n)$ nodes. These are the first fully rigorous results establishing a phase transition for SIR models (and equivalent percolation problems) in small-world graphs. Although one-dimensional small-world graphs are an idealized and unrealistic network model, a number of realistic qualitative phenomena emerge from our analysis, including the spread of the disease through a sequence of local outbreaks, the danger posed by random connections, and the effect of super-spreader events.
Download