Exact solution for mean first-passage time on a pseudofractal scale-free web

Abstract

The explicit determinations of the mean first-passage time (MFPT) for trapping problem are limited to some simple structure, e.g., regular lattices and regular geometrical fractals, and determining MFPT for random walks on other media, especially complex real networks, is a theoretical challenge. In this paper, we investigate a simple random walk on the the pseudofractal scale-free web (PSFW) with a perfect trap located at a node with the highest degree, which simultaneously exhibits the remarkable scale-free and small-world properties observed in real networks. We obtain the exact solution for the MFPT that is calculated through the recurrence relations derived from the structure of PSFW. The rigorous solution exhibits that the MFPT approximately increases as a power-law function of the number of nodes, with the exponent less than 1. We confirm the closed-form solution by direct numerical calculations. We show that the structure of PSFW can improve the efficiency of transport by diffusion, compared with some other structure, such as regular lattices, Sierpinski fractals, and T-graph. The analytical method can be applied to other deterministic networks, making the accurate computation of MFPT possible.

6 pages, 1 figure; definitive version published in Physical Review E

References in corpus (29)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Synchronization in complex networks
• Evolution of networks
• Evolutionary games on graphs
• Critical phenomena in complex networks
• Hierarchical Organization in Complex Networks
• Self-similarity of complex networks
• First-passage times in complex scale-invariant media
• Pseudofractal Scale-free Web
• Deterministic Scale-Free Networks
• Optimal search strategies for hidden targets
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Probing microscopic origins of confined subdiffusion by first-passage observables
• Random walks on graphs: ideas, techniques and results
• Enhanced reaction kinetics in biological cells
• First-passage times for random walks in bounded domains
• Exact mean first-passage time on the T-graph
• Recursive graphs with small-world scale-free properties
• First Passage Properties of the Erdos-Renyi Random Graph
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Random spread on the family of small-world networks
• Random walks on complex trees
• A general geometric growth model for pseudofractal scale-free web
• Trapping in complex networks
• Evolving small-world scale-free networks consist of cliques

Cited by in corpus (57)

• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• First passage time for random walks in heterogeneous 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
• Enumeration of spanning trees in a pseudofractal scale-free web
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Trapping in dendrimers and regular hyperbranched polymers
• 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
• Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Mean first-passage time for maximal-entropy random walks in complex networks
• Heterogeneous continuous time random walks
• 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
• Random walks on complex networks with first-passage resetting
• Anomalous behavior of trapping on a fractal scale-free network
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Controlling the efficiency of trapping in treelike fractals
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Exact results for the first-passage properties in a class of fractal networks
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Thermodynamics of bosons systems related to Dunkl differential-difference operators
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Origin of the hub spectral dimension in scale-free networks
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• 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
• Exact encounter times for many random walkers on regular and complex networks
• Effects of reciprocity on random walks in weighted networks
• Stability and anyonic behavior of systems with M-statistics
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• Geometry of Quantum Group invariant systems
• Scalar curvature of systems with fractal distribution functions
• 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
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• Tutte polynomial of pseudofractal scale-free web
• Response to targeted perturbations for random walks on networks
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• The k-Power Domination Number in Some Self-Similar Graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket