Making Temporal Betweenness Computation Faster and Restless

Buß et al [KDD 2020] recently proved that the problem of computing the betweenness of all nodes of a temporal graph is computationally hard in the case of foremost and fastest paths, while it is solvable in time O(n^3T^2)$ in the case of shortest and shortest foremost paths, where $n$ is the number of nodes and $T$ is the number of distinct time steps. A new algorithm for temporal betweenness computation is introduced in this paper. In the case of shortest and shortest foremost paths, it requires $O(n + M)$ space and runs in time $O(nM)=O(n^3T)$, where $M$ is the number of temporal edges, thus significantly improving the algorithm of Buß et al. Experimental evidence is provided that our algorithm performs between twice and almost 300 times better than the algorithm of Buß et al. Moreover, we were able to compute the exact temporal betweenness values of several large temporal graphs with over a million of temporal edges. For such size, only approximate computation was possible by using the algorithm of Santoro and Sarpe [WWW 2022]. Maybe more importantly, our algorithm extends to the case of \textit{restless} walks (that is, walks with waiting constraints in each node), thus providing a polynomial-time algorithm (with complexity $O(nM)$) for computing the temporal betweenness in the case of several different optimality criteria. Such restless computation was known only for the shortest criterion (Rymar et al [JGAA 2023]). We performed an extensive experimental validation by comparing different waiting constraints and different optimisation criteria. Moreover, as a case study, we investigate six public transit networks including Berlin, Rome, and Paris. Overall we find a general consistency between the different variants of betweenness centrality. However, we do measure a sensible influence of waiting constraints, and note some cases of low correlation for certain pairs of criteria in some networks.

BRUNELLI Filippo;  CRESCENZI Pierluigi;  VIENNOT Laurent; 

2024-09-03

Association for Computing Machinery

JRC136892

9798400704901 (online),   

2154-817X (online),   

https://doi.org/10.1145/3637528.3671825,    https://publications.jrc.ec.europa.eu/repository/handle/JRC136892,   

10.1145/3637528.3671825 (online),