ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in
  Temporal Networks
  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 \emph{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.
