Three Algorithms for Parallel Graph Summarization
Expert Systems · 2026-01 · 43 (1)
DOI: 10.1111/exsy.70179 ↗Kurz gefasst
Fachartikel in der Zeitschrift Expert Systems, online erschienen am 09.12.2025. Verfasst von Till Blume und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Most graph summarization algorithms are tailored to a specific graph summary model and were designed for one‐time computations only, that is, batch‐based computations. We developed a universal approach for parallel graph summarization and three algorithms to compute graph summaries—a batch‐based algorithm for static graphs, an incremental algorithm for evolving graphs, and a hash‐based algorithm that scales to large graphs and large schema structures, that is, using paths of length up to to define vertex equivalence. Experimenting with benchmark and real‐world datasets, we observe that the incremental algorithm almost always runs faster than batch computation, even when 50% of the graph changes, and even when using fewer cores; however, it only uses 8% more memory (). Furthermore, we show that the hash‐based algorithm can compute 10‐hop equivalent subgraphs on graphs with over 10 M edges within seconds, on graphs of 100 + M edges within a few minutes, and on graphs of 1 + B edges in less than an hour. We analyse the complexity of our algorithms in detail and prove that the incremental algorithm is correct. Overall, we show with these three algorithms that our parallel approach for graph summarisation is versatile and opens the path for various applications that require summaries of large‐scale graphs.
Zitieren
APA
Blume, T., Rau, J., Richerby, D., & Scherp, A. (2026). Three Algorithms for Parallel Graph Summarization. Expert Systems, 43(1). https://doi.org/10.1111/exsy.70179
Vancouver
Blume T, Rau J, Richerby D, Scherp A. Three Algorithms for Parallel Graph Summarization. Expert Systems. 2026;43(1). doi:10.1111/exsy.70179
BibTeX
@article{Blume2026,
author = {Blume, Till and Rau, Jannik and Richerby, David and Scherp, Ansgar},
title = {Three Algorithms for Parallel Graph Summarization},
journal = {Expert Systems},
year = {2026},
volume = {43},
number = {1},
doi = {10.1111/exsy.70179}
}
EUVIMED