Institut für Theoretische Informatik, Algorithmik

Algorithmische Methoden der Netzwerkanalyse

Allgemeines

Aktuelles

Vorlesungen / Übung

Datum Thema Material
23.10. Einführung, Grundbegriffe der Graphentheorie
30.10 Gradfolgen
06.11 Zusammenhang
13.11 Zusammenhang (Teil 2)
20.11 Zusammenhang
27.11 Zentralität - Einführung
04.12 Zentralitäten: Closeness und Betweenness
11.12 Zentralitäten: Closeness und Betweenness
18.12 Clustering
08.01 Clustering: Qualitätsmaße
15.01 Clustering: Kleinbergs Axiomatik J. Kleinberg. An Impossibility Theorem for Clustering.
22.01 Clustering: Iterative Clusterungsverfahren
29.01 Clustering: Singel Linkage und MSTs
05.02 Clustering: Modularity
12.02

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 ]