Graphpartitionierung

Ein Graph ist eine Menge von Knoten und Kanten zwischen diesen
Knoten. Man unterscheidet zwischen gerichteten Graphen, wo
Einbahnstraßen darstellbar sind, oder den ungerichteten Graphen,
wo Beziehungen zwischen zwei Knoten immer beidseitig sind.
Beispiele sind die graphische Darstellung von Beziehungen in
einem sozialen Netz oder Straßennetze, für deren Verarbeitung das
Forschungsgebiet von Christian Schulz immer bedeutender wird, wie
wir in seinem Gespräch mit Gudrun Thäter erfahren.


Eine wichtige Aufgabe im Umgang mit Graphen ist die Aufteilung
(oder fachsprachlich Partitionierung), von Graphen in kleinere
Teile. Dies kommt z.B. der Parallelisierung der Arbeit auf den
Graphen zugute, und ist unumgänglich, wenn Graphen eine Größe
haben, die nicht mehr von einem Prozessor bearbeitet werden kann.
Ein wichtiges Merkmal ist hier, die Aufteilung möglichst
gleichmäßig vorzunehmen, damit die Aufteilung von z.B. Rechenzeit
gleichmäßig erfolgt, und gleichzeitig wenig Kommunikation
zwischen der Bearbeitung der Einzelteile erforderlich ist. Es
geht um eine möglichst gute Skalierbarkeit der Graphverarbeitung.


Ein wichtiges Anwendungsproblem ist die Routenplanung, bei der
zwischen zwei Punkten auf der Erde die zeitlich kürzeste
Verbindung berechnet werden soll. In der Informatik ist der
Dijkstra-Algorithmus der passende Basis-Algorithmus für diese
Aufgabe, doch er ist für große Graphen in seiner ursprünglichen
Form sehr ineffizient. In Kombination mit einer passenden
Graphpartitionierung und Algorithmen kann man das Verfahren
deutlich effizienter ausführen und beschleunigen.


Ein klassisches Verfahren zur Aufteilung ist das
Mehrschichtverfahren über die Laplace-Matrix, wo ausgenutzt wird,
dass zwischen den Eigenwerten der Matrix und der Schnittstruktur
des Graphen enge Zusammenhänge bestehen. Dieses Verfahren wurde
zum Mehrschichtverfahren für Graphen weiterentwickelt, bei dem in
einer sogenannten Kontraktion benachbarte Knoten und parallele
Kanten jeweils zusammengeführt werden, und der Graph zu einem
kleinen und kantengewichteten Graph vereinfacht wird. Schließlich
wird das Problem auf einem vereinfachten, groben Gitter gelöst,
und dann jeweils mit lokalen Suchen auf feinere Graphen
erweitert. Für die Kontraktion werden Heuristiken und
Kantenbewertungsfunktionen verwendet.


Ein weiterer Ansatz sind auch evolutionäre Algorithmen. Dabei
wurde eine allgemeinere Umgebung geschaffen, die auf eine weite
Klasse von Optimierungsproblemen angewendet werden kann.


Die Graphentheorie ist natürlich auch Teil der diskreten
Mathematik, und besonders berühmt ist auch das Traveling
Salesperson Problem. Gleichzeitig ist das Thema aber auch in der
Theoretischen Informatik, im Algorithm Engineering und in der
Software-Entwicklung beheimatet.
Literatur und Zusatzinformationen

C. Schulz: High Quality Graph Partitioning, PhD thesis.
Karlsruhe Institute of Technology, 2013.

P. Sanders, C. Schulz: Distributed Evolutionary Graph
Partitioning, Proceedings of the 12th Workshop on Algorithm
Engineering and Experimentation (ALENEX'12), pages 16--19, 2012.

P. Sanders, C. Schulz: High Quality Graph Partitioning,
Proceedings of the 10th DIMACS Implementation Challenge Workshop:
Graph Partitioning and Graph Clustering, pages 1--17, AMS, 2013.

P. Sanders, C. Schulz: Think Locally, Act Globally: Highly
Balanced Graph Partitioning, proceedings of the 12th
International Symposium on Experimental Algorithms (SEA'13),
volume 7933 of LNCS, pages 164--175, 2013.

R. Glantz, H. Meyerhenke, C. Schulz: Tree-based Coarsening
and Partitioning of Complex Networks, Technical Report, Karlsruhe
Institute of Technology, 2014.

KaHIP Homepage

KaHIP auf Twitter

Christian Schulz auf Twitter

Podcast: Death of a traveling salesman