Type: Article
Publication Date: 2012-07-16
Citations: 45
DOI: https://doi.org/10.1145/2332432.2332439
We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary ergodic Markovian dynamic graph process, that is, processes in which the topology of the graph at time t depends only on its topology at time t-1 and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and ergodic.