TY - JOUR

T1 - Random walk centrality for temporal networks

AU - Correa da Rocha, Luis Enrique

AU - Masuda, Naoki

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Nodes can be ranked according to their relative importance within a 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, 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 under periodic boundary conditions that we call TempoRank. It is known that, in static networks, the stationary density of the random walk is proportional to the degree or the strength of a node. In contrast, we find that, in temporal networks, the stationary density is proportional to the in-strength of the so-called effective network, a weighted and directed network explicitly constructed from the original sequence of transition matrices. The stationary density also depends on the sojourn probability q, which regulates the tendency of the walker to stay in the node, and on the temporal resolution of the data. 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 (one of the principles of the PageRank) at the right moment, this effect is negligible in practice when the time order of link activation is included.

AB - Nodes can be ranked according to their relative importance within a 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, 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 under periodic boundary conditions that we call TempoRank. It is known that, in static networks, the stationary density of the random walk is proportional to the degree or the strength of a node. In contrast, we find that, in temporal networks, the stationary density is proportional to the in-strength of the so-called effective network, a weighted and directed network explicitly constructed from the original sequence of transition matrices. The stationary density also depends on the sojourn probability q, which regulates the tendency of the walker to stay in the node, and on the temporal resolution of the data. 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 (one of the principles of the PageRank) at the right moment, this effect is negligible in practice when the time order of link activation is included.

KW - network analysis

KW - network centrality

KW - random walks

KW - stationary state

KW - temporal networks

KW - TempoRank

UR - http://www.scopus.com/inward/record.url?scp=84903647897&partnerID=8YFLogxK

U2 - 10.1088/1367-2630/16/6/063023

DO - 10.1088/1367-2630/16/6/063023

M3 - Article

AN - SCOPUS:84903647897

VL - 16

JO - New Journal of Physics

JF - New Journal of Physics

SN - 1367-2630

M1 - 063023

ER -