  The betweenness centrality of a graph vertex measures how often this vertex
is visited on shortest paths between other vertices of the graph. In the
analysis of many real-world graphs or networks, betweenness centrality of a
vertex is used as an indicator for its relative importance in the network. In
particular, it is among the most popular tools in social network analysis. In
recent years, a growing number of real-world networks is modeled as temporal
graphs, where we have a fixed set of vertices and there is a finite discrete
set of time steps and every edge might be present only at some time steps.
While shortest paths are straightforward to define in static graphs, temporal
paths can be considered "optimal" with respect to many different criteria,
including length, arrival time, and overall travel time (shortest, foremost,
and fastest paths). This leads to different concepts of temporal betweenness
centrality and we provide a systematic study of temporal betweenness variants
based on various concepts of optimal temporal paths. Computing the betweenness
centrality for vertices in a graph is closely related to counting the number of
optimal paths between vertex pairs. We show that counting foremost and fastest
paths is computationally intractable (#P-hard) and hence the computation of the
corresponding temporal betweenness values is intractable as well. For shortest
paths and two selected special cases of foremost paths, we devise
polynomial-time algorithms for temporal betweenness computation. Moreover, we
also explore the distinction between strict (ascending time labels) and
non-strict (non-descending time labels) time labels in temporal paths. In our
experiments with established real-world temporal networks, we demonstrate the
practical effectiveness of our algorithms, compare the various betweenness
concepts, and derive recommendations on their practical use.
