Zufällige Graphen (Wintersemester 2015/16)
- Dozent*in: Dr. Matthias Schulte
- Veranstaltungen: Vorlesung (0103400), Übung (0103410)
- Semesterwochenstunden: 3+1
| Termine | ||
|---|---|---|
| Vorlesung: | Dienstag 9:45-11:15 | SR 2.59 |
| Übung: | Mittwoch 14:00-15:30 | SR 2.59 |
| Lehrende | ||
|---|---|---|
| Dozent, Übungsleiter | Dr. Matthias Schulte | |
| Sprechstunde: nach Vereinbarung | ||
| Zimmer Kollegiengebäude Mathematik (20.30) | ||
| Email: matthias.schulte@kit.edu | ||
Inhalt
Komplexe Netzwerke spielen eine wichtige Rolle in unserem Leben. Beispiele hierfür sind soziale Netzwerke wie Facebook, das World-Wide-Web oder Telekommunikationsnetzte. Alle diese Netzwerke haben gemeinsam, dass sie sehr groß sind und eine unregelmäßige zufällig anmutende Struktur haben. Ein Ansatz um solche Systeme zu modellieren sind zufällige Graphen. Ein zufälliger Graph besteht aus einer (zufälligen) Menge von Knoten, die nach einem zufälligen Mechanismus mit Kanten verbunden werden.
Im Rahmen der Vorlesung werden verschiedene grundlegende Modelle für zufällige Graphen behandelt. Dies sind Erdös-Renyi-Graphen, bei denen Paare von Knoten unabhängig voneinander mit Kanten verbunden werden, das Konfigurationsmodell, in dem die Grad-Verteilung der Knoten vorgegeben ist, sowie Preferential-Attachment-Graphen, bei denen Knoten sequentiell eingefügt werden und sich bevorzugt mit Knoten mit einem hohen Grad verbinden. Am Ende der Lehrveranstaltung werden zufällige geometrische Graphen betrachtet, bei denen die Knoten Punkte im Euklidischen Raum sind.
Die Eigenschaften dieser zufälligen Graphen werden in der Vorlesung mit Hilfe von stochastischen Techniken untersucht, wobei besonderer Wert auf das asymptotische Verhalten für wachsende Anzahl an Knoten gelegt wird.
Voraussetzungen
Die Vorlesung richtet sich an Master-Studierende der mathematischen Studiengänge. Vorausgesetzt werden Kenntnisse der maßtheoretisch fundierten Wahrscheinlichkeitstheorie. Vorkenntnisse aus der Vorlesung Graph Theory, die ebenfalls im WS 2015/16 angeboten wird, sind nicht notwendig.
Skript
Dies ist eine vorläufige Version des Skriptes (Stand 11.02.2016). Das Passwort wurde in der Vorlesung bekannt gegeben.
Aufgabenblätter
- Aufgabenblatt 1 (Übung am 28.10.2015)
- Aufgabenblatt 2 (Übung am 11.11.2015)
- Aufgabenblatt 3 (Übung am 25.11.2015)
- Aufgabenblatt 4 (Übung am 09.12.2015)
- Aufgabenblatt 5 (Übung am 23.12.2015) Quellcode zu Aufgabe 1
- Aufgabenblatt 6 (Übung am 20.01.2016)
- Aufgabenblatt 7 (Übung am 03.02.2016) Quellcode zu Aufgabe 4
Prüfung
Mündlichen Prüfungen zur Lehrveranstaltung werden am 24.02.2016, 24.03.2016 und 11.04.2016 angeboten. Zur Terminvereinbarung oder, falls Sie an den Terminen verhindert sein sollten, schreiben Sie bitte eine E-Mail an matthias.schulte@kit.edu . Bitte beachten Sie, dass Sie sich trotzdem zur Prüfung anmelden müssen.
Literatur
B. Bollobas (2001): Random Graphs, 2. Auflage, Cambridge University Press, Cambridge.
R. Durret (2010): Random Graph Dynamics, Cambridge University Press, Cambridge.
R. van der Hofstad (2014): Random Graphs and Complex Networks, Vol. I & II, http://www.win.tue.nl/~rhofstad/.
S. Janson, T. Luczak, A. Rucinski (2000): Random Graphs, Wiley-Interscience, New York.
M. Penrose (2003): Random geometric graphs, Oxford University Press, Oxford.