Clusterung statischer und zeitbehafteter Graphen

Dr. Tanja Hartmann, Dr. rer. nat. Robert Görke, Prof. Dr. Dorothea Wagner

Teilprojekt des Schwerpunktprogramm 1307 Algorithm Engineering der Deutschen Forschungsgemeinschaft

Infolge des rasch anwachsenden Umfangs elektronisch zugänglicher Daten werden Methoden zur Lokalisierung relevanter Information und deren intelligente Organisation immer wichtiger. Für die Algorithmik stellt sich die Herausforderung, effiziente und praktikable Algorithmen zur Clusterung von Daten zur Verfügung zu stellen. Dabei geht es nicht allein darum, gut funktionierende Algorithmen für bestimmte Anwendungen oder Datensätze zu entwickeln, sondern um den systematischen Entwurf von Algorithmen für formal sauber gefasste Probleme und deren Analyse und Evaluation unter Betrachtung angemessener Qualitätskriterien. In diesem Projekt sollen Algorithmen für die Clusterung von Graphen entwickelt werden.

Im Schwerpunkt unseres Interesses liegen Clusterungen, die auf der Intuition beruhen, dichte Teilgraphen, die untereinander nur lose verbunden sind, als Cluster zu identifizieren. Dazu wollen wir eine systematische Klassifikation von Qualitätskriterien zugrunde legen, die einen objektiven Vergleich verschiedener Verfahren zulässt. Wir wollen uns insbesondere mit dem bisher noch neuen Gebiet der Clusterung von sich verändernden oder zeitbehafteten Graphen beschäftigen. Die Bewertung von Algorithmen wird soweit möglich auf theoretischen Analysen beruhen, grundsätzlich jedoch experimentell erfolgen und zwar sowohl anhand geeignet generierter Graphen als auch unter Betrachtung von realistischen Instanzen. Wie im Algorithm Engineering üblich werden wir den gesamten Kreislauf aus Entwurf, Analyse, Implementierung und experimenteller Bewertung durchlaufen, insbesondere die Ergebnisse der Experimente wieder in den Entwurf und die Analyse einbeziehen. Unsere Implementierungen sollen in Form von Software-Tools bestehend aus verschiedenen Algorithmen, Qualitätsindizes, Vergleichsmaßen und Vergleichsprozeduren, Graphgeneratoren, sowie Benchmarks zur Verfügung gestellt werden.