André Krischke, Helge Röpcke
Graphen und Netzwerktheorie
Grundlagen - Methoden - Anwendungen
Vorwort
7
Inhaltsverzeichnis
9
I Grundlagen der Graphentheorie
15
1 Grundbegriffe der Graphentheorie
17
1.1 Grundbegriffe für Graphen
18
1.1.1 Definition eines Graphen
18
1.1.2 Grad eines Knotens
20
1.1.3 Wege und Kreise
23
1.2 Typen von Graphen
25
1.2.1 Vollständige Graphen
25
1.2.2 Bipartite Graphen
28
1.2.3 Gerichtete Graphen und Multigraphen
30
1.2.4 Bewertete Graphen
31
1.2.5 Bäume und Wälder
35
1.2.6 Gozinto-Graphen
38
2 Das Kürzeste-Wege-Problem in unbewerteten Graphen
41
2.1 Aufspannende Bäume
41
2.2 Breitensuche
43
2.3 Tiefensuche
46
2.4 Anwendungen in der Praxis
49
3 Das Kürzeste-Wege-Problem in bewerteten Graphen
54
3.1 Der Kürzeste-Wege-Baum und die kombinatorische Explosion
54
3.2 Der Algorithmus von Dijkstra
58
II Ausgewählte Probleme der Graphentheorie
66
4 Das Problem minimal aufspannender Bäume
68
4.1 Minimal aufspannender Baum
68
4.2 Algorithmus von Kruskal
70
4.3 Algorithmus von Prim
73
5 Matching-Probleme
76
5.1 Definition von Matchings
76
5.2 Matchings für bipartite Graphen
78
5.3 Maximal-Matching-Algorithmen
80
5.3.1 Greedy-Matching-Algorithmus
81
5.3.2 Verbessernde Wege
82
6 Das Problem des chinesischen Postboten
85
6.1 Euler-Kreise und Euler-Wege
85
6.2 Postbotenproblem
92
7 Das Problem des Handlungsreisenden
97
7.1 Hamilton-Kreise und Hamilton-Wege
97
7.1.1 Existenz von hamiltonschen Graphen
99
7.1.2 Problem des Handlungsreisenden
100
7.2 Heuristiken
102
7.3 Anwendungen in der Praxis
106
8 Färbungsprobleme
112
8.1 Planarität und Satz von Euler
112
8.2 Knotenfärbung
117
8.3 Kantenfärbung
122
8.4 Dualität zwischen Knoten- und Kantenfärbung
124
III Netzwerktheorien und -modelle
126
9 Netzwerktheorie – Bedeutung und neuere Erkenntnisse
128
9.1 Große Netzwerke in der Praxis
128
9.1.1 Interorganisations-Netzwerke
129
9.1.2 Beziehungs-, Freundschafts- und soziale Netzwerke
130
9.1.3 Informations-, Daten- und Wissensnetzwerke
131
9.1.4 Technologische Netzwerke
134
9.1.5 Biologische Netzwerke
136
9.2 Ausgewählte Erkenntnisse der Netzwerkforschung
137
9.2.1 Forschung im Bereich sozialer Netzwerke
138
9.2.2 Cluster als Kennzeichen sozialer Netzwerke
139
9.2.3 Kurze Wege als Kennzeichen sozialer Netzwerke
141
9.2.4 Skalen-Invarianz als Kennzeichen großer Netzwerke
142
9.2.5 Universalität als Kennzeichen großer Netzwerke
145
9.3 Weiterführende Literatur
147
10 Eigenschaften von Netzwerken
148
10.1 Charakterisierung von Netzwerken auf Knoten-Ebene
148
10.1.1 Unterscheidung von Hubs und Authorities
148
10.1.2 Lokaler Cluster-Koeffizient
149
10.1.3 Zentralitätsmaße eines Knotens
150
10.2 Charakterisierung von Netzwerken auf Teilgraphen-Ebene
152
10.2.1 Verfahren zum Auffinden zusammenhängender Komponenten
154
10.2.2 Algorithmen zum Auffinden von Communities
155
10.2.3 Klassifizierende Verfahren zum Auffinden von Communities
156
10.3 Charakterisierung von Netzwerken mit statistischen Größen
158
10.3.1 Mittlerer Knotengrad und durchschnittliche Netzwerkdichte
159
10.3.2 Häufigkeitsverteilung der Kontengrade
160
10.3.3 Der Durchmesser und die mittlere Pfadlänge des Netzwerks
162
10.3.4 Der globale Cluster-Koeffizient eines Netzwerks
163
10.4 Weiterführende Literatur
163
11 Entstehung von Netzwerken – Netzwerkmodelle
164
11.1 Erzeugung von Netzwerken mit Gleich- oder Binomialverteilung
165
11.1.1 Erzeugung von Gittergraphen mit deterministischen Regeln
165
11.1.2 Erzeugung eines Erdös-Renyi-Zufallsgraphen
167
11.1.3 Erzeugung des Watts-Strogatz-Modells – zwischen Kreis- und Zufallsgraph
172
11.2 Erzeugung von Netzwerken mit skalenfreier Verteilung
176
11.2.1 Erzeugung eines skalenfreien Netzwerks durch das Wachstumsmodell
176
11.2.2 Erzeugung eines skalenfreien Netzwerks mit dem Barabasi-Albert-Modell des „Preferential Attachment“
177
11.2.3 Erweiterungen des Barabasi-Albert-Modells
180
11.3 Weiterführende Literatur
183
12 Dynamische Prozesse auf großen Netzwerken
184
12.1 Robustheit von Netzwerken
184
12.1.1 Relevanz und Erscheinungsformen
184
12.1.2 Wesentliche Modelle und Lösungsverfahren
187
12.1.3 Zusammenfassung wesentlicher Erkenntnisse
189
12.2 Epidemische Ausbreitung in Netzwerken
189
12.2.1 Relevanz und Erscheinungsformen
190
12.2.2 Wesentliche Modelle und Lösungsverfahren
192
12.2.3 Homogene Modelle zur Beschreibung der Ausbreitung
193
12.2.4 Netzwerkmodelle zur Beschreibung der Ausbreitung
195
12.2.5 Impfung in heterogenen Netzwerken
196
12.2.6 Zusammenfassung wesentlicher Erkenntnisse
199
12.3 Suche in Netzwerken
199
12.3.1 Relevanz und Erscheinungsformen
200
12.3.2 Wesentliche Modelle und Lösungsverfahren
200
12.3.3 Zusammenfassung wesentlicher Erkenntnisse
203
12.4 Transportprozesse in Netzwerken
203
12.4.1 Datenverkehr und Datenstau in Netzwerken
204
12.4.2 Kaskaden in Transportnetzwerken
207
12.4.3 Zusammenfassung wesentlicher Erkenntnisse
211
12.5 Kollektives Verhalten in Netzwerken
211
12.5.1 Meinungsbildung in Netzwerken – Das Voting-Modell
212
12.5.2 Informationskaskaden in Netzwerken
213
12.5.3 Spieltheorie in Netzwerken
215
12.5.4 Zusammenfassung wesentlicher Erkenntnisse
217
12.6 Dynamische Prozesse in Netzwerken – Forschungsbedarf
217
12.7 Weiterführende Literatur
218
13 Softwarebasierte Analyse und Modellierung großer Netzwerke
219
13.1 Die Modellbildung als Forschungsprozess
219
13.1.1 Formulierung der Forschungsfrage
220
13.1.2 Formulierung der Forschungshypothesen
220
13.1.3 Festlegung der Modellstruktur
221
13.1.4 Implementierung und Verifikation des Modells
222
13.1.5 Analyse und Validierung des Modells
223
13.1.6 Ergebnisdarstellung zur Entscheidungsunterstützung
223
13.2 Softwarebasierte Analyse und Visualisierung
224
13.2.1 Vorgehen bei der Datenbeschaffung und Datenimport
225
13.2.2 Softwarebasierte Erzeugung von Netzwerken
227
13.2.3 Grundlagen der Visualisierung und des Graphzeichnens
228
13.2.4 Softwarebasierte Analyse großer Netzwerke
230
13.3 Softwarebasierte Simulation dynamischer Prozesse in Netzwerken
233
13.3.1 Vergleich verschiedener Simulationsmodelle
233
13.3.2 Agentenbasierte Simulationsmodelle auf regulären Netzwerken
235
13.3.3 Simulation des Wachstums von Netzwerken
237
13.3.4 Simulation dynamischer Prozesse in Netzwerken
238
13.3.5 Simulation dynamischer Prozesse auf dynamischen Netzwerken
240
13.3.6 Generierung von Simulationsdaten und Durchsuchen des Lösungsraums
241
13.4 Schlussbetrachtung zur softwarebasierten Modellierung
242
13.5 Weiterführende Literatur
243
Literaturverzeichnis
244
Bildnachweise
249
Sachwortverzeichnis
250
© 2009-2024 ciando GmbH