TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs
Proceedings of the VLDB Endowment · 01.12.2025 · 19 (4) · 644-656
DOI: 10.14778/3785297.3785306 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 18.03.2026. Verfasst von Dian Ouyang und 5 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben.
Abstract (Originalsprache)
In graph theory, the eccentricity of a vertex quantifies its centrality by measuring the maximum distance to any other vertex in the graph. This metric underpins important graph properties such as the diameter (maximum eccentricity) of the graph, which is defined by the minimum and maximum centrality values across all vertices. Due to the substantial time overhead caused by full-graph BFS traversals, researchers have focused on incorporating bounding techniques to accelerate algorithm execution. However, the state-of-the-art approach is unable to identify useless vertices and fails to terminate during the search since its bound update relies on complete traversals. In this paper, we propose a novel framework that uses vertex dominance to identify redundant vertices and introduces a new rule to ensure correct termination after skipping a vertex. In addition, we adopt a merging strategy to reduce the number of traversals. Our method achieves up to two orders of magnitude speedup in runtime compared to the state-of-the-art approach. while efficiently handling graph data at the 100-million scale.
Zitieren
APA
Ouyang, D., Lin, J., Li, W., Zhang, F., Yang, J., & Luo, X. (2025). TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs. Proceedings of the VLDB Endowment, 19(4), 644-656. https://doi.org/10.14778/3785297.3785306
Vancouver
Ouyang D, Lin J, Li W, Zhang F, Yang J, Luo X. TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs. Proceedings of the VLDB Endowment. 2025;19(4):644-656. doi:10.14778/3785297.3785306
BibTeX
@article{Ouyang2025,
author = {Ouyang, Dian and Lin, Jiajie and Li, Wentao and Zhang, Fan and Yang, Jianye and Luo, Xi},
title = {TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {19},
number = {4},
pages = {644--656},
doi = {10.14778/3785297.3785306}
}
EUVIMED