Gestörte Diffusion für die Partitionierung und Clusteranalyse von Graphen
Final Report Abstract
Die Identifizierung eng vernetzter Teile in Graphen bei gleichzeitiger Minimierung gewisser Kostenfunktionen, wie beispielsweise die Anzahl der Schnittkanten oder Randknoten, ist eine wichtige Teilaufgabe in der Bearbeitung vieler wissenschaftlicher Anwendungen. Prominente Fragestellungen auf diesem Gebiet sind die Partitionierung und Clusteranalyse von Graphen. Für die Lösung dieser Probleme haben wir noch vor der ersten Förderungsphase einen völlig neuen Ansatz entwickelt, der auf dem sog. Diffusionsverfahren beruht und sich von den bisherigen Verfahren gänzlich unterscheidet. Seit dem haben unsere Methode und die erzielten Ergebnisse eine sehr positive Resonanz gefunden, die insbesondere zu einem Best Paper Award an der führenden Tagung für paralleles und verteiltes Rechnen (IEEE International Parallel and Distributed Processing Symposium) sowie einem eingeladenen Vortrag auf der Tagung SIAM Workshop on Combinatorial Scientific Computing (CSC '11) - mit Teilnehmern wie beispielsweise Bruce Hendrickson, Ali Pinar und Iain Duff - geführt hat. In der ersten Förderungsphase hatten wir basierend auf dem o.g. Ansatz einen Algorithmus entwickelt und implementiert, um für schwierige Instanzen bei Problemen der Partitionierung, Lastbalancierung durch Repartitionierung und Clustering eine hohe Lösungsqualität zu erzielen. Sowohl der Algorithmus als auch die zugehörige Software-Bibliothek heißen DIBAP (für diffusionsbasierte Partitionierung). Im Berichtszeitraum haben wir unsere Algorithmen tiefergehend theoretisch analysiert und darauf aufbauend Verbesserungen in der praktischen Umsetzung erzielt. Zunächst haben wir die Implementierung von DIBAP für die parallele Repartitionierung mit dem Message Passing Interface MPI erweitert. Unsere Tests zeigen, dass im Vergleich zu den beiden weit verbreiteten parallelen Bibliotheken ParMetis und Parallel Jostle unser Verfahren so gut wie immer die besten Partitionierungen berechnet. Die Ergebnisse hinsichtlich des Migrationsvolumens sind allerdings nicht so eindeutig. Des Weiteren haben wir unser Verfahren modifiziert, um dem Clusteringproblem zu begegnen. Wir konnten zwar dabei sehr ermutigende Ergebnisse auf sog. Geometrischen Graphen erzielen, allerdings waren wir im Bereich von realen Anwendungen, wie dem Clustern sozialer Netzwerke oder die Bildsegmentierung nicht so erfolgreich. Auf dem Gebiet der theoretischen Analysen haben wir zum einen über ein grundlegendes lokales Optimierungsproblem - das lokale Max-Cut - gezeigt, dass dieses PLS-vollständig ist. Dadurch haben wir ein prominentes offenes Problem gelöst und die Komplexität von mehreren lokalen Optimierungsproblemen bestimmt. Des Weiteren konnten wir zeigen, dass BUBBLE-FOS/C tatsächlich (unter recht schwachen Bedingungen) ein relaxiertes Kantenschnitt-Problem optimal löst. Wir konnten auch beweisen, dass BUBBLE-FOS/C bei der Partitionierung in zwei Teile mindestens eine der beiden Partitionen zusammenhängend lässt.
