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 (38)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• The architecture of complex weighted networks
• Critical phenomena in complex networks
• Dynamical and correlation properties of the Internet
• First-passage times in complex scale-invariant media
• Weighted evolving networks: coupling topology and weights dynamics
• Universality in the synchronization of weighted random networks
• Random walks on graphs: ideas, techniques and results
• Global mean first-passage times of random walks on complex networks
• Biased random walks on complex networks: the role of local navigation rules
• First passage time for random walks in heterogeneous 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
• Random Walks on deterministic Scale-Free networks: Exact results
• Mean-field diffusive dynamics on weighted networks
• Exact calculations of first-passage quantities on recursive networks
• Determining mean first-passage time on a class of treelike regular fractals
• Mean first-passage time for random walks on undirected networks
• 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
• Asymptotic analysis of first passage time in complex networks
• Voter models on weighted networks
• Condensation in a zero range process on weighted scale-free networks
• Effective target arrangement in a deterministic scale-free graph
• Trapping in scale-free networks with hierarchical organization of modularity
• Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
• Random walks in modular scale-free networks with multiple traps
• Walks on weighted networks
• Mean first-passage time for random walks in general graphs with a deep trap
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Condensation phenomena of conserved-mass aggregation model on weighted complex networks
• Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence

Cited by in corpus (35)

• Random walks and diffusion on networks
• Characteristic times of biased random walks on complex networks
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Efficient exploration of multiplex networks
• Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications
• The normalized Laplacian spectrum of subdivisions of a graph
• Mean first-passage time for maximal-entropy random walks in complex networks
• Epidemic spreading driven by biased random walks
• Random walks on complex networks with first-passage resetting
• Levy random walks on multiplex networks
• Random walks on complex networks under node-dependent stochastic resetting
• Correlation Functions, Mean First Passage Times and the Kemeny Constant
• Random walks on complex networks under time-dependent stochastic resetting
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Mean encounter times for multiple random walkers on networks
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Aging in transport processes on networks with stochastic cumulative damage
• An ensemble of random graphs with identical degree distribution
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• On node ranking in graphs
• First-passage phenomena in hierarchical networks
• Compatibility, embedding and regularization of non-local random walks on graphs
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• Entropy rate of random walks on complex networks under stochastic resetting
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Effects of heterogeneity in site-site couplings for tight-binding models on scale-invariant structures
• Non-equilibrium random walks on multiplex networks
• Cross-frequency interactions during diffusion on complex brain networks are facilitated by scale-free properties
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Trapping problem on star-type graphs with applications
• Superdiffusion on complex networks: the role of shortcuts and long-range interactions
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• Non-Backtracking Centrality Based Random Walk on Networks