Random walk centrality for temporal networks
arXiv:1401.5648 · doi:10.1088/1367-2630/16/6/063023
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.
arXiv commentmain text + supplementary material
References in corpus (25)
- Maps of random walks on complex networks reveal community structure
- Temporal Networks
- Search in Power-Law Networks
- What's in a crowd? Analysis of face-to-face behavioral networks
- Optimal network topologies for local search with congestion
- 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
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian 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 networks: slowing down diffusion by long lasting interactions
- Quantifying the effect of temporal resolution on time-varying networks
- Temporal Heterogeneities Increase the Prevalence of Epidemics on Evolving Networks
- Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks
- Bursty communication patterns facilitate spreading in a threshold-based epidemic dynamics
- Generalized Master Equations for Non-Poisson Dynamics on Networks
- Evolutionary dynamics and fixation probabilities in directed networks
- Epidemiologically optimal static networks from temporal network data
- A network-based dynamical ranking system for competitive sports
- Random Walks on Stochastic Temporal Networks
- Mutually-Antagonistic Interactions in Baseball Networks
- Flow Motifs Reveal Limitations of the Static Framework to Represent Human interactions
- 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