Gestörte Diffusion für die Partitionierung und Clusteranalyse von Graphen

• Applicant: Professor Dr. Burkhard Monien
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 48021675

Die Identifizierung eng vernetzter Merkmalsgruppen (Cluster/Partitionen) in einem Graphen bei gleichzeitiger Minimierung gewisser Kostenfunktionen ist eine wichtige Teilaufgabe in der Bearbeitung vieler wissenschaftlicher Fragestellungen. Neben klassischen informatischen Anwendungen im wissenschaftlichen Rechnen und im VLSI Design sind hier die Analyse von Molekülfragmenten in der Chemie oder Gensequenzen in der Biologie sowie Ähnlichkeitsuntersuchungen in sozialen Netzwerken zu nennen. Die aus der Physik adaptierten informatischen Diffusionsprozesse eignen sich neben der Lastbalancierung in Netzwerken auch zur Berechnung von Struktureigenschaften eines Graphen. Wir haben in der ersten Förderungsphase gestörte Diffusionsverfahren entwickelt, die ein geeignetes Abstandsmaß zwischen Knoten oder Knotenmengen liefern, um entsprechende Cluster- oder Partitionierungsprobleme zu lösen. Innerhalb eines iterativen Frameworks, das lokale Verbesserungsschritte vollzieht, können so mit Hilfe der gestörten Diffusion eng verbundene Graphregionen ermittelt werden. Diese Eigenschaft haben wir erfolgreich eingesetzt, um mit unserem Algorithmus DIBAP für schwierige Instanzen bei Problemen der Partitionierung, Lastbalancierung durch Repartitionierung und Clustering eine hohe Lösungsqualität zu erzielen. Teilweise berechnete DIBAP sogar die besten bekannten Lösungen. In der neuen Förderungsphase wollen wir ganz im Sinne des Algorithm-Engineering-Zyklus unsere bis dato entwickelten Algorithmen tiefergehend theoretisch analysieren und darauf aufbauend Verbesserungen in der praktischen Umsetzung erzielen. Theoretische Erkenntnisse wollen wir hinsichtlich des Optimierungsprozesses sowie der Komplexität des lokalen Suchverfahrens BUBBLE-FOS/C, einer Komponente von DIBAP, gewinnen. Aufbauend auf den Ergebnissen dieser Analyse wollen wir die hohe Lösungsqualität unserer Algorithmen auch auf Instanzen übertragen, die bisher für unsere Verfahren problematisch sind. Zusätzlich wollen wir Methoden entwickeln, die auch auf Graphen mit hohen Knotengraden zusammenhängende Partitionen berechnen. Für den effizienten Einsatz als Lastbalancierer in zeitkritischen Anwendungen wollen wir die Laufzeit von DIBAP für große Partitionszahlen verbessern. Zur Erschließung neuer Anwendungsgebiete wird DIBAP für das Clustering-Problem so erweitert, dass die Clusterzahl k, die nicht Teil der Eingabe ist, automatisch berechnet wird. Daneben erfolgen spezifische Anpassungen an dynamische Graphen und an das Anwendungsgebiet Bildsegmentierung. Die entwickelten Algorithmen werden als Bibliotheken implementiert und anhand anerkannter Benchmarkinstanzen evaluiert. Die Parallelisierung soll neben den bisherigen Technologien mit OpenCL erfolgen, um sehr große Datenmengen auf unterschiedlichen Hardware-Architekturen bearbeiten zu können.

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