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.

Clementi, A., Monti, A., Pasquale, F., Silvestri, F. (2011). Information spreading in stationary Markovian evolving graphs. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 22(9), 1425-1432 [10.1109/TPDS.2011.33].

Information spreading in stationary Markovian evolving graphs

CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2011-09-01

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.
1-set-2011
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Con Impact Factor ISI
mobile ad hoc networks; Markov chains; information spreading; random evolving graphs
Full version del paper in IEEE IPDPS 2009. N. di citazioni (versioni rivista+articolo) su Google Scholar al 22/11/15: 74
Clementi, A., Monti, A., Pasquale, F., Silvestri, F. (2011). Information spreading in stationary Markovian evolving graphs. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 22(9), 1425-1432 [10.1109/TPDS.2011.33].
Clementi, A; Monti, A; Pasquale, F; Silvestri, F
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
CMPS-MEG-100428-full.pdf

accesso aperto

Licenza: Non specificato
Dimensione 435.81 kB
Formato Adobe PDF
435.81 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/18932
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 60
  • ???jsp.display-item.citation.isi??? 44
social impact