Self-organizing structure and metrics of complex networks [Elektronische Ressource] / von Jan Carsten Scholz

Jan Carsten Scholz

Sujets

• Physik

Informations

• Publié par: goethe_universitat_frankfurt_am_main
• Publié le: 01 janvier 2010
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Self-organizing structure and metrics
of complex networks
Dissertation
zur Erlangung des Doktorgrades
der Naturwissenschaften
vorgelegt beim Fachbereich Physik
der Goethe Universität
Frankfurt am Main
von
Jan Carsten Scholz
aus Gießen
Frankfurt, 2010
(D30)vom Fachbereich Physik der
Goethe Universität als Dissertation angenommen.
Dekan: Prof. Dr. Michael Huth
Gutachter: Prof. Dr. Martin Greiner, Prof. Dr. Joachim Maruhn
Datum der Disputation:Contents
German summary v
1. Introduction 1
2. Brief Résumé of Graph Theory 5
2.1. Graph Theory notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Empirical networks and network models . . . . . . . . . . . . . . . . 10
2.2.1. Small world graphs . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2. Scale-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3. Geometric-p model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. Game Theory on networks 19
3.1. The Prisoner’s Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2. Games and Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3. Prisoners’ Dilemma Network Game . . . . . . . . . . . . . . . . . . . 27
3.4. Related network structure modeling . . . . . . . . . . . . . . . . . . . 29
4. Iterated prisoners dilemma network game 33
4.1. Iterated Prisoner’s Dilemma (IPD) . . . . . . . . . . . . . . . . . . . . 34
4.2. Neighborhood Exploration Schemes . . . . . . . . . . . . . . . . . . . 37
4.3. Existence of NNEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4. Perturbation dynamics of NNEs . . . . . . . . . . . . . . . . . . . . . 42
4.5. Properties of stationary NNEs . . . . . . . . . . . . . . . . . . . . . . . 47
5. Incentives for cooperation 53
5.1. Underlying interaction model . . . . . . . . . . . . . . . . . . . . . . . 53
5.2. Incentive model and distribution strategies . . . . . . . . . . . . . . . 55
5.3. Comparison of incentive strategies . . . . . . . . . . . . . 56
6. Communication throughput of networks 59
6.1. Data Traffic Model and Load . . . . . . . . . . . . . . . . . . . . . . . 59
6.2. Derivation of Throughput Capacity T . . . . . . . . . . . . . . . . . 61e2e
6.3. Influence of network structure on data throughput . . . . . . . . . . . 62
7. Advanced routing 65
7.1. Weights and metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.2. Routing weight assignments . . . . . . . . . . . . . . . . . . . . . . . . 68
iiiContents
7.3. Effects of metrics on distances and loads . . . . . . . . . . . . . . . . . 71
7.4. Hybrid metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.5. Comparing T -scaling of the metrics . . . . . . . . . . . . . . . . . . 80e2e
7.6. Self-organizing (SO) metric . . . . . . . . . . . . . . . . . . . . . . . . 88
7.7. The log(k k )-metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91i j
8. Conclusion 95
A. AS-level data table 99
B. Coauthored publications 103
Proactive robustness control of heterogeneously loaded networks . . . . . 105
Optimized network structure and routing metric in wireless multihop ad
hoc communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Bibliography 127
Acknowledgments 135
CV 137
ivZusammenfassung in deutscher
Sprache
Die vorliegende Arbeit befasst sich mit der Charakterisierung und Optimierung
von Prozessen auf komplexen Netzwerken. In Natur, Gesellschaft und Technik
existiert eine Vielzahl ungeordneter Systeme, für die die Emergenz makroskopi-
scher Eigenschaften aus mikroskopischen Wechselwirkungen charakteristisch sind.
Diese makroskopischen Eigenschaften sind in den einzelnen mikroskopischen Be-
standteilen nicht erkennbar, sondern entstehen erst durch das Zusammenspiel einer
großen Anzahl derselben. Beispiele für emergente Eigenschaften sind Phasenüber-
gänge wie sie im Magnetismus und in der Perkolation, aber auch in biologischen
und sozialen Systemen auftreten. Weitere bedeutende Beispiele sind komplexe
technologische Systeme, insbesondere solche, bei deren Entwicklung eine hohe
Ausfallsicherheit ohne zentrale Kontrollinstanz eine wichtige Rolle spielt. Die
wahrscheinlich prominentesten Beispiele hierfür sind das Internet, bestehend aus
weltweit vernetzten Routern, sowie das World-Wide-Web, die (virtuelle) Struktur,
gebildet von Homepages und ihren Verbindungen durch Hyperlinks. Eine verblüf-
fende Gemeinsamkeit vieler solcher in der Natur auftretender vernetzter Systeme
ist die Struktur der Netzwerke, die sich weder durch reguläre Gitter, noch durch
rein zufällige Verbindungen beschreiben lassen.
Der mathematische Rahmen zur Beschreibung von Netzwerken ist die Graphen-
theorie. Deren Ursprünge finden sich bereits bei Euler [1736], aber auch heute
stellt sie ein aktives Forschungsfeld der Mathematik dar [z.B. Erdös und Rényi,
1960, Bollobás, 1985, 1998]. Im Formalismus der Graphentheorie werden vernetzte
Strukturen als Menge von Knoten dargestellt, welche durch Kanten miteinander ver-
bunden sind. Durch computergestützte Datenaquise und -verarbeitung wurden in
den zwei vergangenen Jahrzehnten empirische Datensätze zu Netzwerkstrukturen
zugänglich, deren Größe die zuvor manuell ermittelten Datensätze um Größen-
ordnungen übertrifft. Exemplarisch für diese Entwicklung ist die Zahl der Knoten
in Soziologischen Studien zu sehen. Untersucht Zachary [1977] das soziale Netz
zwischen 34 Mitgliedern eines Karateclubs und Klovdahl [1985] das Netzwerk
sexueller Kontakte zwischen 40 HIV infizierten Personen, so extrahieren Ebel et al.
[2002] das soziale Netz zwischen 6000 Kieler Studenten durch die Analyse ihrer
eMail-Kommunikation, und Palla et al. [2007] untersuchen ein Netzwerk von über
4 Millionen Nutzern eines Mobilfunkanbieters.
Viele wissenschaftliche Forschungsgebiete, die zuvor vornehmlich im Bereich
der mikroskopischen Wechselwirkungen quantitativ gearbeitet haben, erfahren
durch die Anwendung der Graphentheorie eine Analyse ihres makroskopischen
vGerman summary
Verhaltens. Den so genannten Small World Effekt, von Milgram [1967] in sozialen
Netzwerken beschrieben als den Umstand, dass jeder Bewohner der USA mit jedem
Anderen im Mittel über eine Kette von ca. 6 Bekanntschaften verbunden ist, finden
Watts und Strogatz [1998] in Netzwerken unterschiedlichsten Ursprungs: Im Netz-
werk der Neuronen des Wurms Caenorhabditis elegans, in der Verbindungsstruktur
des Stromnetzes der westlichen USA, und in einem Graphen, der die Zusammen-
arbeit zwischen Filmschauspielern beschreibt. Watts und Strogatz definieren den
Small World Effekt als das gemeinsame Auftreten enger lokaler Vermaschung (Clu-
stering), und eines kurzen mittleren Abstands zwischen den Knoten des Netzes auf
globaler Ebene. Wenig später folgt die Entdeckung der skalenfreien, d.h. einem
Potenzgesetz folgenden Verteilung der Anzahl der Nachbarn von Knoten in Netz-
werken, im Fall des Internets durch Faloutsos et al. [1999], sowie für das World Wide
Web durch Albert et al. [1999]. Zahlreiche Studien folgen, die sowohl den Small
World Effekt, als auch die Skalenfreiheit als Gemeinsamkeit einer Vielzahl unter-
schiedlichster realer Netze bestätigen. Stellvertretend seien hier soziale Netzwerke
(Zitierungen wissenschaftlicher Artikel Newman [2001a] und die bereits erwähn-
ten Email-Netzwerke [Ebel et al., 2002]), biologische Netzwerke (Interaktionen im
Zellstoffwechsel [Jeong et al., 2000, Wagner und Fell, 2001] und Protein-Protein
Wechselwirkungen [Yook et al., 2004]) und die bereits vorgestellten technologischen
Netzwerke erwähnt, weitere Beispiele finden sich in unterschiedlichsten Bereichen
von Ökologie bis Ökonomie. Aber auch umgekehrt katalysiert die Entdeckung des
Small World Effekts und der Skalenfreiheit in empirischen Netzwerkdaten, die von
dem Standardmodell für zufällige Grafen [Erdös und Rényi, 1960] nicht reprodu-
ziert werden, das Interesse und die Weiterentwicklung der Graphentheorie. Die
interdisziplinäre Vereinigung von Forschungsgebieten durch die Gemeinsamkei-
ten der als Netzwerk abstrahierten Strukturen, sowie die Suche nach Erklärungen
für deren Emergenz bilden das junge Forschungsgebiet der komplexen Netzwer-
ke. Hier helfen Methoden der Physik, wie Generalisierung und Reduktion auf
grundlegende Eigenschaften, die Aufmerksamkeit von implementationsspezifi-
schen Details der mikroskopischen Dynamik auf makroskopische Folgen zu lenken.
Speziell die Konzepte und Methoden der Statistischen Physik erweisen sich im
Umgang mit komplexen Netzwerken als nützlich.
In klassischen Anwendungen der statistischen Physik sind die Wechselwirkun-
gen zwischen den mikroskopischen Bestandteilen durch physikalische Gesetze
gegeben. In Systemen deren mikroskopische Wechselwirkungen beeinflusst wer-
den können, sei es weil sie technologischen Ursprungs sind, oder weil sie eine
(gewisse) Intelligenz besitzen, ergibt sich eine aufregende Perspektive: Werden
die Wechselwirkungen verändert, so kann dies durch die Mechanismen der Emer-
genz und Selbstorganisation das makroskopische Erscheinungsbild des Systems
quantitativ un