Random Walks on deterministic Scale-Free networks: Exact results

Abstract

We study the random walk problem on a class of deterministic Scale-Free networks displaying a degree sequence for hubs scaling as a power law with an exponent $\gamma =\log 3/\log 2$. We find exact results concerning different first-passage phenomena and, in particular, we calculate the probability of first return to the main hub. These results allow to derive the exact analytic expression for the mean time to first reach the main hub, whose leading behavior is given by $\tau \sim V^{1-1/\gamma }$, where $V$ denotes the size of the structure, and the mean is over a set of starting points distributed uniformly over all the other sites of the graph. Interestingly, the process turns out to be particularly efficient. We also discuss the thermodynamic limit of the structure and some local topological properties.

7 pages, 3 figures; accepted for publication in Phys. Rev. E

References in corpus (7)

• First-passage times in complex scale-invariant media
• Exact mean first-passage time on the T-graph
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Characteristics of reaction-diffusion on scale-free networks

Cited by in corpus (49)

• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• First passage time for random walks in heterogeneous networks
• Random walks on weighted networks
• Characteristic times of biased random walks on complex networks
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Exact calculations of first-passage quantities on recursive networks
• Facilitated diffusion of proteins on chromatin
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Mean first-passage time for random walks on undirected networks
• Trapping in dendrimers and regular hyperbranched polymers
• Effective target arrangement in a deterministic scale-free graph
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Trapping in scale-free networks with hierarchical organization of modularity
• Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Average distance in a hierarchical scale-free network: an exact solution
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Mean first-passage time for maximal-entropy random walks in complex networks
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Role of fractal dimension in random walks on scale-free networks
• Mean first-passage time for random walks in general graphs with a deep trap
• Scaling laws for diffusion on (trans)fractal scale-free networks
• 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
• Controlling the efficiency of trapping in treelike fractals
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Origin of the hub spectral dimension in scale-free networks
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• Effects of reciprocity on random walks in weighted networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• An alternative approach to determining average distance in a class of scale-free modular networks
• Limit theorems for Lévy walks in $d$ dimensions: rare and bulk fluctuations
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Response to targeted perturbations for random walks on networks
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Structural and temporal heterogeneities on networks
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Optimal search strategies on complex networks
• Trapping problem on star-type graphs with applications