Please use this identifier to cite or link to this item: doi:10.22028/D291-26384
Title: Randomized rumor spreading in social networks and complete graphs
Author(s): Fouz, Mahmoud
Language: English
Year of Publication: 2012
SWD key words: Randomisierung
Algorithmus
Laufzeit
Vollständiger Graph
Free key words: rumor spreading
social networks
runtime anlaysis
complete graph
information spreading
DDC notations: 004 Computer science, internet
Publikation type: Dissertation
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.
Link to this record: urn:nbn:de:bsz:291-scidok-49032
hdl:20.500.11880/26440
http://dx.doi.org/10.22028/D291-26384
Advisor: Doerr, Benjamin
Date of oral examination: 16-Jul-2012
Date of registration: 23-Jul-2012
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
thesis_1672012.pdf11,33 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.