Dynamische inexakte High-Performance Algorithmen für Netzwerkzentralitäten und Einbettungen von Graphen

• Antragsteller: Professor Dr. Henning Meyerhenke, seit 9/2022
• Fachliche Zuordnung: Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik ; Theoretische Informatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 446872907

Netzwerke (bzw. Graphen) sind ein weit verbreitetes Werkzeug zur Modellierung einer Vielzahl von real-world Anwendungen. Graph Mining bezeichnet dabei die Aufgabe, Wissen aus Netzwerkdaten zu extrahieren. Diese Netzwerke bestehen oft aus Hunderten Millionen bis zu Milliarden von Kanten. Auf Graphen dieser Größe sind gewöhnlicherweise parallele Algorithmen mit (beinahe) linearer Laufzeit notwendig, um Ergebnisse in annehmbarer Zeit zu erzielen. Unglücklicherweise sind viele Graph-Mining-Probleme jedoch inhärent schwierig und lassen solche Algorithmen nicht zu. Aus diesem Grund werden solche Probleme zunehmend inexakt gelöst, d.h., durch Approximationsalgorithmen oder durch das Relaxieren der Problemstellung. Zusätzliche Herausforderungen resultieren aus dem Fakt, dass real-world Graphen sich oft über Zeit ändern. In diesem Kontext können dynamische Algorithmen eingesetzt werden, um häufige Neuberechnungen zu vermeiden. In der Tat gibt es eine Reihe von dynamischen inexakten Algorithmen für Graph Mining, hauptsächlich in sequentiellen bzw. shared-memory Modellen. In verteiltem Speicher ist das Manipulieren von dynamischen Graphen dagegen noch nicht gut verstanden - obwohl es weitreichende Anwendungen gibt. In diesem Antrag möchten wir dynamische inexakte Algorithmen für Hochleistungsrechner entwerfen. Wir betrachten dabei zwei wichtige Anwendungen, nämlich Netzwerkzentralitäten und Einbettungen von Graphen. Verglichen mit dem Stand der Forschung wird dieser Antrag folgende neue Möglichkeiten eröffnen: (i) wir werden Algorithmen für Hochleistungsrechner entwickeln, die dynamische Graph Mining Probleme signifikant schneller lösen als dies bisher möglich ist, (ii) wir werden in der Lage sein, (inexakte) Ergebnisse mit höherer Lösungsqualität zu berechnen als bisher möglich und (iii) dadurch, dass wir Graphen in verteiltem Speicher unterstützen, wird es möglich sein, unsere Algorithmen zur Analyse von dynamischen Graphen einzusetzen, die zu groß sind, um in den Speicher eines einzelnen Rechners zu passen.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Dr. Alexander van den Grinten, bis 8/2022