Random walks on the Apollonian network with a single trap

Abstract

Explicit determination of the mean first-passage time (MFPT) for trapping problem on complex media is a theoretical challenge. In this paper, we study random walks on the Apollonian network with a trap fixed at a given hub node (i.e. node with the highest degree), which are simultaneously scale-free and small-world. We obtain the precise analytic expression for the MFPT that is confirmed by direct numerical calculations. In the large system size limit, the MFPT approximately grows as a power-law function of the number of nodes, with the exponent much less than 1, which is significantly different from the scaling for some regular networks or fractals, such as regular lattices, Sierpinski fractals, T-graph, and complete graphs. The Apollonian network is the most efficient configuration for transport by diffusion among all previously studied structure.

Definitive version accepted for publication in EPL (Europhysics Letters)

References in corpus (24)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Optimal search strategies for hidden targets
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Probing microscopic origins of confined subdiffusion by first-passage observables
• Random walks on graphs: ideas, techniques and results
• Enhanced reaction kinetics in biological cells
• Self-similar disk packings as model spatial scale-free networks
• Exact mean first-passage time on the T-graph
• Finite-size scaling in complex networks
• First Passage Properties of the Erdos-Renyi Random Graph
• High Dimensional Apollonian Networks
• Random walks on complex trees
• Competitive cluster growth in complex networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Trapping in complex networks
• Exact analytical solution of average path length for Apollonian networks
• Different topologies for a herding model of opinion
• The spread of gossip in American schools
• Walks on Apollonian networks
• Analytical approach to directed sandpile models on the Apollonian network

Cited by in corpus (30)

• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• Random walks on weighted networks
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random Walks on deterministic Scale-Free networks: Exact results
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• 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
• 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
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• 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
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Deterministic weighted scale-free small-world networks
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Generalized open quantum walks on Apollonian networks
• Optimal synchronizability of bearings
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• Contact graphs of disk packings as a model of spatial planar networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Fast solver for diffusive transport times on dynamic intracellular networks