Random walks on complex trees

被引:54
作者
Baronchelli, Andrea [1 ]
Catanzaro, Michele [1 ]
Pastor-Satorras, Romualdo [1 ]
机构
[1] Univ Politecn Cataluna, Dept Fis & Engn Nucl, Barcelona 08034, Spain
关键词
D O I
10.1103/PhysRevE.78.011114
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
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.
引用
收藏
页数:9
相关论文
共 44 条
[31]  
LOVSZ L, 1996, COMBINATORICS PAUL E, P353
[32]   Spread of two linked social norms on complex interaction networks [J].
Nakamaru, M ;
Levin, SA .
JOURNAL OF THEORETICAL BIOLOGY, 2004, 230 (01) :57-64
[33]  
Newman MEJ, 2003, HANDBOOK OF GRAPHS AND NETWORKS: FROM THE GENOME TO THE INTERNET, P35
[34]  
Noh JD, 2006, J KOREAN PHYS SOC, V48, pS202
[35]   Random walks on complex networks [J].
Noh, JD ;
Rieger, H .
PHYSICAL REVIEW LETTERS, 2004, 92 (11) :118701-1
[36]   Dynamical and correlation properties of the Internet -: art. no. 258701 [J].
Pastor-Satorras, R ;
Vázquez, A ;
Vespignani, A .
PHYSICAL REVIEW LETTERS, 2001, 87 (25) :258701-1
[37]  
Redner S., 2001, A Guide to First-Passage Processes
[38]   Laplacian spectra of, and random walks on, complex networks: Are scale-free architectures really important? [J].
Samukhin, A. N. ;
Dorogovtsev, S. N. ;
Mendes, J. F. F. .
PHYSICAL REVIEW E, 2008, 77 (03)
[39]   HIERARCHICAL-MODELS FOR AGING AND RELAXATION OF SPIN-GLASSES [J].
SIBANI, P ;
HOFFMANN, KH .
PHYSICAL REVIEW LETTERS, 1989, 63 (26) :2853-2856
[40]   Origins of fractality in the growth of complex networks [J].
Song, CM ;
Havlin, S ;
Makse, HA .
NATURE PHYSICS, 2006, 2 (04) :275-281