Vorlesung Algorithmische Methoden zur Netzwerkanalyse (SS 2017)

  • Dozent: Prof. Dr. Henning Meyerhenke
  • Übungsleitung: Prof. Dr. Henning Meyerhenke, Elisabetta Bergamini
  • Zeiten: Dienstags 14:00-15:30 (SR 301) und mittwochs 14:00-15:30 (SR 301), 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

  • 20.07.: Neue Skriptversion online.
  • 12.07.: Alle Folien sind online.

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

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. Die Materialien werden im Laufe des Semesters online gestellt.

Mittlerweile ist auch der (fast) komplette Foliensatz erhätlich (Termin 6 zur Betweenness-Approximation sowie die NetworKit-Einführung sind nicht enthalten und separat herunterzuladen).

KW Di (14:00-15:30) Mi (14:00-15:30)
17 1: Einführung, Gradverteilung, k-Kern-Zerlegung 2: Cluster-Koeffizienten
18 3: NetworKit-Grundlagen I, Eigenvektor-Zentralität 4: EVZ, PageRank, NetworKit-Grundlagen II
19 5: Betweenness ---
20 6: Betweenness-Approximation, Präsenzübung 7: Closeness und paarweise Distanzen, ÜB1
21 8: Distanzanfragen, ÜB2 9: Durchmesser
22 --- 10: Zusammenhang
23 11: Präsenzübung, Havel-Hakimi 12: ÜB3, Erdös-Gallai-Theorem, Erdös-Renyi-Graphen
24 13: ÜB3, Erdös-Renyi-Graphen 14: Präsenzübungen, Graphgeneratoren: BA, CL, R-MAT
25 --- ---
26 15: RHGs, ÜB4 (Do!) 16: Community Detection
27 17: ÜB4, ÜB5 18: Community Detection
28 19: Clustering, einfache Krankheitsausbreitungen 20: Optimierung zur Cyberabwehr in Netzwerken
29 (24. August, 10:30 Uhr, Raum 033) 21: Zusammenfassung, ÜB6, Prüfungsvorbereitung ---

Übungsblätter

Skript

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.