Random walks with long-range steps generated by functions of Laplacian matrices
From MaRDI portal
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'evy 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'evy 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.
Recommendations
- Recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
- Random walks on weighted networks: a survey of local and non-local dynamics
- Fractional random walk lattice dynamics
- Non-local network dynamics via fractional graph Laplacians
- Random walks and flights over connected graphs and complex networks
Cites work
- A fractional generalization of the classical lattice dynamics approach
- Collective dynamics of `small-world' networks
- Completely monotone functions: a digest
- Completely monotonic functions
- Dynamical Processes on Complex Networks
- Emergence of Scaling in Random Networks
- Fractional diffusion on circulant networks: emergence of a dynamical small world
- Fractional random walk lattice dynamics
- Graph spectra for complex networks
- Graph Wavelets for Multiscale Community Mining
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 438987 (Why is no real title available?)
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 841532 (Why is no real title available?)
- scientific article; zbMATH DE number 878897 (Why is no real title available?)
- scientific article; zbMATH DE number 897154 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems
- Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain
- Navigation in spatial networks: a survey
- Networks. An introduction.
- Nonlocal constitutive laws generated by matrix functions: lattice dynamics models and their continuum limits
- On functions which preserve the class of Stieltjes matrices
- Random walk: A modern introduction
- Random walks and diffusion on networks
- Random walks and diffusions on graphs and databases. An introduction.
- Random walks on lattices. II
- Recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
- Stochastic processes in physics and chemistry.
Cited in
(11)- Lifshitz tails for random diagonal perturbations of Laurent matrices
- Lifshitz tails for the fractional Anderson model
- Compatibility, embedding and regularization of non-local random walks on graphs
- Long-range connections and mixed diffusion in fractional networks
- From the long jump random walk to the fractional Laplacian
- Recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
- Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
- Long-range connections, real-world networks and rates of diffusion
- What is a proper graph Laplacian? An operator-theoretic framework for graph diffusion
- Scoring anomalous vertices through quantum walks
- Random walks and flights over connected graphs and complex networks
This page was built for publication: Random walks with long-range steps generated by functions of Laplacian matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4964566)
