Determining mean first-passage time on a class of treelike regular fractals

Abstract

Relatively general techniques for computing mean first-passage time (MFPT) of random walks on networks with a specific property are very useful, since a universal method for calculating MFPT on general graphs is not available because of their complexity and diversity. In this paper, we present techniques for explicitly determining the partial mean first-passage time (PMFPT), i.e., the average of MFPTs to a given target averaged over all possible starting positions, and the entire mean first-passage time (EMFPT), which is the average of MFPTs over all pairs of nodes on regular treelike fractals. We describe the processes with a family of regular fractals with treelike structure. The proposed fractals include the $T$ fractal and the Peano basin fractal as their special cases. We provide a formula for MFPT between two directly connected nodes in general trees on the basis of which we derive an exact expression for PMFPT to the central node in the fractals. Moreover, we give a technique for calculating EMFPT, which is based on the relationship between characteristic polynomials of the fractals at different generations and avoids the computation of eigenvalues of the characteristic polynomials. Making use of the proposed methods, we obtain analytically the closed-form solutions to PMFPT and EMFPT on the fractals and show how they scale with the number of nodes. In addition, to exhibit the generality of our methods, we also apply them to the Vicsek fractals and the iterative scale-free fractal tree and recover the results previously obtained.

arXiv commentDefinitive version published in Physical Review E

References in corpus (14)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Random walks on graphs: ideas, techniques and results
• Global mean first-passage times of random walks on complex networks
• First-passage times for random walks in bounded domains
• Exact mean first-passage time on the T-graph
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• 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
• Anomalous behavior of trapping on a fractal scale-free network

Cited by in corpus (35)

• Random walks on weighted networks
• Characteristic times of biased random walks on complex networks
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Mean first-passage time for random walks on undirected networks
• Trapping in dendrimers and regular hyperbranched polymers
• Laplacian spectra of recursive treelike small-world polymer networks: Analytical solutions and applications
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• 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
• Mean first-passage time for random walks in general graphs with a deep trap
• The two-particle problem in comb-like structures
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Controlling the efficiency of trapping in treelike fractals
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Origin of the hub spectral dimension in scale-free networks
• Staggered and extreme localization of electron states in fractal space
• Extended Vicsek fractals: Laplacian spectra and their applications
• 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 in small-world exponential treelike networks
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Local orientational mobility in regular hyperbranched polymers
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• First-passage properties of mortal random walks: ballistic behavior, effective reduction of dimensionality, and scaling functions for hierarchical graphs
• Dynamics of "comb-of-comb" 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
• Topological regulation of activation barriers on fractal substrates
• 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
• First-passage times to a fractal boundary: local persistence exponent and its log-periodic oscillations
• Species survival and scaling laws in hostile and disordered environments
• A Method for Geodesic Distance on Subdivision of Trees with Arbitrary Orders and Their Applications
• More on the normalized Laplacian Estrada index
• Random walks on stochastic uniform growth trees: Analytical formula for mean first-passage time