Mean first-passage time for random walks on the T-graph

Abstract

For random walks on networks (graphs), it is a theoretical challenge to explicitly determine the mean first-passage time (MFPT) between two nodes averaged over all pairs. In this paper, we study the MFPT of random walks in the famous T-graph, linking this important quantity to the resistance distance in electronic networks. We obtain an exact formula for the MFPT that is confirmed by extensive numerical calculations. The interesting quantity is derived through the recurrence relations resulting from the self-similar structure of the T-graph. The obtained closed-form expression exhibits that the MFPT approximately increases as a power-law function of the number of nodes, with the exponent lying between 1 and 2. Our research may shed light on the deeper understanding of random walks on the T-graph.

Definitive version accepted for publication in New Journal of Physics

References in corpus (12)

• Statistical mechanics of complex networks
• Self-similarity of complex networks
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Random walks on graphs: ideas, techniques and results
• Exact mean first-passage time on the T-graph
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Exact solution of mean geodesic distance for Vicsek fractals
• Trapping in complex networks
• Fractal scale-free networks resistant to disease spread
• Transition from fractal to non-fractal scalings in growing scale-free networks

Cited by in corpus (18)

• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Determining mean first-passage time on a class of treelike regular fractals
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• 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
• Controlling the efficiency of trapping in treelike fractals
• 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
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Random walks in small-world exponential treelike networks
• Local orientational mobility in regular hyperbranched polymers
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• An alternative approach to determining average distance in a class of scale-free modular networks
• Mean first-passage time of quantum transition processes
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network