Graphs that evolve over time are currently one of the most studied topics in computer science. These dynamic structures arise from several areas such as computer networks, network of users exchanging e-mail or instant messages, peer-to-peer networks, social networks, and many other more.

In this talk, we introduce stochastic time-dependency in evolving networks by considering graphs with edges change according to a Markovian process. Such evolving graph model is a wide generalization of time-independent dynamic randomgraphs  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 the probability parameters) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes.

Interestingly enough, the above bounds are obtained via a new, ''dynamic'' version of node-expansion properties of random graphs.


Joint work with Claudio Macci, Angelo Monti, Francesco Pasquale and Riccardo Silvestri.