Papers › MANTRA: Temporal Betweenness Centrality Approximation through Sampling
MANTRA: Temporal Betweenness Centrality Approximation through Sampling
Antonio Cruciani
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.
We present MANTRA, a framework for approximating the temporal betweenness centrality of all nodes in a temporal graph. Our method can compute probabilistically guaranteed high-quality temporal betweenness estimates (of nodes and temporal edges) under all the feasible temporal path optimalities, presented in the work of Bu{\ss} et al. (KDD, 2020). We provide a sample-complexity analysis of our method and speed up the temporal betweenness computation using a state-of-the-art progressive sampling approach based on Monte Carlo Empirical Rademacher Averages. Additionally, we provide an efficient sampling algorithm to approximate the temporal diameter, average path length, and other fundamental temporal graph characteristic quantities within a small error ε with high probability. The running time of such approximation algorithm is 𝒪̃(logn/ε²·|ℰ|), where n is the number of nodes and |ℰ| is the number of temporal edges in the temporal graph. We support our theoretical results with an extensive experimental analysis on several real-world networks and provide empirical evidence that the MANTRA framework improves the current state of the art in speed, sample size, and required space while maintaining high accuracy of the temporal betweenness estimates.
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