Institut für Theoretische Informatik, Algorithmik

Algorithmische Methoden der Netzwerkanalyse

Allgemeines

Aktuelles

Vorlesungen / Übung

Datum Thema Material
21.10. Multigraph, Graph, Grad 1. Vorlesungsfolien
21.10. Übung zu Gradfolgen 1. Übungsblatt
28.10. Gradfolgen, Wege und Kreise 2. Vorlesungsfolien
04.11. Zusammenhang, Tiefensuche 3. Vorlesungsfolien DFS-Beispiel (2x1)
04.11. Übung zu Gradfolgen, Praxisübung 2. Übungsblatt
11.11. Algorithmen zum 2-fachen Knoten-/Kantenzusammenhang 4. Vorlesungsfolien
18.11. Starker Zusammenhang, Kerne, Zentralitäten 5. Vorlesungsfolien
18.11. Übung zu Zusammenhang und Tiefensuche, Praxisübung 3. Übungsblatt
25.11. (Abstands-)Zentralitäten, Closeness, Betweenness 6. Vorlesungsfolien
02.12. Abstandszentralitäten, Closeness, Betweenness 7. Vorlesungsfolien
02.12. Übung zu Zusammenhang, Kerne und Zentralitäten, Praxisübung 4. Übungsblatt
09.12. Betweenness, Rückkopplungszentralitäten 8. Vorlesungsfolien
13.01. Clusterung (Einführung) 9. Vorlesungsfolien
13.01. Übung zu Zentralitäten 5. Übungsblatt
20.01. Clusterung: Einführung und Editierdistanzen 10. Vorlesungsfolien
20.01. Übung zu Zentralitäten 6. Übungsblatt
27.01. Clusterung: Qualitätsindizes 11. Vorlesungsfolien
27.01. Übung zur Editierdistanz 7. Übungsblatt
03.02. Clustering: Linkage und Splitting; Kleinbergs Theorem 12. Vorlesungsfolien
10.02. Clustering: Kleinbergs Theorem
10.02. Übung zum Correlation Clustering 8. Übungsblatt

Beschreibung

Netzwerke sind heutzutage allgegenwärtig. Neben physisch realisierten Netzwerken wie z.B. in der Elektrotechnik oder dem Transportwesen werden zunehmend auch abstrakte Netzwerke wie z.B. die Verbindungsstruktur des WWW oder Konstellationen politischer Akteure analysiert. Bedingt durch die Vielzahl der Anwendungen und resultierenden Fragestellungen kommt dabei ein reicher Methodenkatalog zur Anwendung, der auf interessante Zusammenhänge zwischen Graphentheorie, Linearer Algebra und probabilistischen Methoden führt.

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.

Literatur

  • D. Jungnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathmatics (ACM) Volume 5, Springer. [ html ]
  • G. Sierksma and H. Hoogeveen, Seven Criteria for Integer Sequences Being Graphic, Journal of Graph Theory, 15(2), p. 223-231, 1991. [ html | pdf ]
  • R. Shamir, R. Sharan, and D. Tsur, Cluster Graph Modification Problems, In Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'02), LNCS 2573, pp. 379-390, 2002. [ html | pdf ]
  • J. Kleinberg, An Impossibility Theorem for Clustering, In Proceedings of 15th Conference: Neural Information Processing Systems, 2000. [ pdf ]