Name
Abstract | ||
|---|---|---|
We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p. Such evolving graph model is a wide generalization of time-independent dynamic random graphs [6] and will be called edge-Markovian dynamic graphs. We investigate the speed of information dissemination in such dynamic graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide: i) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial probability distribution. ii) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time does not asymptotically depend on the edge death-rate q. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1400751.1400781 | PODC |
Keywords | Field | DocType |
edge death-rate q,edge death-rate,arbitrary initial edge probability,probabilities p,tight characterization,dynamic graph,completion time,time step,edge-markovian dynamic graph,edge birth-rate,markov processes,random graphs,probability distribution,random graph,flooding,markov process | Random regular graph,Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Random graph,Chordal graph,Probability distribution,Pathwidth,1-planar graph,Mathematics,Distributed computing | Conference |
Citations | PageRank | References |
61 | 2.77 | 12 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E.F. Clementi | 1 | 61 | 2.77 |
| Claudio Macci | 2 | 99 | 6.66 |
| Angelo Monti | 3 | 671 | 46.93 |
| Francesco Pasquale | 4 | 421 | 28.22 |
| Riccardo Silvestri | 5 | 1324 | 90.84 |