On recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices

Abstract

We analyze a random walk strategy on undirected regular networks involving power matrix functions of the type $L^{\frac{\alpha }{2}}$ where $L$ indicates a `simple' Laplacian matrix. We refer such walks to as `Fractional Random Walks' with admissible interval $0<\alpha \le 2$. We deduce for the Fractional Random Walk probability generating functions (network Green's functions). From these analytical results we establish a generalization of Polya's recurrence theorem for Fractional Random Walks on $d$-dimensional infinite lattices: The Fractional Random Walk is transient for dimensions $d>\alpha$ (recurrent for $d\le \alpha$) of the lattice. As a consequence for $0<\alpha <1$ the Fractional Random Walk is transient for all lattice dimensions $d=1,2,..$ and in the range $1\le \alpha <2$ for dimensions $d\ge 2$. Finally, for $\alpha =2$ Polya's classical recurrence theorem is recovered, namely the walk is transient only for lattice dimensions $d\ge 3$. The generalization of Polya's recurrence theorem remains valid for the class of random walks with Lévy flight asymptotics for long-range steps. We also analyze for the Fractional Random Walk mean first passage probabilities, mean first passage times, and global mean first passage times (Kemeny constant). For the infinite 1D lattice (infinite ring) we obtain for the transient regime $0<\alpha <1$ closed form expressions for the fractional lattice Green's function matrix containing the escape and ever passage probabilities. The ever passage probabilities fulfill Riesz potential power law decay asymptotic behavior for nodes far from the departure node. The non-locality of the Fractional Random Walk is generated by the non-diagonality of the fractional Laplacian matrix with Lévy type heavy tailed inverse power law decay for the probability of long-range moves.

arXiv comment28 pages, 5 figures. HAL Id : hal-01543330, version 1

References in corpus (14)

• Statistical mechanics of complex networks
• Critical phenomena in complex networks
• Intermittent search strategies
• Lévy walks
• Validation of Dunbar's number in Twitter conversations
• Characterizing and modeling the dynamics of online popularity
• Fractional Laplacian in Bounded Domains
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Mean first-passage time for random walks on undirected networks
• A regularized representation of the fractional Laplacian in n dimensions and its relation to Weierstrass-Mandelbrot type fractal functions
• A fractional generalization of the classical lattice dynamics approach
• Mean number of visits to sites in Levy flights
• Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain

Cited by in corpus (8)

• Nonlocal biased random walks and fractional transport on directed networks
• Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction
• Continuous time random walk and diffusion with generalized fractional Poisson process
• On Discrete Time Prabhakar-Generalized Fractional Poisson Processes and Related Stochastic Dynamics
• Random walks with stochastic resetting in complex networks: a discrete time approach
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• Asymmetric random walks with bias generated by discrete-time counting processes
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics