Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees

Abstract

The determination of mean first-passage time (MFPT) for random walks in networks is a theoretical challenge, and is a topic of considerable recent interest within the physics community. In this paper, according to the known connections between MFPT, effective resistance, and the eigenvalues of graph Laplacian, we first study analytically the MFPT between all node pairs of a class of growing treelike networks, which we term deterministic uniform recursive trees (DURTs), since one of its particular cases is a deterministic version of the famous uniform recursive tree. The interesting quantity is determined exactly through the recursive relation of the Laplacian spectra obtained from the special construction of DURTs. The analytical result shows that the MFPT between all couples of nodes in DURTs varies as $N\ln N$ for large networks with node number $N$. Second, we study trapping on a particular network of DURTs, focusing on a special case with the immobile trap positioned at a node having largest degree. We determine exactly the average trapping time (ATT) that is defined as the average of FPT from all nodes to the trap. In contrast to the scaling of the MFPT, the leading behavior of ATT is a linear function of $N$. Interestingly, we show that the behavior for ATT of the trapping problem is related to the trapping location, which is in comparison with the phenomenon of trapping on fractal T-graph although both networks exhibit treestructure. Finally, we believe that the methods could open the way to exactly calculate the MFPT and ATT in a wide range of deterministic media.

8 pages, 6 figures, definitive version published in Physical Review E

References in corpus (23)

• Critical phenomena in complex networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• First-passage times in complex scale-invariant media
• Scaling theory of transport in complex networks
• Exact mean first-passage time on the T-graph
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random walks on complex trees
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Trapping in scale-free networks with hierarchical organization of modularity
• Mean first-passage time for random walks on the T-graph
• Anomalous behavior of trapping on a fractal scale-free network
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Transition from small to large world in growing networks
• Border trees of complex networks
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• Degree and component size distributions in generalized uniform recursive tree
• Random Walks on Complex Networks

Cited by in corpus (19)

• Random walks and diffusion on networks
• 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
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• 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
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Exact results for the first-passage properties in a class of fractal networks
• 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
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• An alternative approach to determining average distance in a class of scale-free modular networks
• 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
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Scale-free tree network with an ultra-large diameter
• Heterogeneous Mean First-Passage Time Scaling in Fractal Media
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula