In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where p = Ω(1/n) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when p ≪ log n/n ). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and p = Θ (1/n) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism. © 2013 Springer-Verlag.

Rumor Spreading in Random Evolving Graphs / Andrea, Clementi; Pierluigi, Crescenzi; Carola, Doerr; Pierre, Fraigniaud; Isopi, Marco; Panconesi, Alessandro; Pasquale, Francesco; Silvestri, Riccardo. - STAMPA. - 8125:(2013), pp. 325-336. (Intervento presentato al convegno 21st Annual European Symposium on Algorithms, ESA 2013 tenutosi a Sophia Antipolis, France) [10.1007/978-3-642-40450-4_28].

Rumor Spreading in Random Evolving Graphs

ISOPI, Marco;PANCONESI, Alessandro;PASQUALE, FRANCESCO;SILVESTRI, RICCARDO
2013

Abstract

In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where p = Ω(1/n) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when p ≪ log n/n ). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and p = Θ (1/n) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism. © 2013 Springer-Verlag.
2013
21st Annual European Symposium on Algorithms, ESA 2013
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Rumor Spreading in Random Evolving Graphs / Andrea, Clementi; Pierluigi, Crescenzi; Carola, Doerr; Pierre, Fraigniaud; Isopi, Marco; Panconesi, Alessandro; Pasquale, Francesco; Silvestri, Riccardo. - STAMPA. - 8125:(2013), pp. 325-336. (Intervento presentato al convegno 21st Annual European Symposium on Algorithms, ESA 2013 tenutosi a Sophia Antipolis, France) [10.1007/978-3-642-40450-4_28].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/11573/530139
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact