Trapping in complex networks

Abstract

We investigate the trapping problem in Erdos-Renyi (ER) and Scale-Free (SF) networks. We calculate the evolution of the particle density $\rho (t)$ of random walkers in the presence of one or multiple traps with concentration $c$. We show using theory and simulations that in ER networks, while for short times $\rho (t)\propto \exp (-Act)$, for longer times $\rho (t)$ exhibits a more complex behavior, with explicit dependence on both the number of traps and the size of the network. In SF networks we reveal the significant impact of the trap's location: $\rho (t)$ is drastically different when a trap is placed on a random node compared to the case of the trap being on the node with the maximum connectivity. For the latter case we find $ρ(t)\propto\exp\left[-At/N^\frac{γ-2}{γ-1}\av{k}\right]$ for all $\gamma >2$, where $\gamma$ is the exponent of the degree distribution $P(k)\propto k^{-\gamma }$.

Appendix added

References in corpus (13)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The diameter of the world wide web
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• First Passage Properties of the Erdos-Renyi Random Graph
• Anomalous Transport in Complex Networks
• Absence of kinetic effects in reaction-diffusion processes in scale-free networks
• Random walk and trapping processes on scale-free networks
• Ring structures and mean first passage time in networks
• Anomalous Size Dependence of Relaxational Processes
• Numerical evaluation of the upper critical dimension of percolation in scale-free networks
• On the Tomography of Networks and Multicast Trees

Cited by in corpus (37)

• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• Random walks on weighted networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Random Walks on deterministic Scale-Free networks: Exact results
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Mean first-passage time for random walks on undirected networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Random walks on the Apollonian network with a single trap
• Trapping in dendrimers and regular hyperbranched polymers
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Trapping in scale-free networks with hierarchical organization of modularity
• Mean first-passage time for random walks on the T-graph
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Mean first-passage time for maximal-entropy random walks in complex networks
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• 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
• Anomalous behavior of trapping on a fractal scale-free network
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Controlling the efficiency of trapping in treelike fractals
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Anomalous biased diffusion in networks
• Exact eigenvalue spectrum of a class of fractal scale-free networks
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• Inter-arrival times of message propagation on directed networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Unexpected advantages of exploitation for target searches in complex networks
• Intransitiveness in the Penney Game and in Random Walks on rings, networks, communities and cities
• Efficiency of message transmission using biased random walks in complex networks in the presence of traps
• Optimal search strategies on complex networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Trapping problem on star-type graphs with applications