  We propose the Temporal Walk Centrality, which quantifies the importance of a
node by measuring its ability to obtain and distribute information in a
temporal network. In contrast to the widely-used betweenness centrality, we
assume that information does not necessarily spread on shortest paths but on
temporal random walks that satisfy the time constraints of the network. We show
that temporal walk centrality can identify nodes playing central roles in
dissemination processes that might not be detected by related betweenness
concepts and other common static and temporal centrality measures. We propose
exact and approximation algorithms with different running times depending on
the properties of the temporal network and parameters of our new centrality
measure. A technical contribution is a general approach to lift existing
algebraic methods for counting walks in static networks to temporal networks.
Our experiments on real-world temporal networks show the efficiency and
accuracy of our algorithms. Finally, we demonstrate that the rankings by
temporal walk centrality often differ significantly from those of other
state-of-the-art temporal centralities.
