2008/01/31 by Andrea Baronchelli, Michele Catanzaro, Romualdo Pastor‐Satorras +1 · 3 citations
Mathematics · Physics and Astronomy · #Combinatorics #Complex Network Analysis Techniques #Degree (music) #First-hitting-time model #Geometry #Graph #Inverse #Logarithm #Mathematical analysis #Mathematics #Opinion Dynamics and Social Influence #Physics #Random walk #Statistical physics #Statistics #Theoretical and Computational Physics #Tree (set theory) #Vertex (graph theory) #cond-mat.dis-nn #cond-mat.stat-mech #math.PR
paper · pdf · doi:10.1103/physreve.78.011114
published as Phys. Rev. E 78, 011114 (2008) · 9 pages, 13 figures (extended version of previous "Random walks on scale-free trees")
arxiv created 2008/06/10 · openalex publication_date 2008/07/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the properties of random walks on complex trees. We observe that the absence of loops is reflected 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.