Modelle für die Informationsausbreitung in Graphen
- 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.
Author: | Alrik Messner |
---|---|
Document Type: | Master's Thesis |
Language: | German |
Year of Completion: | 2015 |
Granting Institution: | Hochschule Mittweida |
Release Date: | 2016/01/07 |
GND Keyword: | Graphen |
Institutes: | 03 Mathematik / Naturwissenschaften / Informatik |
DDC classes: | 530 Physik |
Open Access: | Innerhalb der Hochschule |
Licence (German): | Urheberrechtlich geschützt |