Random walks on weighted networks

Abstract

Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using the spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT, which is defined as the average MFPT to a given node over every starting point chosen from the stationary distribution. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For the case of uncorrelated networks, we provide explicit formulas for the stationary distribution as well as ATT. Particularly, for uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending also on the same parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.

Definitive version accepted for publication in Physical Review E

References in corpus (16)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Universality in the synchronization of weighted random networks
• Exact mean first-passage time on the T-graph
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Determining mean first-passage time on a class of treelike regular fractals
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Trapping in dendrimers and regular hyperbranched polymers
• Voter models on weighted networks
• Condensation in a zero range process on weighted scale-free networks
• Mean first-passage time for random walks in general graphs with a deep trap
• Condensation phenomena of conserved-mass aggregation model on weighted complex networks