Beschleunigung numerischer Berechnungen für die Analyse dynamischer komplexer Netzwerke
Zusammenfassung der Projektergebnisse
Viele Methoden zur Graphanalyse und zum maschinellen Lernen verwenden Routinen der linearen Algebra auf großen Datensätzen. Solche Routinen können sehr rechenintensiv sein und dann die verfügbaren Ressourcen übersteigen. Außerdem nutzen selbst moderne Software-Bibliotheken keine dynamischen Veränderungen in diesen Datensätzen aus. Das Ziel von ALMACOM war es daher insbesondere, algebraische Algorithmen zur Graphanalyse für große und dynamische Graphen deutlich zu beschleunigen. Die Graph-Datenstruktur (GDS) Dynamic Hashed Blocks (DHB) wurde speziell für dynamische Graophoperationen entwickelt. Im Vergleich zu etablierten dynamischen GDS sorgt sie für eine deutliche Beschleunigung bei statischen und dynamischen Operationen. DHB diente zudem als Basis für weitere Veröffentlichungen in ALMACOM. Um grundlegende algebraische Routinen zu beschleunigen, haben wir einen neuen MPI-basierten dynamischen Algorithmus zur Multiplikation von dünn besetzten Matrizen entwickelt. Dieser Ansatz konnte zu einem MPI-basierten Algorithmus für dynamische Closeness-Zentralität erweitert werden. Zur Approximation der Diagonale von Pseudoinversen der Laplace-Matrix von Graphen haben wir einen neuen Algorithmus veröffentlicht, der hauptsächlich kombinatorische Techniken nutzt. Dieser erzielt eine höhere Genauigkeit, ist schneller und verbraucht weniger Speicher im Vergleich mit dem Stand der Technik. In veränderter Form nutzten wir diesen Algorithmus auch, um die Diagonale der sogenannten Wald-Matrix eines Graphen zu approximieren, was ebenso zu den oben genannten vorteilhaften Eigenschaften führt. Die Neuordnung (engl. reordering) eines Graphen kann die Cache-Effizienz von Graphenalgorithmen deutlich verbessern. Dazu entwickelten wir einen Mehrebenen-Ansatz, der Graphen auf hierarchische Architekturen abbildet. Dieser ergibt einen besseren Kompromiss aus Qualität und Laufzeit im Vergleich zum Stand der Technik und kann auch zur Neuordnung verwendet werden. Weiterhin entwickelten wir einen statischen und dynamischen Algorithmus zur Berechnung einer Knotenrangfolge gemäß Katz-Zentralität. Der Algorithmus verbessert iterativ untere und obere Schranken auf die Zentralitätswerte, was Qualitätsgarantien erlaubt. Zudem veröffentlichten wir eine dynamische Version des Suitor-Algorithmus für gewichtete Matchings in Graphen. Als eine weitere Anwendung der Approximation von Pseudoinversen betrachteten wir die Optimierung der Robustheit von Graphen. Unsere Algorithmen beschleunigen den etablierten Greedy-Algorithmus deutlich bei geringen Einbußen in der Lösungsqualität.
Projektbezogene Publikationen (Auswahl)
-
Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis. 28th Europ. Symp. on Algorithms (ESA), 6:1–6:24, 2020.
E. Angriman, M. Predari, A. v. d. Grinten & H. Meyerhenke
-
Distributing Sparse Matrix/Graph Applications in Heterogeneous Clusters -an Experimental Study. 2020 IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC), 72-81. IEEE.
Tzovas, Charilaos; Predari, Maria & Meyerhenke, Henning
-
An MPI-based Algorithm for Mapping Complex Networks onto Hierarchical Architectures. Lecture Notes in Computer Science, 167-182. Springer International Publishing.
Predari, Maria; Tzovas, Charilaos; Schulz, Christian & Meyerhenke, Henning
-
New Approximation Algorithms for Forest Closeness Centrality – for Individual Vertices and Vertex Groups. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), 136-144. Society for Industrial and Applied Mathematics.
van der Grinten, Alexander; Angriman, Eugenio; Predari, Maria & Meyerhenke, Henning
-
A Batch-dynamic Suitor Algorithmfor Approximating Maximum Weighted Matching. ACM Journal of Experimental Algorithmics, 27, 1-41.
Angriman, Eugenio; Boroń, Michał & Meyerhenke, Henning
-
A Fast Data Structure for Dynamic Graphs Based on Hash-Indexed Adjacency Blocks. 20th Intl. Symp. on Exp. Alg. (SEA), 11:1–11:18, 2022
A. v. d. Grinten, M. Predari & F. Willich
-
An MPI-Parallel Algorithm for Static and Dynamic Top-k Harmonic Centrality. 2022 IEEE 34th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 100-109. IEEE.
van der Grinten, Alexander; Custers, Geert; Thanh, Duy Le & Meyerhenke, Henning
-
Fast Dynamic Updates and Dynamic SpGEMM on MPI-Distributed Graphs. 2022 IEEE International Conference on Cluster Computing (CLUSTER), 429-439. IEEE.
van der Grinten, Alexander; Custers, Geert; Thanh, Duy Le & Meyerhenke, Henning
-
Faster Greedy Optimization of Resistance-based Graph Robustness. 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 1-8. IEEE.
Predari, Maria; Kooij, Robert & Meyerhenke, Henning
-
Scalable Katz Ranking Computation in Large Static and Dynamic Graphs. ACM Journal of Experimental Algorithmics, 27, 1-16.
Grinten, van der Alexander; Bergamini, Elisabetta; Green, Oded; Bader, David A. & Meyerhenke, Henning
-
Greedy optimization of resistance-based graph robustness with global and local edge insertions. Social Network Analysis and Mining, 13(1).
Predari, Maria; Berner, Lukas; Kooij, Robert & Meyerhenke, Henning
