Random walks on complex trees

Abstract

We study the properties of random walks on complex trees. We observe that the absence of loops reflects in physical observables showing large differences with respect to their looped counterparts. First, both the vertex discovery rate and the mean topological displacement from the origin present a considerable slowing down in the tree case. Second, the mean first passage time (MFPT) displays a logarithmic degree dependence, in contrast to the inverse degree shape exhibited in looped networks. This deviation can be ascribed to the dominance of source-target topological distance in trees. To show this, we study the distance dependence of a symmetrized MFPT and derive its logarithmic profile, obtaining good agreement with simulation results. These unique properties shed light on the recently reported anomalies observed in diffusive dynamical systems on trees.

9 pages, 13 figures (extended version of previous "Random walks on scale-free trees")

References in corpus (6)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Non-equilibrium dynamics of language games on complex networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Ring structures and mean first passage time in networks
• Border trees of complex networks

Cited by in corpus (6)

• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random walks on the Apollonian network with a single trap
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random walks on networks: cumulative distribution of cover time
• Response to targeted perturbations for random walks on networks