TY  - THES
U1  - Master Thesis
A1  - Messner, Alrik
T1  - Modelle für die Informationsausbreitung in Graphen
N2  - In dieser Arbeit werden Übergangswahrscheinlichkeiten für die anderen beiden Modelle abgeleitet. Des weiteren wird gezeigt, dass sich die Anzahl der benötigten Gleichungen zum Lösen der in [21] angegebenen Rekursion für die mittleren Erstankunftszeiten der den Modellen zugrunde liegenden Markovketten für den Sterngraphen zu 2 j V j 1 ergibt. Es wird für bestimmte Graphen mit guten Symmetrieeigenschaften eine alternative Darstellung als Markovkette angegeben. Für eben diese Graphen werden nur O (j V j) viele Gleichungen benötigt, um eine äquivalente Rekursion für die mittlere Zeit bis zum Informieren von ganz V zu lösen. Es werden Reduktionen und Schranken für die mittleren Erstankunftszeiten angegeben und unabhängig von [9] und [7] wird eine Variante des Push-Algorithmus mit Gedächtnis eingeführt, für welche eine obere Schranke für die Laufzeit angegeben wird. Allem vorangestellt wird kurz das zugrunde liegende Problem  und vor allem der Push-Algorithmus beleuchtet und es werden wichtige frühere Ergebnisse anderer Autoren vorgestellt. Abschließend werden die Ergebnisse bewertet und offene Probleme angegeben. Es werden in dieser Arbeit nicht behandelte Modelle vorgeschlagen.
KW  - Graphen
Y2  - 2015
ER  -