MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Ultra-Fast Rumor Spreading in Models of Real-World Networks

Konstantinos Panagiotou
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 5, AG 4, MMCI  
AG Audience
English

Date, Time and Location

Friday, 15 April 2011
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We analyze the popular push-pull protocol for spreading a rumor on networks.

Initially, a single node knows of a rumor. In each succeeding round, every node
chooses a random neighbor, and the two nodes share the rumor if one of them is
already aware of it. We present the first theoretical analysis of this protocol
on two models of random graphs that have a power law degree distribution with
an arbitrary exponent $\beta > 2$. In particular, we study preferential
attachment graphs and random graphs with a given expected degree sequence.

Our main findings reveal a striking dichotomy in the performance of the
protocol that depends on the exponent of the power law. More specifically, we
show that if $2 < \beta < 3$, then the rumor spreads to almost all nodes in
$\Theta(\log\log n)$ rounds with high probability. This is \emph{exponentially}
faster than all previously known upper bounds for the push-pull protocol
established for various classes of networks. On the other hand, if $\beta > 3$,
then~$\Omega(\log n)$ rounds are necessary.

We also investigate the asynchronous version of the push-pull protocol, where
the nodes do not operate in rounds, but exchange information according to a
Poisson process with rate 1. Surprisingly, we are able to show that, if $2 <
\beta < 3$, the rumor spreads even in {\em constant} time, which is much
smaller than the typical distance of two nodes.

This is joint work with N. Fountoulakis, T. Sauerwald.

Contact

Konstantinos Panagiotou
--email hidden
passcode not visible
logged in users only

Konstantinos Panagiotou, 04/14/2011 11:07
Konstantinos Panagiotou, 03/30/2011 11:43
Konstantinos Panagiotou, 03/21/2011 15:03
Konstantinos Panagiotou, 03/18/2011 14:32 -- Created document.