Allgemeine Ziele

Clusterung von Graphen ist ein Bereich, in dem Methoden des Algorithm Engineering einen entscheidenden Beitrag leisten können. Theoretische Erkenntnisse zu formal sauber gefassten Optimierungsproblemen aus diesem Gebiet dürften nur von begrenztem Nutzen sein, da sie typischerweise nicht alle relevanten Aspekte der Clusterung von Graphen abdecken. Andererseits reichen experimentelle Ergebnisse zu bestimmten Anwendungen bzw. Datensätzen nicht aus, um anwendungsübergreifende Erkenntnisse zu gewinnen.Wegen des wachsenden Bedarfs an Methoden zur Auswertung der riesigen Datenmengen, die heutzutage elektronisch erfasst werden, sind allgemeiner einsetzbare Algorithmen aber unbedingt erforderlich. Nicht zuletzt ist die Algorithmik auch deshalb gefordert, bessere Verfahren bereitzustellen, weil in den letzten Jahren die Physik im Rahmen des dort stark forcierten Gebiets „Komplexe Systeme“ in diesen Bereich (dort als „Entdeckung von Communities“ bezeichnet) drängt. Unserer Ansicht nach hat Algorithm Engineering der Vorgehensweise der Physik etwas entgegenzusetzen, da es geeignete Methoden bereit stellt, um auch zu allgemeingültigen bzw. übertragbaren Erkenntnissen zu gelangen.

Bei der Umsetzung dieses Vorhabens verfolgen wir langfristig folgende Ziele:

1. Eine systematische Modellierung aller algorithmischen Aspekte des Clustern statischer und sich verändernder Graphen: Systematik von Qualitätsindizes, Formulierung von Vergleichsmaßen für Clusterungen verschiedener statischer Graphen bzw. verschiedener Snapshots eines sich verändernden Graphen.
2. Die Erstellung von Software-Tools, die eine experimentelle Überprüfung von Algorithmen zur Clusterung von Graphen unterstützen. Dazu gehören neben Implementationen von verschiedenen Algorithmen und Qualitätsindizes insbesondere Vergleichsmaße und Prozeduren zum direkten Vergleich von Clusterungen, Graphgeneratoren und eine Datenstruktur zur geeigneten Repräsentation zeitbehafteter Graphen.
3. Die Entwicklung von Algorithmen zur Clusterung von statischen und von sich verändernden Graphen, für die wir anwendungsübergreifende Qualitätsaussagen treffen können. Die Berechnung von Schnitten und Separatoren soll dabei als Hilfsmittel einfließen, aber auch als eigenständiges Thema betrachtet werden.
4. Die Entwicklung von Algorithmen zur Zerlegung und Clusterung vor dem Hintergrund ausgewählter Anwendungsfälle aus der Netzwerkanalyse. Möglicherweise wird dies auch zu Anwendungsfällen mit sehr großen Graphen führen. In diesem Fall wollen wir auch Modelle (z.B. Streaming-Modell) zur Bearbeitung riesiger Datenmengen betrachten.
5. Die Bereitstellung von Benchmarks. Neben synthetischen Daten wollen wir sinnvolle Benchmarks aus Anwendungsdaten anbieten.