Reed-Frost Transition on Dense Graphs

The classic Reed-Frost stochastic epidemic process on a population of $n$ elements with probability p can be viewed as a percolation on a complete graph with a given number of initially infective vertices. At each step each infected vertex infects an undeleted and uninfected vertex independently with probability $p$, and all previously infected vertices are removed. The process stops if there is no new infected vertex. The percolation time is the time $t$ when all vertices have been infected or $+\infty$.

In this talk, we extend the the Reed-Frost process from complete graphs to general graphs and obtain a few sufficient conditions on the density of graphs and probability such that with high probability that the percolation time is bounded above by a constant. We also notice that these conditions are best possible in some sense.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.