Papers › Temporal Betweenness Centrality on Shortest Walks Variants
Temporal Betweenness Centrality on Shortest Walks Variants
Mehdi Naima
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Betweenness centrality has been extensively studied since its introduction in 1977 as a measure of node importance in graphs. This measure has found use in various applications and has been extended to temporal graphs with time-labeled edges. Recent research by Buss et al. and Rymar et al. has shown that it is possible to compute the shortest path betweenness centrality of all nodes in a temporal graph in O(n³ T²) and O(n² m T²) time, respectively, where T is the maximum time, m is the number of temporal edges, and n is the number of nodes. These approaches considered paths that do not take into account contributions from intermediate temporal nodes. In this paper, we study the classical temporal betweenness centrality paths that we call \textit{passive} shortest paths, as well as an alternative variant that we call \textit{active} shortest paths, which takes into account contributions from all temporal nodes. We present an improved analysis of the running time of the classical algorithm for computing betweenness centrality of all nodes, reducing the time complexity to O(n m T+ n² T). Furthermore, for active paths, we show that the betweenness centrality can be computed in O(n m T+ n² T²). We also show that our results hold for different shortest paths variants. Finally, we provide an open-source implementation of our algorithms and conduct experiments on several real-world datasets. We compare the results of the two variants on both the node and time dimensions of the temporal graph, and we also compare the temporal betweenness centrality to its static counterpart. Our experiments suggest that for the shortest foremost variant looking only at the first 10% of the temporal interaction is a very good approximation for the overall top ranked nodes.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections