Prof. Dr. Benjamin Doerr
MPI Informatik, Saarbrücken

Randomized rumor spreading in social networks

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).