# ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks

arXiv: https://arxiv.org/abs/2203.00653 · HTML: https://mlsanity.com/paper/2203.00653/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 37 references that are in the map.
- First posted on arXiv 1 Mar 2022.

## Builds on (most cited first, 7 of 7)

- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages](https://mlsanity.com/paper/1602.05866/) (2016)
- [Recent Advances in Fully Dynamic Graph Algorithms](https://mlsanity.com/paper/2102.11169/) (2021)
- [Algorithmic Aspects of Temporal Betweenness](https://mlsanity.com/paper/2006.08668/) (2020)
- [SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds](https://mlsanity.com/paper/2106.03462/) (2021)
- [Fundamental Structures in Dynamic Communication Networks](https://mlsanity.com/paper/1907.09966/) (2019)
- [Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality](https://mlsanity.com/paper/2105.13055/) (2021)

## Built on by (most cited first, 3 of 3)

- [Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs](https://mlsanity.com/paper/2310.15865/) (2023)
- [CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs](https://mlsanity.com/paper/2506.14122/) (2025)
- [Inferring Network Evolutionary History via Structure-State Coupled Learning](https://mlsanity.com/paper/2601.02121/) (2026)

## Abstract (arXiv)

In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis of modern networks, enabling the identification of the most central nodes in such networks. Additionally to being massive, modern networks also contain information about the time at which their events occur. Such networks are often called temporal networks. The temporal information makes the study of the betweenness centrality in temporal networks (i.e., temporal betweenness centrality) much more challenging than in static networks (i.e., networks without temporal information). Moreover, the exact computation of the temporal betweenness centrality is often impractical on even moderately-sized networks, given its extremely high computational cost. A natural approach to reduce such computational cost is to obtain high-quality estimates of the exact values of the temporal betweenness centrality. In this work we present ONBRA, the first sampling-based approximation algorithm for estimating the temporal betweenness centrality values of the nodes in a temporal network, providing rigorous probabilistic guarantees on the quality of its output. ONBRA is able to compute the estimates of the temporal betweenness centrality values under two different optimality criteria for the shortest paths of the temporal network. In addition, ONBRA outputs high-quality estimates with sharp theoretical guarantees leveraging on the empirical Bernstein bound, an advanced concentration inequality. Finally, our experimental evaluation shows that ONBRA significantly reduces the computational resources required by the exact computation of the temporal betweenness centrality on several real world networks, while reporting high-quality estimates with rigorous guarantees.