Random walks with long-range steps generated by functions of Laplacian matrices

Abstract

In this paper, we explore different Markovian random walk strategies on networks with transition probabilities between nodes defined in terms of functions of the Laplacian matrix. We generalize random walk strategies with local information in the Laplacian matrix, that describes the connections of a network, to a dynamics determined by functions of this matrix. The resulting processes are non-local allowing transitions of the random walker from one node to nodes beyond its nearest neighbors. We find that only two types of Laplacian functions are admissible with distinct behaviors for long-range steps in the infinite network limit: type (i) functions generate Brownian motions, type (ii) functions Lévy flights. For this asymptotic long-range step behavior only the lowest non-vanishing order of the Laplacian function is relevant, namely first order for type (i), and fractional order for type (ii) functions. In the first part, we discuss spectral properties of the Laplacian matrix and a series of relations that are maintained by a particular type of functions that allow to define random walks on any type of undirected connected networks. Once described general properties, we explore characteristics of random walk strategies that emerge from particular cases with functions defined in terms of exponentials, logarithms and powers of the Laplacian as well as relations of these dynamics with non-local strategies like Lévy flights and fractional transport. Finally, we analyze the global capacity of these random walk strategies to explore networks like lattices and trees and different types of random and complex networks.

33 pages, 5 figures

References in corpus (15)

• Emergence of scaling in random networks
• Synchronization in complex networks
• Random walks and diffusion on networks
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Global mean first-passage times of random walks on complex networks
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Flow graphs: interweaving dynamics and structure
• Quantum evolution in the stroboscopic limit of repeated measurements
• Nonlocal constitutive laws generated by matrix functions: Lattice Dynamics Models and their Continuum Limits
• Hardy's nonlocality argument as witness for post-quantum correlation
• A fractional generalization of the classical lattice dynamics approach
• Burstiness and fractional diffusion on complex networks
• Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain
• Random Walks on Complex Networks

Cited by in corpus (12)

• Diffusive transport on networks with stochastic resetting to multiple nodes
• Nonlocal biased random walks and fractional transport on directed networks
• Mean encounter times for multiple random walkers on networks
• Aging in transport processes on networks with stochastic cumulative damage
• Biased continuous-time random walks with Mittag-Leffler jumps
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• Compatibility, embedding and regularization of non-local random walks on graphs
• Lifshitz tails for the fractional Anderson model
• Scoring Anomalous Vertices Through Quantum Walks
• Lifshitz tails for random diagonal perturbations of Laurent matrices
• Long-range connections and mixed diffusion in fractional networks
• Long-range connections, real-world networks and rates of diffusion