Random walk centrality for temporal networks

Abstract

Nodes can be ranked according to their relative importance within the network. Ranking algorithms based on random walks are particularly useful because they connect topological and diffusive properties of the network. Previous methods based on random walks, as for example the PageRank, have focused on static structures. However, several realistic networks are indeed dynamic, meaning that their structure changes in time. In this paper, we propose a centrality measure for temporal networks based on random walks which we call TempoRank. While in a static network, the stationary density of the random walk is proportional to the degree or the strength of a node, we find that in temporal networks, the stationary density is proportional to the in-strength of the so-called effective network. The stationary density also depends on the sojourn probability q which regulates the tendency of the walker to stay in the node. We apply our method to human interaction networks and show that although it is important for a node to be connected to another node with many random walkers at the right moment (one of the principles of the PageRank), this effect is negligible in practice when the time order of link activation is included.

main text + supplementary material

References in corpus (12)

• Maps of random walks on complex networks reveal community structure
• What's in a crowd? Analysis of face-to-face behavioral networks
• Centrality in Interconnected Multilayer Networks
• Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
• Path lengths, correlations, and centrality in temporal networks
• Information dynamics shape the networks of Internet-mediated prostitution
• Network reachability of real-world contact sequences
• Random walks and search in time-varying networks
• Temporal Heterogeneities Increase the Prevalence of Epidemics on Evolving Networks
• Evolutionary dynamics and fixation probabilities in directed networks
• A network-based dynamical ranking system for competitive sports
• Random Walks on Complex Networks

Cited by in corpus (19)

• Random walks and diffusion on networks
• Modern temporal network theory: A colloquium
• Ranking in evolving complex networks
• Stream Graphs and Link Streams for the Modeling of Interactions over Time
• Random walks on activity-driven networks with attractiveness
• Big Networks: A Survey
• Steady state and mean recurrence time for random walks on stochastic temporal networks
• Coverage centralities for temporal networks
• Epidemic spreading on time-varying multiplex networks
• Exploring Temporal Networks with Greedy Walks
• Burstiness and tie reinforcement in time varying social networks
• Navigating temporal networks
• The spreading of computer viruses on time-varying networks
• Fixation probability in evolutionary dynamics on switching temporal networks
• A Parrondo paradox in susceptible-infectious-susceptible dynamics over periodic temporal networks
• Structural importance and evolution: an application to financial transaction networks
• A survey on modelling of infectious disease spread and control on social contact networks
• A Markov model for inferring flows in directed contact networks
• Diffusion on dynamic contact networks with indirect transmission links