Graphen und Netzwerktheorie

Vorwort

Inhaltsverzeichnis

I Grundlagen der Graphentheorie

1 Grundbegriffe der Graphentheorie

1.1 Grundbegriffe für Graphen

1.1.1 Definition eines Graphen

1.1.2 Grad eines Knotens

1.1.3 Wege und Kreise

1.2 Typen von Graphen

1.2.1 Vollständige Graphen

1.2.2 Bipartite Graphen

1.2.3 Gerichtete Graphen und Multigraphen

1.2.4 Bewertete Graphen

1.2.5 Bäume und Wälder

1.2.6 Gozinto-Graphen

2 Das Kürzeste-Wege-Problem in unbewerteten Graphen

2.1 Aufspannende Bäume

2.2 Breitensuche

2.3 Tiefensuche

2.4 Anwendungen in der Praxis

3 Das Kürzeste-Wege-Problem in bewerteten Graphen

3.1 Der Kürzeste-Wege-Baum und die kombinatorische Explosion

3.2 Der Algorithmus von Dijkstra

II Ausgewählte Probleme der Graphentheorie

4 Das Problem minimal aufspannender Bäume

4.1 Minimal aufspannender Baum

4.2 Algorithmus von Kruskal

4.3 Algorithmus von Prim

5 Matching-Probleme

5.1 Definition von Matchings

5.2 Matchings für bipartite Graphen

5.3 Maximal-Matching-Algorithmen

5.3.1 Greedy-Matching-Algorithmus

5.3.2 Verbessernde Wege

6 Das Problem des chinesischen Postboten

6.1 Euler-Kreise und Euler-Wege

6.2 Postbotenproblem

7 Das Problem des Handlungsreisenden

7.1 Hamilton-Kreise und Hamilton-Wege

7.1.1 Existenz von hamiltonschen Graphen

7.1.2 Problem des Handlungsreisenden

7.2 Heuristiken

7.3 Anwendungen in der Praxis

8 Färbungsprobleme

8.1 Planarität und Satz von Euler

8.2 Knotenfärbung

8.3 Kantenfärbung

8.4 Dualität zwischen Knoten- und Kantenfärbung

III Netzwerktheorien und -modelle

9 Netzwerktheorie – Bedeutung und neuere Erkenntnisse

9.1 Große Netzwerke in der Praxis

9.1.1 Interorganisations-Netzwerke

9.1.2 Beziehungs-, Freundschafts- und soziale Netzwerke

9.1.3 Informations-, Daten- und Wissensnetzwerke

9.1.4 Technologische Netzwerke

9.1.5 Biologische Netzwerke

9.2 Ausgewählte Erkenntnisse der Netzwerkforschung

9.2.1 Forschung im Bereich sozialer Netzwerke

9.2.2 Cluster als Kennzeichen sozialer Netzwerke

9.2.3 Kurze Wege als Kennzeichen sozialer Netzwerke

9.2.4 Skalen-Invarianz als Kennzeichen großer Netzwerke

9.2.5 Universalität als Kennzeichen großer Netzwerke

9.3 Weiterführende Literatur

10 Eigenschaften von Netzwerken

10.1 Charakterisierung von Netzwerken auf Knoten-Ebene

10.1.1 Unterscheidung von Hubs und Authorities

10.1.2 Lokaler Cluster-Koeffizient

10.1.3 Zentralitätsmaße eines Knotens

10.2 Charakterisierung von Netzwerken auf Teilgraphen-Ebene

10.2.1 Verfahren zum Auffinden zusammenhängender Komponenten

10.2.2 Algorithmen zum Auffinden von Communities

10.2.3 Klassifizierende Verfahren zum Auffinden von Communities

10.3 Charakterisierung von Netzwerken mit statistischen Größen

10.3.1 Mittlerer Knotengrad und durchschnittliche Netzwerkdichte

10.3.2 Häufigkeitsverteilung der Kontengrade

10.3.3 Der Durchmesser und die mittlere Pfadlänge des Netzwerks

10.3.4 Der globale Cluster-Koeffizient eines Netzwerks

10.4 Weiterführende Literatur

11 Entstehung von Netzwerken – Netzwerkmodelle

11.1 Erzeugung von Netzwerken mit Gleich- oder Binomialverteilung

11.1.1 Erzeugung von Gittergraphen mit deterministischen Regeln

11.1.2 Erzeugung eines Erdös-Renyi-Zufallsgraphen

11.1.3 Erzeugung des Watts-Strogatz-Modells – zwischen Kreis- und Zufallsgraph

11.2 Erzeugung von Netzwerken mit skalenfreier Verteilung

11.2.1 Erzeugung eines skalenfreien Netzwerks durch das Wachstumsmodell

11.2.2 Erzeugung eines skalenfreien Netzwerks mit dem Barabasi-Albert-Modell des „Preferential Attachment“

11.2.3 Erweiterungen des Barabasi-Albert-Modells

11.3 Weiterführende Literatur

12 Dynamische Prozesse auf großen Netzwerken

12.1 Robustheit von Netzwerken

12.1.1 Relevanz und Erscheinungsformen

12.1.2 Wesentliche Modelle und Lösungsverfahren

12.1.3 Zusammenfassung wesentlicher Erkenntnisse

12.2 Epidemische Ausbreitung in Netzwerken

12.2.1 Relevanz und Erscheinungsformen

12.2.2 Wesentliche Modelle und Lösungsverfahren

12.2.3 Homogene Modelle zur Beschreibung der Ausbreitung

12.2.4 Netzwerkmodelle zur Beschreibung der Ausbreitung

12.2.5 Impfung in heterogenen Netzwerken

12.2.6 Zusammenfassung wesentlicher Erkenntnisse

12.3 Suche in Netzwerken

12.3.1 Relevanz und Erscheinungsformen

12.3.2 Wesentliche Modelle und Lösungsverfahren

12.3.3 Zusammenfassung wesentlicher Erkenntnisse

12.4 Transportprozesse in Netzwerken

12.4.1 Datenverkehr und Datenstau in Netzwerken

12.4.2 Kaskaden in Transportnetzwerken

12.4.3 Zusammenfassung wesentlicher Erkenntnisse

12.5 Kollektives Verhalten in Netzwerken

12.5.1 Meinungsbildung in Netzwerken – Das Voting-Modell

12.5.2 Informationskaskaden in Netzwerken

12.5.3 Spieltheorie in Netzwerken

12.5.4 Zusammenfassung wesentlicher Erkenntnisse

12.6 Dynamische Prozesse in Netzwerken – Forschungsbedarf

12.7 Weiterführende Literatur

13 Softwarebasierte Analyse und Modellierung großer Netzwerke

13.1 Die Modellbildung als Forschungsprozess

13.1.1 Formulierung der Forschungsfrage

13.1.2 Formulierung der Forschungshypothesen

13.1.3 Festlegung der Modellstruktur

13.1.4 Implementierung und Verifikation des Modells

13.1.5 Analyse und Validierung des Modells

13.1.6 Ergebnisdarstellung zur Entscheidungsunterstützung

13.2 Softwarebasierte Analyse und Visualisierung

13.2.1 Vorgehen bei der Datenbeschaffung und Datenimport

13.2.2 Softwarebasierte Erzeugung von Netzwerken

13.2.3 Grundlagen der Visualisierung und des Graphzeichnens

13.2.4 Softwarebasierte Analyse großer Netzwerke

13.3 Softwarebasierte Simulation dynamischer Prozesse in Netzwerken

13.3.1 Vergleich verschiedener Simulationsmodelle

13.3.2 Agentenbasierte Simulationsmodelle auf regulären Netzwerken

13.3.3 Simulation des Wachstums von Netzwerken

13.3.4 Simulation dynamischer Prozesse in Netzwerken

13.3.5 Simulation dynamischer Prozesse auf dynamischen Netzwerken

13.3.6 Generierung von Simulationsdaten und Durchsuchen des Lösungsraums

13.4 Schlussbetrachtung zur softwarebasierten Modellierung

13.5 Weiterführende Literatur

Literaturverzeichnis

Bildnachweise

Sachwortverzeichnis