Vorlesung: Zufällige Graphen (Sommersemester 2020)
Einführung
Graphen
sind abstrakte Modelle für Netzwerke und bestehen aus Knoten und Kanten, die jeweils zwei Knoten verbinden.
Beispiele umfassen
- das Netzwerk der Neuronen in einem menschlichen Gehirn, die über Axone verbunden sind,
- die Proteine von Hefezellen, die verbunden sind, wenn sie gemeinsam an einer chemischen Reaktion teilnehmen,
- Websites im Internet mit Links als Kanten,
- die Finanzstruktur aller Banken, die sich Geld leihen und darüber in Verbindung stehen,
- Lieferketten zwischen Fabriken,
- elektrische Netzwerke mit Erzeugern und Verbrauchern, die mit Kabeln verbunden sind,
- Kontaktnetzwerke für die Ausbreitung von Nachrichten, Krankheiten oder Memes, sowohl analog als auch digital,
- ...
Bei der Analyse von Netzwerken sucht man nach Merkmalen, Parameter, Kenngrößen,
die die lokale und globale Struktur des Netzwerks beschreiben.
Diese sind oft statistischer Natur.
Beispiele sind der durchschnittliche Knotengrad, also die durchschnittliche Anzahl an Nachbarn eines Knoten,
die statistische Verteilung des Knotengrades,
oder die durchschnittliche Länge einer kürzesten Verbindung zwischen zwei zufällig ausgewählten Knoten,
die Ausfallsicherheit, also welchen Anteil der Knoten oder der Kanten man entfernen kann bevor das Netzwerk in mehrere Teile zerbricht,
oder wie ansteckend eine Krankheit höchstens sein darf, so dass sie gerade noch von alleine ausstirbt.
Die Analyse vieler Netzwerke gestaltet sich aber aus verschiedensten Gründen als schwierig.
Problematische Faktoren können die Größe und Komplexität eines Netzwerks sein,
oft gibt es Schwierigkeiten, die Netzwerkstruktur im Ganzen überhaupt zu messen und erfassen,
und viele Netzwerke verändern sich zudem über die Zeit.
Oft ist man also gezwungen, mit partiellen Daten über ein Netzwerk
die relevanten Parameter zu schätzen.
Dazu untersucht man in der Theorie zufälliger Graphen verschiedene Modelle zufälliger Graphen.
Die Vorlesung orientiert sich in großen Teilen am Buch
Random Graphs and Complex Networks
von Remco van der Hofstad.
- Als Einstieg führen wir graphentheoretische Grundlagen ein und wiederholen einige stochastische Fakten.
- Wir beginnen mit zufälligen Bäumen, die schon länger erforscht werden und einfacher zu verstehen sind als Graphen.
Sie erweisen außerdem als essenzielles Hilfsmittel bei der Untersuchung komplizierterer Modelle.
- Als nächstes wenden wir uns dem einfachsten zufälligen Graphen, dem Erdős-Renyi-Graph zu,
bei dem alle Kanten unabhängig voneinander mit vorgegebener Wahrscheinlichkeit vorhanden sind.
Es stellt sich heraus, dass dieser zufällige Graph für viele Anwendungen nicht die richtigen Eigenschaften mitbringt.
- Deshalb stellen wir den generalized random graph, eine Verallgemeinerung des Erdős-Renyi-Graphen,
und das Konfigurationsmodell vor, mit denen man zufällige Graphen mit in der Realität beobachteten Eigenschaften herstellen kann.
- Das Preferential Attachment-Modell versucht eine Erklärung, wie sich realistische komplexe Netzwerke in Selbstorganisation bilden.
- Im Weiteren Verlauf der Vorlesung studieren wir die eingeführten Modelle zufälligen Graphen mit Hilfe fortgeschrittener Techniken eingehender,
um weitere Eigenschaften und typisches Verhalten zufälliger Graphen zu verstehen.
Dazu gehört das Kleine-Welt-Phänomen und die "Baumartigkeit" der zufälligen Graphen.
- Wenn die Zeit es zulässt, betrachten wir statistische Zugänge, um Grapheneigenschaften und -parameter zu schätzen.
Ablauf
Die Vorlesungszeiten sind Montags und Donnerstags jeweils von 14:15 bis 15:45 Uhr.
Für die Übung werden individuelle Termine gefunden.
Am Ende des Semseters findet eine mündliche Prüfung statt.
Aufgrund der derzeitigen Ausnahmesituation mit Betretungsverbot für den Campus
wird die Vorlesung bis auf weiteres digital stattfinden.
Dazu plane ich, den üblichen Verlauf von Vorlesung und Übung umzustellen.
- Die Teilnehmerinnen und Teilnehmer bereiten den Stoff der jeweiligen Vorlesungseinheit
zu Hause anhand der angegebenen Literatur vor.
- In der Vorlesung besprechen wir im Rahmen einer Videokonferenz den Vorlesungsstoff,
füllen Lücken,
klären Fragen,
beleuchten Kontext,
betrachten Anwendungsbeispiele,
lösen den Text ergänzende Aufgaben,
erarbeiten zielführende Strategien zum Umgang mit mathematischen Texten
und gehen auf Wünsche aller Anwesenden ein.
Dabei können alle zur Beantwortung von Fragen und Klärung von Problemen beitragen,
was den Verständnisgrad des Stoffes für alle vertiefen wird.
- Der Umfang der Hausaufgaben wird reduziert,
denn die Vorbereitung des Vorlesungsstoffes benötigt ja auch Zeit.
In der Übung werden über den Text hinausgehende Fragestellungen behandelt.
Je nach Motivation der Beteiligten können dabei auch Computer zum Einsatz kommen.
- Der Ablauf wird im laufenden Semester nach Bedarf angepasst.
Bitte melden Sie sich in
Moodle
für die Vorlesung an, damit ich Ihnen rechtzeitig die Textabschnitte sowie die Informationen
zur Videokonferenz zukommen lassen kann.
Inhalt
Zum angegebenen Termin wird in der Videokonferenz von 14:15 Uhr bis 15:45 Uhr folgender Stoff behandelt.
- 23.4.2020: Kapitel 1.1, 1.2, 1.3, 1.4 (bis Fig. 1.4.1), 1.5 und 1.10 aus
Diestel: Graph Theory
(Grundlagen/Notation aus der Graphentheorie)
- 27.4.2020: Kapitel 2.2 aus
v. d. Hofstad: Random Graphs and Complex Networks, Volume I (RGCN I)
(Kopplungen,
zuletzt geändert am 27.04.2020),
Übungsaufgaben: 2.13, 2.14, 2.15, 2.16
- 30.4.2020: RGCN I: Kapitel 1.1, 1.2, 2.3
(Stochastische Ordnung,
zuletzt geändert am 30.04.2020),
Übungsaufgaben: 2.17, 2.18, 2.19
- 04.5.2020: RGCN I: Kapitel 2.4
(Ungleichungen für Wahrscheinlichkeiten,
zuletzt geändert am 04.06.2020),
Übungsaufgaben: 2.20, 2.21
- 07.5.2020: RGCN I: Kapitel 3.1
(Verzweigungsprozesse: Die Aussterbewahrscheinlichkeit,
zuletzt geändert am 11.05.2020)
Übungsaufgaben: 3.1, 3.2, 3.3, 3.6
- 11.5.2020: RGCN I: Kapitel 3.2, 3.3, 3.5
(Verzweigungsprozesse: Verzweigungsprozesse und Irrfahrten,
zuletzt geändert am 11.05.2020)
Übungsaufgaben: 3.8, 3.10, 3.12, 3.13, 3.14, 3.15, 3.16, 3.17
- 14.5.2020: RGCN I: Kapitel 3.6 ohne Theorem 3.17, 3.7
(Verzweigungsprozesse: Poissonsche und Binomial-Verzweigungsprozesse,
zuletzt geändert am 18.06.2020)
Übungsaufgaben: 3.23, 3.28, 3.29, 3.30
- 18.5.2020: RGCN I: Kapitel 4.1, 4.2
(Der Erdős-Renyi-Graphs: subkritisch,
zuletzt geändert am 19.05.2020)
Übungsaufgaben: 4.1, 4.3, 4.5, 4.6, 4.7, 4.10, 4.11
- 21.5.2020: Feiertag
- 25.5.2020: RGCN I: Kapitel 4.3
(Der Erdős-Renyi-Graphs: subkritisch II,
zuletzt geändert am 25.05.2020)
Übungsaufgaben: 4.12, 4.13, 4.14, 4.15
- 28.5.2020: RGCN I: Kapitel 4.4
(Der Erdős-Renyi-Graphs: superkritisch,
zuletzt geändert am 04.06.2020)
Übungsaufgaben: 4.16, 4.17, 4.18, 4.19, 4.20
- 01.6.2020: Feiertag
- 04.6.2020: RGCN I: Kapitel 4.4 zuende, 5.4
(Der Erdős-Renyi-Graphs: Gradverteilung,
zuletzt geändert am 13.06.2020)
Übungsaufgaben: 5.16, 5.14, 5.15
- 08.6.2020: RGCN I: Intermezzo + Kapitel 6.1, 6.2
(Der Generalized Random Graph: Einführung,
zuletzt geändert am 28.06.2020)
Übungsaufgaben: 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8
- 11.6.2020: Feiertag
- 15.6.2020: RGCN I: Theorem 6.6 + Kapitel 6.3, 6.4
(Der Generalized Random Graph: Grade,
zuletzt geändert am 21.06.2020)
Übungsaufgaben: 6.9, 6.10, 6.11, 6.12, 6.14, 6.15, 6.16, 6.17
- 18.6.2020: RGCN I: Kapitel 6.4, 6.6 ohne den Beweis von Theorem 6.14
(Die Verteilung des GRG,
zuletzt geändert am 18.06.2020)
Übungsaufgaben: 6.23, ...
- 22.6.2020: RGCN I: Kapitel 6.7, 6.8
(Asymptotische Äquivalenz von inhomogenen zufälligen Graphen,
zuletzt geändert am 14.07.2020)
Übungsaufgaben: 6.35, 6.36, 6.37, 6.38, 6.39
- 25.6.2020: RGCN I: Kapitel 7.1, 7.2, 7.3
(Das Konfigurationsmodell: Einführung, Erased CM,
zuletzt geändert am 29.06.2020)
Übungsaufgaben: tba
- 29.6.2020: RGCN I: Kapitel 7.4, 7.5,
7.6
(Das Konfigurationsmodell: Wahrscheinlichkeit einfacher Graphen, Verbindung zum GRG, zufällige Knotengrade,
zuletzt geändert am 07.07.2020)
- 02.7.2020: RGCN I: Kapitel 7.7, 7.8
(Das Konfigurationsmodell: Ausblick, Preferential Attachement: Einführung,
zuletzt geändert am 03.07.2020)
- 06.7.2020: RGCN I: Kapitel (2.5,) 8.1, 8.2, 8.3, 8.4
(Preferential Attachement: Einführung,
zuletzt geändert am 09.07.2020)
- 09.7.2020: RGCN I: Kapitel 8.3, 8.4, 8.5, 8.6
(Preferential Attachement: Knotengrade,
zuletzt geändert am 13.07.2020)
- 13.7.2020: RGCN I: Kapitel 8.6
- 16.7.2020: RGCN I: Kapitel 8.9, 1
(Varianten des Preferential Attachement Modells und Überblick,
zuletzt geändert am 18.07.2020)
Hinweise zum Lesen mathematischer Texte
Gehen Sie strukturiert vor.
- Schritt 0: Legen Sie Zettel und Stift bereit.
- Schritt 1: Überfliegen Sie den Text: Versuchen Sie, zu erfassen, worum es geht.
Schlagen Sie unbekannte und wichtig erscheinende englische Wörter nach.
Überspringen Sie die Beweise, rechnen Sie nichts nach,
konzentrieren Sie sich auf die Aussagen und was diese (für Sie) bedeuten.
Teilen Sie den Text im Kopf in grobe thematische Abschnitte
und notieren Sie zu jedem Teil eine stichwortartige Zusammenfassung.
Dabei stellen sich Ihnen vielleicht Fragen,
schreiben Sie diese Fragen für später auf.
- Stufe 2: Lesen Sie den Text nochmal von vorne,
diesmal im Detail und mit Beweisen.
Prüfen Sie bei jeder Aussage, ob Sie diese nachrechnen können.
Beachten Sie dabei den Kontext:
- Manchmal steht direkt nach einer krassen Behauptung eine Erklärung oder ein Hinweis.
- Manchmal braucht man Voraussetzungen aus dem Satz, die nicht nochmal erwähnt werden.
Wenn Sie eine Aussage nachrechnen können, notieren Sie sich kurz, wie das geht.
Wenn nicht, notieren Sie die Aussage auf Ihrer Fragenliste.
- Stufe 3: Schauen Sie Ihre Fragenliste durch.
Können Sie einige Fragen mittlerweile schon beantworten?
Hängen manche Fragen zusammen?
Überprüfen Sie, ob Ihre kurzen Zusammenfassungen der Textabschnitte immer noch zutreffen.
Links
Kontakt
Adresse
TU Dortmund
Fakultät für Mathematik
Lehrstuhl IX
Vogelpothsweg 87
44227 Dortmund
Sie finden uns auf dem sechsten Stock des Mathetowers.
Sekretariat
Janine Textor (Raum M 620)
Tel.: (0231) 755-3063
Fax: (0231) 755-5219
Mail: janine.textor@tu-dortmund.de
Bürozeiten:
Mo. und Do. von 8 bis 12 Uhr
Home Office:
Di. und Fr. von 8 bis 12 Uhr
Weiteres
