English

The underlying theme of this thesis is the detection of dense regions of an undirected graph G = (V,E). A dense region is a subset of the nodes V' \subset V with many edges between nodes in V' and only few edges to nodes in V \ V'. The identification of these regions is helpful for solving the graph partitioning problem (GPP) and related clustering tasks. The GPP asks for a partition of V into k equally sized subdomains (clusters) such that the number of inter-cluster edges is minimized. Applications that involve problems related to GPP are numerous; they include parallel numerical simulations, network analysis, circuit design, and gene analysis in bioinformatics. GPP and all relevant formulations of related partitioning problems are NP-hard, so that no polynomial-time algorithms for their optimal solution are known. State-of-the-art graph partitioning libraries employ local node-exchanging heuristics within a multilevel framework and yield good solutions in very short time. However, the computed partitions do not necessarily meet the requirements of all users. This includes the choice of the appropriate objective function and the shape of the computed subdomains. Furthermore, due to their sequential nature, the most popular partitioning heuristics are difficult to parallelize, which is necessary for their efficient use as load balancers in parallel applications. For graph clustering problems, where the cluster sizes do not need to be balanced, there is no method which is both highly efficient, delivers high-quality results in many diverse applications, and is theoretically well understood. To overcome these drawbacks, we introduce the disturbed diffusion scheme FOS/C. It is capable of distinguishing dense from sparse graph regions, which we explain by its relation to random walks. The combination of FOS/C with the k-means related framework Bubble yields the iterative and inherently parallel (re)partitioning/clustering algorithm Bubble-FOS/C. In our theoretical investigations on FOS/C and Bubble-FOS/C, we examine the random walk relation and its connection to the pseudoinverse of the input graph's Laplacian matrix. Amongst others, the derived results lead to an enhanced solution process of FOS/C and to a proof that Bubble-FOS/C converges to a local optimum which can be characterized by a potential function. Since Bubble-FOS/C requires the solution of many linear systems, we construct an efficient algebraic multigrid solver, whose graph hierarchy is simultaneously used for a multilevel improvement process of the partitions. Despite the fact that our algebraic multigrid approach is significantly faster than previous implementations, the running time of Bubble-FOS/C is still very high. Thus, its very good solution quality experienced in graph partitioning experiments can hardly be exploited in practice. Further acceleration approaches are discussed, but they are either not always successful or very complicated to implement. That is why we develop in a next step a much faster and easier method for the improvement of partitions. This method is based on a different disturbed diffusive process, which is restricted to local areas of the graph and also contains a high degree of parallelism. By coupling this new technique with Bubble-FOS/C in a multilevel framework based on two different hierarchy construction methods, we obtain our new heuristic DibaP for (re)partitioning and clustering graphs. Compared to Bubble-FOS/C, DibaP shows a considerable acceleration, while retaining the positive properties of the slower algorithm. Extensive experiments with popular benchmark graphs show an extremely good behavior for partitioning graphs stemming from numerical simulations. DibaP computes consistently better results than the state-of-the-art libraries METIS and Jostle. Moreover, with our new algorithm, we have improved a large number of the best known partitions of six widely used benchmark graphs. In the related problems of load balancing by repartitioning and graph clustering, DibaP also improves the solution quality of state-of-the-art programs in many cases. Insofar, our work consists of practical and theoretical advances concerning graph (re)partitioning and graph clustering, achieved by the development of new successful heuristic algorithms and the theoretical analysis of some important properties of these algorithms.

Deutsch

Die grundlegende Thematik der vorliegenden Dissertation ist die Identifizierung dichter Regionen eines ungerichteten Graphen G = (V,E). Eine dichte Region ist dabei eine Teilmenge der Knoten V' \subset V mit vielen Kanten, die zwischen Knoten aus V' verlaufen, aber vergleichsweise wenigen Kanten zu Knoten in V \ V'. Die Bestimmung dieser Gebiete ist bei der Lösung des Graphpartitionierungsproblems (GPP) sowie verwandten Aufgaben der Clusteranalyse hilfreich. Das GPP besteht in der Erstellung einer Partitionierung von V in k gleich große Teilmengen (Partitionen, Cluster) derart, dass die Zahl der Kanten, die zwischen verschiedenen Clustern verlaufen, minimiert wird. Es gibt zahlreiche Anwendungen, die die Lösung dieser oder ähnlicher Fragestellungen benutzen. Beispiele sind unter anderem parallele numerische Simulationen, Netzwerkanalyse, Schaltkreisentwurf sowie Genanalyse in der Bioinformatik. GPP und alle relevanten Formulierungen verwandter Partitionierungsprobleme sind NP-schwer, so dass keine Polynomialzeit-Algorithmen für ihre optimale Lösung bekannt sind. Partitionierungsbibliotheken, die dem aktuellen Stand der Technik entsprechen, benutzen lokale Knotenaustauschheuristiken innerhalb eines mehrstufigen Verbesserungsprozesses. Sie erzielen damit gute Lösungen in sehr kurzer Zeit. Jedoch entsprechen diese Lösungen nicht in jedem Fall den Anforderungen der Benutzer. Dies betrifft zum einen die Wahl der Zielfunktion im Optimierungsprozess, zum anderen die Form der Partitionen. Außerdem sind die am häufigsten eingesetzten Partitionierungsheuristiken schwierig zu parallelisieren, da sie inhärent sequentielle Teile enthalten. Eine solche Parallelisierung ist aber notwendig für den effizienten Einsatz als Lastbalancierer in parallelen Anwendungen. Zur Clusteranalyse von Graphen, bei der die Partitionen bzw. Cluster nicht gleich groß sein müssen, gibt es kein Verfahren, das sowohl sehr effizient arbeitet, Ergebnisse von sehr hoher Qualität in vielen verschiedenen Anwendungen liefert, als auch theoretisch wohlverstanden ist. Um diese Nachteile bestehender Methoden zu beseitigen, entwerfen und untersuchen wir in dieser Arbeit den gestörten Diffusionsprozess FOS/C. Er kann dichte Gebiete eines Graphen von solchen mit wenigen Kanten unterscheiden, was wir mit seiner Beziehung zu Random Walks erklären. Durch die Kombination von FOS/C mit Bubble - einem generischen Verfahren ähnlich zu Lloyds k-means-Algorithmus - erhalten wir den iterativen und inhärent parallelen Algorithmus Bubble-FOS/C zur (Re)Partitionierung und Clusteranalyse von Graphen. In unseren theoretischen Untersuchungen zu FOS/C und Bubble-FOS/C beleuchten wir den Bezug zu Random Walks und zur Pseudoinversen der Laplacematrix des Eingabegraphen. Die dabei erzielten Ergebnisse führen unter anderem zu einem verbesserten Lösungsprozess von FOS/C und zu einem Beweis, dass Bubble-FOS/C gegen ein lokales Optimum konvergiert, welches durch eine Potentialfunktion charakterisiert werden kann. Da Bubble-FOS/C die Lösung vieler linearer Gleichungssysteme erfordert, konstruieren wir einen effizienten Löser auf Basis des algebraischen Mehrgitterverfahrens (AMG). Die Graphhierarchie, die von diesem Löser erstellt wird, benutzen wir gleichzeitig für den mehrstufigen Partitionierungsprozess, der lokale Verbesserungen mit Bubble-FOS/C durchführt. Obwohl unser AMG-Löser eine deutliche Beschleunigung im Vergleich zu vorherigen Implementierungen hervorruft, bleibt die Laufzeit von Bubble-FOS/C weiterhin sehr hoch. Daher kann die gute Lösungsqualität des Algorithmus, die in Experimenten zur Graphpartitionierung beobachtet werden kann, kaum in der Praxis genutzt werden. Weitere Möglichkeiten zur Beschleunigung werden diskutiert, aber sie sind entweder nicht immer erfolgreich oder erfordern eine sehr aufwändige Implementierung. Deshalb entwickeln wir in einem nächsten Schritt eine sehr viel schnellere und einfachere Methode zur Verbesserung von Partitionierungen. Diese Methode basiert auf einem anderen gestörten Diffusionsverfahren, das nur begrenzte Bereiche des Graphen betrachtet und auch einen hohen Grad an Parallelität aufweist. Das neue Verfahren kombinieren wir mit Bubble-FOS/C zu einem neuen mehrstufigen heuristischen Algorithmus namens DibaP. Eine Besonderheit dieser Kombination ist, dass ihre Mehrstufen-Hierarchie durch zwei verschiedene Konstruktionsansätze erstellt wird. Verglichen mit Bubble-FOS/C, zeigt die neue Heuristik eine deutliche Beschleunigung und erhält gleichzeitig die positiven Eigenschaften des langsameren Algorithmus. Ausführliche Experimente zeigen ein extrem gutes Verhalten bei der Partitionierung von Graphen, die aus numerischen Simulationen stammen. DibaP erzeugt durchgängig bessere Ergebnisse als die sehr häufig eingesetzten Bibliotheken METIS und Jostle. Weiterhin haben wir mit unserem neuen Algorithmus eine große Zahl der besten bekannten Partitionierungen von sechs weit verbreiteten Benchmark-Graphen verbessert. Auch in den verwandten Problemen der Lastbalancierung durch Repartitionierung und der Clusteranalyse verbessert DibaP die Lösungsqualität des Stands der Technik in vielen Fällen. Insofern besteht die vorliegende Arbeit aus praktischen und theoretischen Fortschritten für die (Re)Partitionierung und die Clusteranalyse von Graphen durch die Entwicklung neuer erfolgreicher heuristischer Algorithmen und die theoretische Analyse einiger wichtiger Eigenschaften dieser Algorithmen.