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.

本文提出了 ONBRA 算法作为第一种基于抽样的近似算法，用来计算带有时间信息网络中节点的时间介数中心性，为减少计算代价带来质量保证。