FINCA: Schnelle inexakte kombinatorische und algebraische Löser für große Netzwerke

• Antragsteller: Professor Dr. Henning Meyerhenke
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 255185982

Zahlreiche bahnbrechende Technologien generieren Datensätze von enormer Größe. Viele dieser Datensätze lassen sich als Netzwerk modellieren. Die so produzierten Datensätze enthalten wertvolle Informationen, die durch geeignete Algorithmen und Software-Tools zur Analyse extrahiert und weiterverarbeitet werden können.In diesem Folgeantrag (zweite Förderphase) fokussieren wir auf die Verbindung von Distanzen in Netzwerken (inkl. Nichtstandard-Distanzmaßen) mit essentiellen Themen der algorithmischen Netzwerkanalyse: (i) Zentralitätsmaße, einschließlich ihrer (ii) Verallgemeinerung zu Gruppenzentralitäten, (iii) Einflussmaximierung und (iv) Netzwerkhyperbolizität. Zentralitätsmaße geben die Wichtigkeit von Knoten oder Kanten an; wir betrachten Maße, die Knoten gemäß ihres durchschnittlichen Abstands zu anderen Knoten ordnen. Gruppenzentralität zielt wiederum auf die Identifizierung einer Menge von Knoten ab, so dass die Distanz zwischen jedem Knoten und mindestens einem aus der Menge klein ist. Bei der Ausbreitung von Einfluss lässt sich die Wahrscheinlichkeit, dass Einfluss propagiert werden kann, auch als eine Art Distanz auffassen. Schließlich gibt die Eigenschaft der Hyperbolizität an, wie ähnlich der metrische Raum eines Graphen zu dem eines Baumes ist.All diese algorithmischen Aufgaben haben zahlreiche Big-Data-Anwendungen. Dazu gehören unter anderem Marketing-Strategien, Routing und Netzwerksicherheit. Trotzdem haben bisherige Algorithmen deutliche Schwächen, wenn die Eingabe groß ist oder eine komplexe Struktur aufweist. Da viele Realwelt-Datensätze bereits Ungenauigkeiten enthalten, befürworten wir einen inexakten Lösungsprozess mit Approximationsalgorithmen und Heuristiken. Wir werden daher für die genannten Aufgaben deutlich verbesserte Algorithmen für den Einsatz in großen und dynamischen Netzwerken entwickeln und implementieren. Die Eingabegröße, die in akzeptabler Zeit handhabbar ist, soll dabei um mindestens eine Größenordnung im Vergleich zum Stand der Technik verbessert werden.Wir integrieren unsere neuen Methoden in die Open-Source-Software zur Netzwerkanalyse NetworKit, welche wann immer möglich Parallelität mit gemeinsamem Speicher nutzt. Das Werkzeug ist frei und kostenlos für die Allgemeinheit und andere SPP-Projekte zugänglich. Dadurch wird die sofortige Anwendung unserer Beiträge auf Realwelt-Probleme, die skalierbare Codes erfordern, gefördert.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen