Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

AE Projekt Seminar zur Maximierung der Modularität in großen Graphen

Beschreibung

Ein essenzielles Werkzeug bei der Analyse großer Datenmengen ist das Clustern dieser Daten. Dabei ist man an einer großen Ähnlichkeit innerhalb der Cluster, sowie an einer geringen Ähnlichkeit zwischen den Clustern interessiert. Für Graphen bedeutet das intuitiv, dass man viele Kanten innerhalb von Clustern und wenige Kanten zwischen verschiedenen Clustern hat. Es gibt verschiedene Qualitätsmaße, die diese Intuition formalisieren; eines der wichtigsten ist die Modularität. Obwohl es NP-schwer ist, einen Graphen zu clustern, sodass die Modularität maximiert wird, so gibt es doch einige Heuristiken, die auf praktischen Instanzen schnell sind und gute Ergebnisse liefern. 

Das Ziel dieses Projektseminars ist es, die existierenden Algorithmen bezüglich Laufzeit und Qualität des resultierenden Clusterings zu verbessern. Dabei ist es wichtig, ein Verständnis dafür zu entwickeln, welche Eigenschaften typische Instanzen haben, um diese dann algorithmisch ausnutzen zu können. Über die praktische Verbesserung hinaus ist es aus theoretischer Sicht interessant, unter welchen Voraussetzungen man Garantien für die Laufzeit bzw. für die Qualität des Clusterings beweisen kann.
 

Leistungserfassung

Als Bewertungsgrundlage dient die Abschlusspräsentation (1/3), sowie die schriftliche Ausarbeitung (2/3), in der die Studierenden ihre Ergebnisse darlegen.

Allgemeine Information

  • Semesterwochenstunden : 4
  • ECTS : 6
  • Benotet : Ja
  • Programm : IT-Systems Engineering MA
  • Lehrform : PS
  • Belegungsart : Wahlpflicht
  • Teilnehmeranzahl: max. 3 (FCFS)
  • Anmeldung per Email an die oben genannten Dozenten

Module

  •  IT-Systems Engineering MA

    • ISAE-Konzepte und Methoden
    • ISAE-Spezialisierung
    • ISAE-Techniken und Werkzeuge
    • OSIS-Spezialisierung
    • SAMT-Konzepte und Methoden
    • SAMT-Spezialisierung
    • SAMT-Techniken und Werkzeuge

  •  Data Engineering MA

    • DATA-Konzepte und Methoden
    • DATA-Techniken und Werkzeuge
    • DATA-Spezialisierung

  •  Digital Health MA

    • SCAD-Specialization