Webrelaunch 2020

Der Modellansatz: Modell038 - Graphpartitionierung

modellansatz.de/graphpartitionierung

Bei genauem Hinsehen finden wir die Naturwissenschaft und besonders Mathematik überall in unserem Leben, vom Wasserhahn über die automatischen Temporegelungen an Autobahnen, in der Medizintechnik bis hin zum Mobiltelefon. Woran die Forscher, Absolventen und Lehrenden in Karlsruhe gerade tüfteln, erfahren wir im Modellansatz Podcast aus erster Hand.

Der Modellansatz: Graphpartitionierung, Visualisierung: Christian Schulz/KaHIP, Komposition: Sebastian Ritterbusch

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