Algorithm Engineering for Graph Clustering

Das Ziel des Graphenclustern ist es, einen gegebenen Graph G in Blöcke zu unterteilen, die in sich gut verbunden sind und untereinander schwach. Als Gütekriterium für Graphenclusterungen ist die Zielfunktion modularity sehr verbreitet, Techniken zur Maximierung gibt es viele. Jedoch ist bekannt dass es NP-schwer ist modularity zu maximieren, d.h. in der Praxis werden hauptsächlich Heuristiken zur Optimierung von Modularity eingesetzt. 

In unser Arbeitsgruppe existiert bereits ein Framework für die Partitionierung von Graphen. Die Anzahl Blöcke ist in dem Fall vorgegeben und die Blöcke müssen ungefähr gleich groß sein.  Es handelt sich dabei um Mehrlevelalgorithmen, d.h. der Eingabegraph wird zunächst durch Kontraktionsschritte verkleinert, dann wird das Problem "gelöst" und die Lösung wird levelweise wieder auf den Eingabegraphen projetziert. Dieses Framework enthält interessante Techniken zur Cut-Optimierung, z.B. Flow-Basiert, sehr lokale Suchen und auch globale Techniken. Ziel der Arbeit ist es zu untersuchen wie sich diese Techniken auf das Clustern von Graphen übertragen lassen und sich ggf. auch andere Zielfunktionen zu überlegen.

Vorraussetzungen

• Interesse und solide Kenntnisse uber Algorithmen und Datenstrukturen
• Gute Programmierkentnisse in C++