Random walks in weighted networks with a perfect trap: An application of Laplacian spectra

Abstract

In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.

Definitive version accepted for publication in Physical Review E

References in corpus (24)

• The scaling laws of human travel
• Universality in the synchronization of weighted random networks
• Entropy Rate of Diffusion Processes on Complex Networks
• Exact mean first-passage time on the T-graph
• Maximal-entropy random walks in complex networks with limited information
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Random walks on weighted networks
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• 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
• Laplacian spectra of recursive treelike small-world polymer networks: Analytical solutions and applications
• Evolution of optimal Lévy-flight strategies in human mental searches
• Condensation in a zero range process on weighted scale-free networks
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Mean first-passage time for random walks on the T-graph
• Transport on weighted Networks: when correlations are independent of degree
• Mean first-passage time for random walks in general graphs with a deep trap
• Trapping of Continuous-Time Quantum walks on Erdos-Renyi graphs
• Origin of the hub spectral dimension in scale-free networks
• Understanding the complexity of the Lévy-walk nature of human mobility with a multi-scale cost/benefit model

Cited by in corpus (21)

• Random walks and diffusion on networks
• Characteristic times of biased random walks on complex networks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Efficient exploration of multiplex networks
• Mean first-passage time for maximal-entropy random walks in complex networks
• Heterogeneous continuous time random walks
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Random walks on complex networks under node-dependent stochastic resetting
• Random walks on complex networks under time-dependent stochastic resetting
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Effects of reciprocity on random walks in weighted networks
• The normalized Laplacian spectrum of $n$-polygon graphs and its applications
• Higher-order models capture changes in controllability of temporal networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• 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
• Extended corona product as an exactly tractable model for weighted heterogeneous networks
• Navigation by anomalous random walks on complex networks
• Non-Backtracking Centrality Based Random Walk on Networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula