Randomized rumor spreading in social networks and complete graphs

Abstract

This thesis deals with two rumor spreading problems. In the first part, we study the rumor spreading problem in social networks modelled by preferential attachment graphs. We consider the push-pull strategy by Karp, Schindelhauer, Shenker, and Vöcking [FOCS 2000], where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. The push-pull strategy delivers a message to all nodes within \Theta(\log n) rounds with high probability, where n is the number of nodes in the graph. The best known bound so far was O(\log^2 n) by Chierichetti, Lattanzi, and Panconesi [TCS 2011]. If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to \Theta(\logn/\log\log n). This is asymptotically optimal since it matches the diameter of the graph. In an asynchronous version of the protocol, the running time is shown to be even O(\sqrt{\log n}). In the second part, we consider the rumor spreading problem on the complete graph. We propose a new push protocol that achieves an asymptotically optimal time of (1+o(1))\log^2 n. It needs only O(n f(n)) calls, where f(n) = \omega(1) can be arbitrary. The protocol is robust against random node failures. We also extend it to deal with adversarial node failures efficiently.

Im ersten Teil untersuchen wir die Verteilung von Informationen auf sozialen Netzwerken anhand des “Preferential Attachment” Modells. Hierzu betrachten wir das “Push-Pull” Protokoll von Karp, Schindelhauer, Shenker, and Vöcking [FOCS 2000]: In jeder Runde wählt ein Knoten einen zufälligen Nachbarknoten aus und tauscht sich mit ihm aus, d.h., wenn einer der beiden Knoten eine Information hat, erhält sie der andere. Wir zeigen folgende Resultate. Das Push-Pull Protokoll verbreitet mit hoher Wahrscheinlichkeit eine Nachricht an alle Knoten innerhalb von \Theta(\log n) Runden, wobei n die Zahl der Knoten im Graph darstellt. Die beste bisher bekannte Laufzeitschranke war O(\log^2 n) von Chierichetti, Lattanzi, and Panconesi [TCS 2011]. Wenn wir das Protokoll leicht anpassen, so dass jeder Knoten bei der zufälligen Wahl eines Nachbarknoten den zuletzt kontaktierten ausschließt, verbessert sich diese Schranke auf \Theta(\log n/\log\log n). Dies ist asymptotisch optimal, da es dem Durchmesser des Graphen entspricht. In einer asynchronen Fassung des Protokolls reduziert sich die Laufzeit sogar auf O(\sqrt{\log n}). Im zweiten Teil betrachten wir die Verteilung von Informationen auf dem vollständigen Graphen. Wir führen ein neues “Push” Protokoll ein, das eine asymptotisch optimale Laufzeit von (1+o(1))\log n erreicht. Dabei benötigt es nur O(n f(n)) Anrufe, wobei f(n) = \omega(1) beliebig ist. Das Protokoll ist zudem robust gegenüber zufälligen Knotenausfällen. Ferner erweitern wir das Protokoll, so dass es auch bei gezielten Knotenausfällen effizient bleibt.