Information Spreading in Stationary Markovian Evolving Graphs

Details Information Spreading in Stationary Markovian Evolving Graphs Information Spreading in Stationary Markovian Evolving Graphs

2011-03-03

arxiv.org/abs/1103.0741v1

Computer Science

Discrete Mathematics

16 pages

Scientific paper

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the "stationary phase" by analyzing the completion time of the "flooding mechanism". We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. "Geometric Markovian evolving graphs" where the Markovian behaviour is yielded by "n" mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. "Edge-Markovian evolving graphs" where the probability of existence of any edge at time "t" depends on the existence (or not) of the same edge at time "t-1". In both cases, the obtained upper bounds hold "with high probability" and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.

Affiliated with

Also associated with

No associations

Rating

Information Spreading in Stationary Markovian Evolving Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Information Spreading in Stationary Markovian Evolving Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information Spreading in Stationary Markovian Evolving Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-589917