Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TPDS.2011.33 | IEEE Transactions on Parallel and Distributed Systems |
Keywords | Field | DocType |
markov processes,graph theory,mobile radio,radio networks,completion time,dynamic graph models,edge existence probability,edge-markovian evolving graphs,fixed transmission radius,flooding mechanism,geometric markovian evolving graphs,independent random walks,information spreading,mobile networks,mobile radio stations,node-expansion properties,square region,stationary markovian evolving graphs,stationary phase,mobile ad hoc networks,flooding,random graphs.,network topology,information analysis,data mining,solid modeling,mobile communication,protocols,upper bound,random walk,dynamic network,titanium,probability density function | Dynamic network analysis,Graph,Markov process,Upper and lower bounds,Computer science,Peer to peer computing,Theoretical computer science,Probability density function,Mobile telephony,Distributed computing | Journal |
Volume | Issue | ISSN |
22 | 9 | 1045-9219 |
Citations | PageRank | References |
41 | 1.42 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Clementi | 1 | 59 | 3.54 |
| Angelo Monti | 2 | 671 | 46.93 |
| Francesco Pasquale | 3 | 421 | 28.22 |
| Riccardo Silvestri | 4 | 1324 | 90.84 |