Preview

PDF, English - main document Download (5MB) | Terms of use

Abstract

(Hyper)Graph decomposition is a family of problems that aim to break down large (hyper)graphs into smaller sub(hyper)graphs for easier analysis. The importance of this lies in its ability to enable efficient computation on large and complex (hyper)graphs, such as social networks, chemical compounds, and computer networks. This dissertation explores several types of (hyper)graph decomposition problems, including graph partitioning, hypergraph partitioning, local graph clustering, process mapping, and signed graph clustering. Our main focus is on streaming algorithms, local algorithms and multilevel algorithms. In terms of streaming algorithms, we make contributions with highly efficient and effective algorithms for (hyper)graph partitioning and process mapping. In terms of local algorithms, we propose sub-linear algorithms which are effective in detecting high-quality local communities around a given seed node in a graph based on the distribution of a given motif. In terms of multilevel algorithms, we engineer high-quality multilevel algorithms for process mapping and signed graph clustering. We provide a thorough discussion of each algorithm along with experimental results demonstrating their superiority over existing state-of-the-art techniques. The results show that the proposed algorithms achieve improved performance and better solutions in various metrics, making them highly promising for practical applications. Overall, this dissertation showcases the effectiveness of advanced combinatorial algorithmic techniques in solving challenging (hyper)graph decomposition problems.

Translation of abstract (German)

(Hyper-)Graphenzerlegung fasst mehrere Probleme zusammen, bei denen große Graphen oder Hypergraphen zur einfacheren Analyse in kleinere Subgraphen oder Subhypergraphen zerlegt werden. Dies ist bedeutsam, denn es befähigt dazu Berechnungen auf großen und komplexen Graphen und Hypergraphen, wie soziale Netzwerke, chemische Verbindungen und Computernetzwerke, effizient zu machen. Diese Dissertation befasst sich mit der Untersuchung verschiedener Arten von (Hyper-)Graphenzerlegungsproblemen, darunter Graphpartitionierung, Hypergraphpartitionierung, Prozesszuweisung, Signed-Graph-Clustering und Local-Graph-Clustering. Unser Hauptaugenmerk liegt auf Streaming-Algorithmen, lokalen Algorithmen und Multi-Level-Algorithmen. Im Bereich der Streaming-Algorithmen leisten wir Beiträge mit hocheffizienten und effektiven Algorithmen für die (Hyper-)Graphpartitionierung und Prozesszuweisung. Bei den lokalen Algorithmen schlagen wir sub-lineare Algorithmen vor, die auf Grundlage der Verteilung eines bestimmten Motivs hochwertige lokale Cluster um einen gegebenen Startknoten in einem Graphen bestimmen. Was die Multi-Level-Algorithmen betrifft, so entwickeln wir hochwertige Multi-Level-Algorithmen für Prozesszuweisung und Signed-Graph-Clustering. Wir liefern zu jedem Algorithmus eine ausführliche Diskussion zusammen mit experimentellen Ergebnissen, die ihre Überlegenheit gegenüber bestehenden Stand der Technik zeigen. Die Ergebnisse legen dar, dass die vorgeschlagenen Algorithmen eine bessere Laufzeit und bessere Lösungen in verschiedenen Metriken erzielen, womit sie für praktische Anwendungen sehr vielversprechend sind. Insgesamt zeigt diese Dissertation die Effektivität fortschrittlicher kombinatorischer algorithmischer Techniken bei der Lösung anspruchsvoller (Hyper-)Graphenzerlegungsprobleme.