Randomisiertes Rumor Spreading auf Sozialen Netwerken und Vollständigen Graphen

Abstract

Nicht zuletzt wegen dem Einfluss des Internets ist die Analyse der Verbreitung von Informationen in komplexen Netzwerken ein wichtiger Forschungsbereich. In meiner Dissertation beschäftigen wir uns mit zwei Problemstellungen in diesem Zusammenhang. Im ersten Teil untersuchen wir die Verbreitung von Informationen in sozialen Netzwerken. Hierzu benutzen wir das "Preferential Attachment"-Graph Modell. Wir beweisen, dass ein natürliches Protokoll zur Verbreitung von Informationen sublogarithmische Zeit benötigt in der Größe des Netzwerks, um eine Nachricht von einem Knoten zu allen Knoten zu verbreiten. Im Gegensatz dazu benötigt das Protokoll auf allen vorher untersuchten Netzwerktopologien mindestens logarithmische Zeit. Im zweiten Teil betrachten wir die Verbreitung von Informationen auf vollständigen Gra- phen. Wir führen ein neues Protokoll ein, das eine Laufzeit von (1 + o(1)) log2 n erreicht. Dies ist asymptotisch optimal unter allen Protokollen, bei denen nur informierte Knoten an der Nachrichtenübertragung aktiv beteiligt sind und zudem in jedem Schritt höchstens einen Nachbarknoten informieren können. Dabei braucht es lediglich O(nf(n)) Nachrichten, wobei f(n) = ω(1) beliebig ist.