Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
arXiv:1307.0903 · doi:10.1103/PhysRevE.87.062140
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.
arXiv commentDefinitive version accepted for publication in Physical Review E
References in corpus (52)
- Emergence of scaling in random networks
- The architecture of complex weighted networks
- The scaling laws of human travel
- Dynamical and correlation properties of the Internet
- Weighted evolving networks: coupling topology and weights dynamics
- Universality in the synchronization of weighted random networks
- Random walks on graphs: ideas, techniques and results
- Entropy Rate of Diffusion Processes on Complex Networks
- Localization of maximal entropy random walk
- 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
- 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
- Random Walks on deterministic Scale-Free networks: Exact results
- Flow graphs: interweaving dynamics and structure
- Epidemic Spreading in Weighted Networks: An Edge-Based Mean-Field Solution
- Exact calculations of first-passage quantities on recursive networks
- Mean-field diffusive dynamics on weighted 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
- Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
- 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
- Effective target arrangement in a deterministic scale-free graph
- Trapping in scale-free networks with hierarchical organization of modularity
- 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
- Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
- Transport on weighted Networks: when correlations are independent of degree
- Random walks in modular scale-free networks with multiple traps
- Rationality, irrationality and escalating behavior in lowest unique bid auctions
- Role of fractal dimension in random walks on scale-free networks
- Mean first-passage time for random walks in general graphs with a deep trap
- Walks on weighted networks
- Trapping of Continuous-Time Quantum walks on Erdos-Renyi graphs
- Supercooperation in Evolutionary Games on Correlated Weighted Networks
- Geometric origin of scaling in large traffic networks
- Complete spectrum of stochastic master equation for random walks on treelike fractals
- Origin of the hub spectral dimension in scale-free networks
- Random walks in small-world exponential treelike networks
- Understanding the complexity of the Lévy-walk nature of human mobility with a multi-scale cost/benefit model
- Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
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 -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