Stochastische Analyse von Preferential Attachment-Modellen
Stochastic analysis of preferential attachment models
- Die vorliegende Arbeit untersucht ausgewählte Eigenschaften von Preferential Attachment-Graphen. Darunter verstehen wir eine Klasse komplexer zufälliger Graphen, die mit einer vorgegebenen Konfiguration gestartet werden und anschließend mit jedem Zeitschritt um eine Ecke und m Kanten wachsen. Die Wachstumsregeln sind so gestaltet, dass eine neue Ecke ihre Kanten bevorzugt an Ecken sendet, die bereits mit vielen anderen Ecken verbunden sind, woraus sich die Bezeichnung Preferential Attachment (PA) ableitet. Die Arbeit stellt zunächst heuristisch die Eigenschaft der Skalenfreiheit von PA-Modellen vor und bespricht anschließend einen Beweis zu dieser These. Weiter betrachten wir den Durchmesser von PA-Graphen und untersuchen das Verhalten bei Anwachsen des Graphen. Wir erkennen, dass der Durchmesser bei wachsendem Graphen deutlich langsamer wächst, was wir als Small World-Phänomen bezeichnen. Die zentralen Aussagen und Beweise orientieren sich an den Arbeiten von Remco van der Hofstad, der die bekannten PA-Modelle um einen Parameter erweitert hat. Damit ist es möglich, sowohl logarithmische als auch doppelt-logarithmische Schranken für den Durchmesser zu erhalten.
Author: | Christoph te Kampe |
---|---|
URN: | urn:nbn:de:hebis:30-71249 |
Advisor: | Ralph Neininger |
Document Type: | diplomthesis |
Language: | German |
Date of Publication (online): | 2009/10/23 |
Year of first Publication: | 2009 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Granting Institution: | Johann Wolfgang Goethe-Universität |
Release Date: | 2009/10/23 |
Tag: | preferential attachment models preferential attachment |
GND Keyword: | Preferential Attachment-Modelle |
HeBIS-PPN: | 217177905 |
Institutes: | Informatik und Mathematik / Mathematik |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | Deutsches Urheberrecht |