2 Aprile 2009: INFORMATION SPREADING IN EVOLVING NETWORKS (Andrea Clementi)

Il prossimo incontro di \Piz^2@TV(+IAC) si terrà il 2 aprile, sempre alle ore 13, presso il Dipartimento di Matematica di Roma Tor Vergata, aula "Dal Passo", sarà animato da Andrea Clementi (Dipartimento di Matematica, Universita' degli Studi di Roma TOR VERGATA) e avrà come titolo "INFORMATION SPREADING IN EVOLVING NETWORKS"

Summary: There is a strong and increasing interest in the study of Evolving Networks. Evolving Networks are graphs that change their topology with time. Such dynamic systems arise from several areas such as computer networks, citation networks, peer-to-peer networks, social networks, and mobile networks.

A first major issue here is that of finding abstract models that well approximate some concrete
important features of realistic scenarios. On the other hand, ''high''-realistic models are too hard to study from an analytical point of view. Finding the right trade-off between these two aspects
is a key-ingredient in this emerging research field.

A good model of Evolving Networks is then used to analyze the phenomenon of Information Spreading. This is typically performed by studying basic communication primitives (such as broadcasting and gossiping) over such dynamic structures.

In this talk, after providing the basic concepts of Evolving Networks, some recent theoretical
advances on this topic will be presented. In particular, a simple and elegant Markovian model of
Evolving Networks will be introduced and, then, some tight bounds on the Flooding Time will be
given.

Such bounds provide a strong analytical evidence of an interesting phenomenon that was previously observed from an experimental point of view only: (random) dynamicity helps Information Spreading rather than being a hurdle.

Finally, some interesting future research directions will be discussed.

=======BIBLIOGRAFIA==============
This talk mainly relies on concepts and results presented in the following works:

- Clementi A., Monti A., Pasquale F., and Silvestri R. (2007) Broadcasting in Dynamic Radio Networks. Journal of Computer and System Sciences 74(4), 2009 (Preliminary version in Proc. of Annual 26th ACM/SIGACTS Principles Of Distributed Computing 2007).

- Clementi A., Macci C., Monti A., Pasquale F., and Silvestri R. (2008) Flooding Time of Edge-Markovian Evolving Graphs. Proc. of Annual 27th ACM/SIGACTS Principles of Distributed Computing 2008.