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.