Randomized Rumor Spreading in Social Networks

DIKU Talk by Benjamin Doerr, Senior Researcher, Max-Planck-Institut für Informatik, Saarbrücken,


Randomized rumor spreading is a simple decentralized process disseminating information in networks, usually by nothing else than nodes communicating with neighbors chosen uniformly at random. Despite its simplicity, randomized rumor spreading is highly efficient and at the same time robust against many types of transmission failures. If the underlying network has the structure of a complete graph, hypercube, Erdos-Renyi or regular random graph, then with high probability after a logarithmic number of rounds a news initially known to a single node has reached all nodes. This remains true if messages get lost independently with constant probability.

In this talk, I will discuss what is known about randomized rumor spreading in graphs that are closer to real-world and social networks.

One main finding will be that rumors spread even faster in such networks. Much of the work I will present is joint work with Mahmoud Fouz and Tobias Friedrich (appeared at STOC'11 and SWAT'12).


Benjamin Doerr is a senior researcher at the Max Planck Institute for Computer Science and a professor at Saarland University. He received his diploma (1998), PhD (2000) and habilitation (2005) in mathematics from Kiel University. His research area is the theory both of problem-specific algorithms and of randomized search heuristics like evolutionary algorithms.

More info: http://www.mpi-inf.mpg.de/~doerr/index.html


Scientific Host: Christian Igel, DIKU

The talk is open to all interested parties - admission is free