Information Spreading in Dynamic Graphs

摘要

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. Under general conditions, we bound the flooding time in terms of the mixing time of the dynamic graph process. We recover, as special cases of our result, bounds on the flooding time for the random trip model and the random path models; previous analysis techniques provided bounds only in restricted settings for such models. Our result also provides the first bound for the random waypoini model (which is tight for the most realistic ranges of network parameters) whose analysis had been an important open question.