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


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.


Projektleitung
Meyerhenke, Henning Prof. Dr. (Details) (Modellierung und Analyse komplexer Systeme)

Laufzeit
Projektstart: 10/2017
Projektende: 11/2020

Forschungsbereiche
Theoretische Informatik

Forschungsfelder
Big Data, Mathematical Modeling and algorithms for exascale simulations and data-intensive science, Theoretische Informatik

Publikationen
A. van der Grinten, E. Angriman, H. Meyerhenke: Scaling up Network Centrality Computations ‐ a Brief Overview. Accepted by it - Information Technology. Feb. 2020 (to appear), de Gruyter.

Mehmet Şimşek, Henning Meyerhenke, Combined centrality measures for an improved characterization of influence spread in social networks, Journal of Complex Networks, Volume 8, Issue 1, February 2020, cnz048, https://doi.org/10.1093/comnet/cnz048

Alexander van der Grinten, Henning Meyerhenke: Scaling Betweenness Approximation to Billions of Edges by MPI-based Adaptive Sampling. In Proc. 34th IEEE Intl. Parallel and Distributed Processing Symposium (IPDPS'20), IEEE Computer Society.

Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski, Daniel Zügner, Stephan Günnemann, Henning Meyerhenke: Group Centrality Maximization for Large-scale Graphs. ALENEX 2020: 56-69.

Eugenio Angriman, Alexander van der Grinten, Henning Meyerhenke: Local Search for Group Closeness Maximization on Big Graphs. In Proc. IEEE Intl. Conf. Big Data 2019, IEEE Computer Society.

Eugenio Angriman, Alexander van der Grinten, Moritz von Looz, Henning Meyerhenke, Martin Nöllenburg, Maria Predari, Charilaos Tzovas: Guidelines for Experimental Algorithmics: A Case Study in Network Analysis. Algorithms 12(7): 127 (2019)

Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke: Computing top-k Closeness Centrality Faster in Unweighted Graphs. TKDD 13(5): 53:1-53:40 (2019)

Alexander van der Grinten, Henning Meyerhenke: Scaling up Network Centrality Computations. DATE 2019: 1319-1324

Alexander van der Grinten, Eugenio Angriman, Henning Meyerhenke: Parallel Adaptive Sampling with Almost No Synchronization. Euro-Par 2019: 434-447

Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo, Henning Meyerhenke, Lorenzo Severini, Yllka Velaj: Improving the Betweenness Centrality of a Node by Adding Links. ACM Journal of Experimental Algorithmics 23 (2018)

Moritz von Looz, Henning Meyerhenke: Updating Dynamic Random Hyperbolic Graphs in Sublinear Time. ACM Journal of Experimental Algorithmics 23 (2018)

Henning Meyerhenke, Martin Nöllenburg, Christian Schulz: Drawing Large Graphs by Multilevel Maxent-Stress Optimization. IEEE Trans. Vis. Comput. Graph. 24(5): 1814-1827 (2018)

Patrick Bisenius, Elisabetta Bergamini, Eugenio Angriman, Henning Meyerhenke: Computing Top-k Closeness Centrality in Fully-dynamic Graphs. ALENEX 2018: 21-35

Elisabetta Bergamini, Tanya Gonser, Henning Meyerhenke: Scaling up Group Closeness Maximization. ALENEX 2018: 209-222

Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, Henning Meyerhenke: Scalable Katz Ranking Computation in Large Static and Dynamic Graphs. ESA 2018: 42:1-42:14

Roland Glantz, Henning Meyerhenke: Many-to-many Correspondences between Partitions: Introducing a Cut-based Approach. SDM 2018: 1-9

Zuletzt aktualisiert 2021-04-01 um 17:47