Random walks on complex networks.

By J. Noh, H. Rieger. Physical Review Letters, 2003

984 citations recorded by the source corpus.

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.

Subfields: Experimental and Cognitive Psychology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d043a37fb6d9f36d9bce84e967e21034941fda69

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Experimental and Cognitive Psychology

In Statistical and Nonlinear Physics

Citations in the corpus

Random walks and diffusion on networks (2016, methodology): “A third method to calculate the MFPT is to take advantage of relaxation properties of RWs [144].”
Mathematical Formulation of Multilayer Networks (2013, background): “Random walks on monoplex networks [2,72,74] have attracted considerable interest because they are both important and easy to interpret.”
Persistence and first-passage properties in nonequilibrium systems (2013, background): “od), transport limited chemical and biochemical reactions etc. The mean rst-passage time in a bounded domain (which can be any scale invariant medium such as a fractal [381] or even a complex network [383]) has been studied considerably in the recent past and a host of exact and approximate analytic”
A measure of betweenness centrality based on random walks (2003, background): “e power centrality of vertex i is the expected number of times such a walk passes through i, averaged over all possible starting points for the walk. The random-walk centrality introduced recently by Noh and Rieger (2003) is a measure of the speed with which randomly walking messages reach a vertex ”
Clustering attributed graphs: Models, measures and methods (2015, methodology): “Even without considering attributes, this has motivated the development of several methods, such as the well-known clique percolation method by Palla et al. (2005), or the ones by Nicosia et al.”
Graph based anomaly detection and description: a survey (2014, background): “The node-level features include (in/out) degrees, centrality measures such as eigenvector [Bonacich and Lloyd, 2001], closeness [Noh and Rieger, 2004], and betweenness [Freeman, 1977] centralities, local clustering coefficient [Watts and Strogatz, 1998], radius [Kang et al., 2011c], degree…”
Navigability of interconnected networks under random failures (2013, background): “Indeed, following the approach proposed in [5] for random walks on monoplexes, it is possible to show that the time required to a random walker starting from vertex i to arrive back to the same vertex, i.”