Home | english  | Impressum | Sitemap | KIT

Graphpartitionierung und Graphenclustern in Theorie und Praxis

Graphpartitionierung und Graphenclustern in Theorie und Praxis
Typ: Vorlesung (V)
Semester: SS 2014
Ort:

Geb. 50.34, Raum 236 

Zeit: Dienstag 09:45 bis 11:15 Uhr

Dozent:

Prof. Dr. Peter Sanders
Dr. Christian Schulz
Übungsleitung: Sebastian Schlag

 

 

LVNr.: 2400008
News: Prüfungstermine im August und September nach Vereinbarung per Email. Bitte beachten Sie: Sie müssen sich vor der Prüfung am Studierendenportal für diese Veranstaltung anmelden.

Kontext
 
Viele Anwendungen der Informatik beinhalten das Clustern und die Partitionierung von Graphen, z.B. die Finite Element Methode in wissenschaftlichen Simulationen, Digitaler Schaltkreisentwurf, Routenplanung, Analyse des Webgraphen oder auch die Analyse von Sozialen Netzwerken.

Ein bekanntes Beispiel, in der gute Partitionierungen von unstrukturierten Graphen benötigt werden, ist die Parallelverarbeitung. Hier müssen Graphen partitioniert werden, um Berechnungen gleichmäßig auf eine gegebene Anzahl von Prozessoren zu verteilen und die Kommunikation zwischen diesen zu minimieren. Wenn man k Prozessoren verwenden möchte, muss der Graph in k ungefähr gleich große Blöcke aufgeteilt werden, so dass die Anzahl Kanten zwischen den Blöcken minimal ist.


Veranstaltungsziele

Ziel der Vorlesung ist es, den Studierenden einen ersten Einblick in die Problematik des Graphpartitionierens und des Graphenclusterns zu vermitteln und dabei Wissen aus der Graphentheorie sowie der Algorithmik umzusetzen. Auf der einen Seite werden die auftretenden Fragestellungen auf ihren algorithmischen Kern reduziert und anschließend effizient gelöst. Auf der anderen Seite, werden verschiedene Modellierungen und deren Interpretationen behandelt.
 
Material
Themen für Miniseminar oder Programmieraufgabe
 
Inhalte

Da in der Praxis viele Partitionierungs- und Clusteringprobleme auftreten, werden die besprochene Probleme vorgestellt und motiviert. Es werden sowohl die theoretischen als auch die praktischen Aspekte der Graphpartitionierung und des Graphenclusterns vermitteln. Dies beinhaltet Heuristiken, Meta-Heuristiken, evolutionäre und genetische Algorithmen sowie Approximations- und Streamingalgorithmen.
 
Detailierter Inhalt der Vorlesung:
  • Definition von Graphpartitionierungs- und clustering Problemen
  • Verschiedene Zielfunktionen (Kantenschnitt, Conductance, Modularity, ...)
  • NP-Härte von GP und GC
  • Exakte Partitionierung und exaktes Clustern
  • Spektrale Partitionierung und Clusterung
  • Approximationsalgorithmus von Arora-Rao-Vazirani
  • Lokale Suchen
  • Multilevel Algorithmen
  • Evolutionäre Algorithmen und Meta-Heuristiken 
  • Parallele Graphpartitionierung
  • External- und Semi-External Graph Partitioning
  • Streaming Algorithmen für Graph Partitionierung
  • Greedy Agglomeration Algorithmen und Top-Down Approaches
  • Evolutionäre und Parallele Methoden fürs Graphenclustern
  • Min-Cut Tree Clustering
  • Dynamisches Graphenclustern, Online Algorithmen
  • Community Detection with Overlaps
 
Weitere Informationen gibt es hier als PDF.