  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 $\varepsilon$ with high probability. The running time of such
approximation algorithm is $\tilde{\mathcal{O}}(\frac{\log
n}{\varepsilon^2}\cdot |\mathcal{E}|)$, where $n$ is the number of nodes and
$|\mathcal{E}|$ 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.
