Beschleunigung numerischer Berechnungen für die Analyse dynamischer komplexer Netzwerke

• Antragsteller: Professor Dr. Henning Meyerhenke
• Fachliche Zuordnung: Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 425481309

Viele gängige Techniken des Graph Mining und des maschinellen Lernens basieren auf Routinen der linearen Algebra (LA), welche auf großen Datensätzen sehr rechenintensiv sind. Ein wesentliches Beispiel ist die Berechnung vieler Eigenpaare oder eine vollständige Spektralzerlegung der Laplace-Matrix eines Graphen. Die Anwendung dieser Operationen auf Graphen mit Millionen oder Milliarden von Kanten resultiert in hohen Laufzeiten und ist mitunter nicht praktikabel. Außerdem berücksichtigen Bibliotheksimplementierungen von Routinen der LA nicht, wenn sich ein Graph über die Zeit verändert. Da uns solche dynamischen Graphen wie der Web-Graph oder soziale Interaktions-Netzwerke im Überfluss in Praxisanwendungen begegnen, führt diese Nichtberücksichtigung zu Ressourcenverschwendung.Unser Antrag zielt auf deutlich schnellere (dabei inexakte) Algorithmen für LA-Routinen ab, die für dynamische Graph-Mining-Anwendungen eingesetzt werden. Wir möchten Algorithmen entwickeln, die den Zustand des Graphen und des Algorithmus über die Zeit mit geeigneten Datenstrukturen verfolgen; dies vermeidet kostenintensive Neuberechnungen. Außerdem verwenden wir Approximation, um Rechenzeit mit (einer adäquaten) Genauigkeit abzuwägen. Weiterhin nutzen wir gängige strukturelle Eigenschaften von komplexen Netzwerken aus, unserer Hauptklasse von Eingaben. Zu diesem Zweck verbinden wir Ergebnisse und Methoden aus der numerischen LA, dem kombinatorischen wissenschaftlichen Rechnen sowie der theoretischen Informatik miteinander. Ein signifikanter Teil des Projektes soll die erzielten Verbesserungen anhand von drei gängigen algorithmischen Problemstellungen des Graph Mining in dynamischen Szenarien demonstrieren: Clusteranalyse, Ähnlichkeit und Repräsentation. Schlussendlich sollen die entwickelten Algorithmen in die quelloffene Netzwerkanalyse-Software NetworKit integriert werden; auf diese Weise erleichtern wir den Transfer unserer Ergebnisse in die wissenschaftliche Community und beschleunigen zudem verwandte Algorithmen in NetworKit.

• DFG-Verfahren: Sachbeihilfen