Algorithm Engineering für Dynamische und (Re)Streaming Graphpartitionierungsalgorithmen

• Antragsteller: Professor Dr. Christian Schulz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 519626652

Die Verarbeitung großer komplexer Netzwerke hat in letzter Zeit enorme Wichtigkeit bekommen. Manchmal bestehen diese Netzwerke aus Milliarden von Einheiten, die neue Eigenschaften und Strukturen hervorbringen. Die Zerlegung und Analyse dieser Strukturen hilft uns, neue Erkenntnisse über unsere Umgebung zu gewinnen. Da riesige Netzwerke im Überfluss vorhanden sind, besteht ein Bedarf an skalierbaren Algorithmen, um Analysen durchzuführen. Das Partitionierungsproblem fordert eine Unterteilung eines Graphen in eine gegebene Anzahl Blöcke ungefähr gleicher Größe, so dass zwischen den Blöcken nur wenige Kanten liegen. Zur Lösung dieses Problems werden in der Praxis meist heuristische Algorithmen eingesetzt. Im letzten Jahrzehnt haben wir die führenden Codes für die das Problem entwickelt, z.B. zur Graphpartitionierung (KaHIP) oder zur Partitionierung von Hypergraph (KaHyPar). Inzwischen sind unsere Algorithmen gut etabliert und als Algorithmen bekannt, die die besten Lösungen für das jeweilige Problem berechnen. Dieser Erfolg wird durch eine beispielhafte Anwendung der Algorithm Engineering Methodik erreicht. Oft ändern sich die zugrunde liegenden Graphen oder Instanzen im Laufe der Zeit, d. h. im Laufe der Zeit werden Knoten oder Kanten eingefügt oder gelöscht. Daher wurde in den letzten Jahrzehnten eine ganze Reihe von Algorithmen und Datenstrukturen für dynamische Graphen entdeckt. Auf der anderen Seite sind (Re)Streaming-Algorithmen zur Zerlegung von Graphen derzeit ein aufstrebendes Feld. Im Streaming-Modell kommen die Knoten einzeln an und Entscheidungen über Blockzugehörigkeiten müssen direkt getroffen werden. Derzeit ist jedoch in der Praxis bei sehr großen Graphen allerdings eine Lücke zu beobachten: Aktuelle Streaming-Algorithmen berechnen eine viel geringere Lösungsqualität im Vergleich zu ihren Konkurrenten, die die Instanz komplett im Speicher halten können. Der Schwerpunkt des Projekts liegt auf Algorithmen zur dynamischen und (re)streaming Partitionierung von (Hyper)graphen. Dynamische und Streaming-basierte Versionen der Probleme werden in der Praxis nicht ausreichend gut gelöst. Wir werden die Methodik des Algorithm Engineering anwenden, um zu Algorithmen zu gelangen, die wesentlich schneller und bessere Lösungen liefern als bisher möglich. Beispielsweise werden wir dynamische Algorithmen entwickeln, indem wir alle Komponenten des Mehrlevel-Ansatzes dynamisieren. Das Projekt wird ebenfalls die derzeit beobachtete Lücke zwischen (Re)Steaming-Algorithmen und Algorithmen die Graphen im internen Speicher halten können schließen: Wir werden schnelle Streaming-Algorithmen entwickeln, die Verfahren basierend auf Mehrleveltechniken einsetzen und aktuelle lokale Suchtechniken verwenden; somit können qualitativ hochwertige Partitionen von Graphen auf einzelnen Computern mit wenig Speicher berechnet werden. Darüber hinaus werden wir Shared-Memory-Parallelisierung verwenden, um die erforderliche Laufzeit zu reduzieren.

• DFG-Verfahren: Sachbeihilfen