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.

Definitive version published in Physical Review E

References in corpus (7)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Fractal and Transfractal Recursive Scale-Free Nets
• 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
• Mean first-passage time for random walks on the T-graph
• Anomalous behavior of trapping on a fractal scale-free network

Cited by in corpus (16)

• Random walks on weighted 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
• Staggered and extreme localization of electron states in fractal space
• Origin of the hub spectral dimension in scale-free networks
• Extended Vicsek fractals: Laplacian spectra and their applications
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Local orientational mobility in regular hyperbranched polymers
• First-passage properties of mortal random walks: ballistic behavior, effective reduction of dimensionality, and scaling functions for hierarchical graphs
• Topological regulation of activation barriers on fractal substrates
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• First-passage times to a fractal boundary: local persistence exponent and its log-periodic oscillations