On approximating the temporal betweenness centrality through sampling

04/17/2023

∙

by   Antonio Cruciani, et al.

∙

0

∙

share

We present a collection of sampling-based algorithms for approximating the temporal betweenness centrality of all nodes in a temporal graph. Our methods 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ß et al. (KDD, 2020). We provide a sample-complexity analysis of these methods and we speed up the temporal betweenness computation using progressive sampling techniques. Finally, we conduct an extensive experimental evaluation on real-world networks and we compare their performances in approximating the betweenness scores and rankings.