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 (21)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Critical phenomena in complex networks
• Dynamical and correlation properties of the Internet
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Generation of uncorrelated random scale-free networks
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Cut-offs and finite size effects in scale-free networks
• Non-equilibrium dynamics of language games on complex networks
• Comparison of voter and Glauber ordering dynamics on networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Rate equation approach for correlations in growing network models
• Topology and correlations in structured scale-free networks
• Scaling Properties of Random Walks on Small-World Networks
• Universal scaling of distances in complex networks
• Random walk and trapping processes on scale-free networks
• Ring structures and mean first passage time in networks
• Degree-dependent intervertex separation in complex networks
• Diffusion in scale-free networks with annealed disorder
• Border trees of complex networks

Cited by in corpus (31)

• Random walks and diffusion on networks
• Random walks and search in time-varying networks
• Global mean first-passage times of random walks on complex networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Lévy flights in human behavior and cognition
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Mean-field diffusive dynamics on weighted networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Random walks on the Apollonian network with a single trap
• Networking - A Statistical Physics Perspective
• Scaling of human behavior during portal browsing
• Trapping in scale-free networks with hierarchical organization of modularity
• Degree Correlation in Scale-Free Graphs
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Slow dynamics and rare-region effects in the contact process on weighted tree networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Dynamic topologies of activity-driven temporal networks with memory
• Random walks in small-world exponential treelike networks
• Random walks on networks: cumulative distribution of cover time
• Complex networks and glassy dynamics: walks in the energy landscape
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Response to targeted perturbations for random walks on networks
• Scale-free tree network with an ultra-large diameter
• Detecting Structure of Complex Network by Quantum Bosonic Dynamics
• Slow dynamics of Zero Range Process in the Framework of Traps Model
• Random walks on stochastic uniform growth trees: Analytical formula for mean first-passage time
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Random walks on bifractal networks