Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices

Abstract

The family of Vicsek fractals is one of the most important and frequently-studied regular fractal classes, and it is of considerable interest to understand the dynamical processes on this treelike fractal family. In this paper, we investigate discrete random walks on the Vicsek fractals, with the aim to obtain the exact solutions to the global mean first-passage time (GMFPT), defined as the average of first-passage time (FPT) between two nodes over the whole family of fractals. Based on the known connections between FPTs, effective resistance, and the eigenvalues of graph Laplacian, we determine implicitly the GMFPT of the Vicsek fractals, which is corroborated by numerical results. The obtained closed-form solution shows that the GMFPT approximately grows as a power-law function with system size (number of all nodes), with the exponent lies between 1 and 2. We then provide both the upper bound and lower bound for GMFPT of general trees, and show that leading behavior of the upper bound is the square of system size and the dominating scaling of the lower bound varies linearly with system size. We also show that the upper bound can be achieved in linear chains and the lower bound can be reached in star graphs. This study provides a comprehensive understanding of random walks on the Vicsek fractals and general treelike networks.

Definitive version accepted for publication in Physical Review E

References in corpus (17)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Global mean first-passage times of random walks on complex networks
• Exact mean first-passage time on the T-graph
• 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 deterministic Scale-Free networks: Exact results
• Random walks on complex trees
• Exact solution of mean geodesic distance for Vicsek fractals
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Random walks on the Apollonian network with a single trap
• 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
• Mean first-passage time for random walks on the T-graph
• A geometric growth model interpolating between regular and small-world networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random Walks on Complex Networks

Cited by in corpus (22)

• Random walks and diffusion on networks
• Determining mean first-passage time on a class of treelike regular fractals
• Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications
• Trapping in dendrimers and regular hyperbranched polymers
• Laplacian spectra of recursive treelike small-world polymer networks: Analytical solutions and applications
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Random walks in modular scale-free networks with multiple traps
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• 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
• Extended Vicsek fractals: Laplacian spectra and their applications
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Random walks in small-world exponential treelike networks
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• Exact eigenvalue spectrum of a class of fractal scale-free networks
• Marginally compact fractal trees with semiflexibility
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• First-passage times to a fractal boundary: local persistence exponent and its log-periodic oscillations
• Consensus and Coherence in Fractal Networks
• Random walks on stochastic uniform growth trees: Analytical formula for mean first-passage time
• Exact mean first-passage time on generalized Vicsek fractal
• First passage times of transport on planar spatial networks and their connections to off-network planar diffusion