Vorlesung Algorithmische Methoden zur Netzwerkanalyse (WS 15/16)
- Dozent: Prof. Dr. Henning Meyerhenke
- Zeiten: Dienstags 11:30-13:00 (SR 236) und donnerstags 14:00-15:30 (SR 236), jeweils im Geb. 50.34 (Infobau)
- SWS: 2+1, 5 LP
- Modul: Algorithmische Methoden zur Netzwerkanalyse (Master Informatik)
- Hinweis: Die Veranstaltung ist mit 2+1 SWS angesetzt, findet aber mit 4 Wochenstunden statt, da einige Termine im Semester aufgrund von Terminkonflikten ausfallen werden. Diese werden rechtzeitig angekündigt.
Neuigkeiten
- 17.11.: Foliensatz 6/7 online, 1-3 korrigiert (Code zu Kernzerlegung).
- 28.10.: Foliensatz 2 und 3 sind online bzw. aktualisiert!
- Prüfungstermine
- Bitte registrieren Sie sich auf unserer Mailingliste!
Beschreibung
Netzwerke in physischer Form oder als Modellierungsgegenstand sind heutzutage allgegenwärtig. Physisch realisierte Netzwerke treten beispielsweise in technischen Bereichen (Strom, Telefon) oder dem Transportwesen auf. Neuerdings gewinnen abstrakte Netzwerke, etwa zur Modellierung der Verbindungsstruktur des World Wide Web oder von sozialen Kontakten, eine große Bedeutung. Bedingt durch die Vielzahl der Anwendungen und resultierenden Fragestellungen, kommt dabei ein reicher Methodenkatalog zur Anwendung. Es werden unter anderem Techniken aus der Graphentheorie und der linearen Algebra angewendet. Außerdem werden interessante Zusammenhänge zu probabilistischen Methoden deutlich.
In dieser Veranstaltung sollen einige der eingesetzten Methoden und deren Grundlagen systematisch behandelt werden. Fragestellungen werden exemplarisch an Anwendungsbeispielen motiviert, der Schwerpunkt wird auf den zur Lösung verwendeten algorithmischen Vorgehensweisen sowie deren Voraussetzungen und Eigenschaften liegen.
Vorläufiger Ablauf und zugehörige Materialien
Materialien werden im Laufe des Semesters online gestellt.
Das Skript dient nur der Ergänzung. Es enthält zum Beispiel Beweise, die nicht auf den Folien stehen.
In der folgenden Tabelle werden die Inhalte der Termine angekündigt sowie nach der Veranstaltung die zugehörigen Materialien verlinkt. Beachten Sie bitte, dass der Ablaufplan vorläufig ist und sich noch ändern kann.
| KW | Di (11:30-13:00) | Do (14:00-15:30) |
|---|---|---|
| 43 | Einführung, Gradfolgen, k-Kern-Zerlegung | k-Kern-Zerlegung, Cluster-Koeffizienten |
| 44 | Cluster-Koeffizienten, Grundlagen, Zusammenhang | ÜB 1, Zusammenhang |
| 45 | Präsenzübung von ÜB 2, Durchmesser, kürzeste Wege | --- |
| 46 | APSP, APD, KW-Anfragen | Übung |
| 47 | KW-Anfragen | Zentralitätsmaße: EV, PR |
| 48 | Zentralitätsmaße: PR, BC | Update PR, BC, BC-Approximation |
| 49 | Nähezentralität, ER | ER, Havel-Hakimi |
| 50 | --- | --- |
| 51 | Theorem von Erdös und Gallai, BA-Graphen | BA, CL, R-MAT |
| 1 | vorlesungsfrei | Hyperbolische Netzwerke |
| 2 | Motivsuche | V/Ü: Motivsuche, Community Detection |
| 3 | V/Ü: Projekte, ÜB 5 | --- |
| 4 | --- | --- |
| 5 | --- | ÜB 6, Community Detection |
| 6 | ÜB 6, Community Detection | Prüfungsvorbereitung |
Übungsblätter
Literatur
- M. E. J. Newman: Networks. An Introduction. Oxford University Press, 2010.
- Ulrik Brandes, Thomas Erlebach (eds.): Network Analysis. Methodological Foundations. Lecture Notes in Computer Science, vol. 3418. Springer-Verlag 2005. ISBN: 978-3-540-24979-5 (Print) 978-3-540-31955-9 (Online).
- Weitere Literaturempfehlungen im Laufe des Semesters auf den Vorlesungsfolien.