# Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2021.

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

- [ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks](https://mlsanity.com/paper/2203.00653/) (2022)

## Abstract (arXiv)

In static graphs, the betweenness centrality of a graph vertex measures how many times this vertex is part of a shortest path between any two graph vertices. Betweenness centrality is efficiently computable and it is a fundamental tool in network science. Continuing and extending previous work, we study the efficient computability of betweenness centrality in temporal graphs (graphs with fixed vertex set but time-varying arc sets). Unlike in the static case, there are numerous natural notions of being a "shortest" temporal path (walk). Depending on which notion is used, it was already observed that the problem is #P-hard in some cases while polynomial-time solvable in others. In this conceptual work, we contribute towards classifying what a "shortest path (walk) concept" has to fulfill in order to gain polynomial-time computability of temporal betweenness centrality.