Institut für Theoretische Informatik, Algorithmik

Graphpartitionierung und Graphenclustern in Theorie und Praxis

Allgemeines

  • Vorlesung: Asynchron über Videos im Ilias, zusätzliche alle zwei Wochen Freitags um 9:30 30 Minuten Live-Termin via Microsoft Teams, genaue Termine im Ilias.
  • Raum: Online (MS Teams)!
  • Studiengang: Master Informatik, Master Wirtschaftsinformatik, Bachelor Informatik (Zusatzleistungen)
  • Modul: Graphpartitionierung und Graphenclustern in Theorie und Praxis [M-INFO-100758]
  • Anmeldung: Bitte via Ilias anmelden!
  • Prüfung: Mündliche Prüfung, außerdem zusätzlich als Prüfungsleistung anderer Art (siehe Mini-Seminar/-Praktikum)
  • Prüfungstermine: Die mündlichen Prüfungen finden am 11.03. und 25.03.21 statt. Bitte senden Sie zur Vereinbarung eines Termins eine Email an sekr-wagner@ira.uka.de. Aktuell ist geplant, die Prüfungen in Präsenz durchzuführen. Falls dies nicht möglich sein sollte, erhalten Sie Bescheid, ob die Prüfungen per Videokonferenz oder ggf. später durchgeführt werden.

Online-Vorlesungen

Die Vorlesung findet online via vorab produzierte Videos statt. Zusätzlich gibt es alle zwei Wochen eine Live-Veranstaltung via MS Teams mit der Möglichkeit, Fragen zu stellen. Die Terminabfrage findet aktuell im Ilias statt. Alternativ können Fragen auch via Ilias gestellt werden.

Im Arbeitsbereich auf Ilias gibt es sowohl die Videos als auch weiteres Material zur Vorlesung (z.B. Folien).

Inhalt

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 dem 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. Da in der Praxis viele Partitionierungs- und Clusteringprobleme auftreten, werden die besprochenen Probleme vorgestellt und motiviert.

Es werden sowohl theoretische als auch praktische Aspekte der Graphpartitionierung und des Graphenclusterns vermittelt. Dies beinhaltet NP-Schwere-Beweise, heuristische und exakte Algorithmen, sowie parallele und verteilte Algorithmen.

Inhaltlich wird die Vorlesung sich teilweise an der Vorlesung wie sie bis Sommersemester 2017 angeboten wurde orientieren, auf der alten Vorlesungsseite findet sich auch Material dazu. Es werden aber auch einige Inhalte wegfallen und durch neue Inhalte ersetzt werden. Es ist aktuell nicht geplant, dass die Vorlesung wieder regelmäßig auch in zukünftigen Semestern stattfinden wird. Konkret sind folgende Inhalte geplant:

  • Modularity als Qualitätsmaß für disjunkte Cluster
  • Evaluation von Clusterungen
  • Weitere Qualitätsmaße für disjunkte Cluster
  • Parallele und verteilte Algorithmen für disjunkte Cluster
  • Multi-Level Algorithmen für Graphpartitionierung
  • Flussbasierte Algorithmen für Graphpartitionierung
  • Parallele Algorithmen für Graphpartitionierung
  • Lokale Cluster um einzelne Knoten herum
  • Algorithmen für überlappende Cluster
  • Weitere Varianten, z.B. für Graphen mit Knotenattributen oder dynamische Graphen

Termine

Die Vorlesung ist mit 3 SWS angesetzt. Diese werden als zwei Stunden Videomaterial pro Woche sowie einer halben Stunde Live-Veranstaltung via MS Teams realisiert. Die Termine für die Live-Veranstaltungen befinden sich im Ilias. Die Videos werden jeweils bis zum Freitag Abend davor zusammen mit dem dazugehörigen Material (Präsentation/Mitschrieb) im Ilias veröffentlicht.

Mini-Seminar/Praktikum

Neben der mündlichen Prüfung besteht die Erfolgskontrolle auch aus einer Erfolgskontrolle anderer Art nach § 4 Abs. 2 Nr. 3 der SPO. Es wird dabei die Wahl geben zwischen einem kleinen Seminar, in dem Sie sich selbständig in eine Literaturquelle einarbeiten und diese präsentieren sowie Programmierprojekten geben. In den Programmierprojekten soll jeweils ein in der Vorlesung vorgestellter Algorithmus oder ein Maß in NetworKit umgesetzt und kurz evaluiert werden. Hierzu wird es auch eine Einführung in NetworKit geben, es werden allerdings Grundkenntnisse in C++ und Python vorausgesetzt.

Danksagung

Teile der Vorlesung basieren auf einer von Christian Schulz gehaltenen Vorlesung, deren Material wir freundlicherweise auch für diese Vorlesung nutzen dürfen. Herzlichen Dank hierfür!