Clustering of Static and Temporal Graphs

• Applicant: Professorin Dr. Dorothea Wagner
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 48145076

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.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering