Temporal Walk Centrality: Ranking Nodes in Evolving Networks
This addresses the need for more accurate centrality measures in temporal networks for applications like information dissemination, though it is incremental as it builds on existing walk-counting methods.
The paper tackles the problem of ranking node importance in evolving networks by proposing Temporal Walk Centrality, which measures a node's ability to obtain and distribute information via temporal random walks rather than shortest paths, and shows that it identifies central nodes missed by other methods with significant ranking differences in experiments.
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.