Vorlesung Algorithmische Methoden zur Netzwerkanalyse (WS 13/14)

Neuigkeiten

  • Für die Prüfung sind alle Vorlesungs- und Übungsinhalte relevant, nicht nur diejenigen, deren Foliensätze hier zur Verfügung stehen!
  • 18.02.: Aktualisierung Foliensatz 3, Folie 12 und Foliensatz 20/21, Folie 13.
  • Der geplante Termin zur Prüfungsvorbereitung ist Montag, 17.2., 14:00 bis ca. 15:00 Uhr im SR 236. Senden Sie bitte Ihre Fragen bis zum 14.2. um 13:00 Uhr an mich per E-Mail!
  • 07.02.: Aktualisierung Foliensatz 19, Folie 9.
  • 17.01.: UB7 online.
  • 14.01.: Foliensatz 16 online, dieses Mal mit Latex-Pausen aus technischen Grüden.
  • 23.12.: Foliensatz 15 und UB 6 online. Bitte machen Sie Ihre NetworKit-Repositories privat (falls nicht schon geschehen), Sie können Ihren Kommilitonen bei Bedarf Zugriffsrechte geben.
  • 14.11.: Neue Richtlinien zur Entwicklung mit NetworKit.
  • Diese Veranstaltung ist auch im Diplomstudiengang prüfbar. Als Vertiefungsgebiete sind Theoretische Grundlagen und Algorithmentechnik möglich.
  • Prüfungstermine
  • 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 (15:45-17:15)
43 --- Foliensatz 1a: Orga, Einführung, Foliensatz 1b: Gradverteilung, k-Kern-Zerlegung
44 Foliensatz 2: k-Kern-Zerlegung, Clustering-Koeffizient Foliensatz 3: Clusterkoeffizienten, Zusammenhang
45 Foliensatz 4: Zusammenhang, Durchmesser Foliensatz 5: Durchmesser, paarweise Distanzen
46 Foliensatz 6: Paarweise Distanzen und kürzeste Wege Foliensatz 7: Paarweise kürzeste Wege
47 Foliensatz 8: EVZ und PageRank ---
48 Foliensatz 9: PageRank, BC, CC Foliensatz 10: Abschluss Zentralitätsmaße
49 Foliensatz 11: Zufallsgraphen, Gradfolgen Foliensatz 12: Gradfolgen
50 Foliensatz 13: Netzwerkmodelle Foliensatz 14: Netzwerke mit hyp. Geometrie
51 Foliensatz 15: Clustering in Netzwerken ---
2 --- Foliensatz 16: Spektrales Clustering, lokale Greedy-Methoden
3 --- Foliensatz 17: High-performance Community Detection
4 kernel-k-means ---
5 Foliensatz 19: Clustering mit Netzwerkflüssen Foliensatz 20-21: Epidemien in Netzwerken
6 Foliensatz 20-21: Epidemien in Netzwerken verlegt auf 17.2. als Prüfungsvorbereitung im Raum 236

Übungsblätter

Literatur