Random walks on weighted networks: a survey of local and non-local dynamics
Authors:
Open Access
- 18 September 2021
- journal article
- review article
- Published by Oxford University Press (OUP) in Journal of Complex Networks
- Vol. 9 (5)
Abstract
In this article, we present a survey of different types of random walk models with local and non-local transitions on undirected weighted networks. We present a general approach by defining the dynamics as a discrete-time Markovian process with transition probabilities expressed in terms of a symmetric matrix of weights. In the first part, we describe the matrices of weights that define local random walk dynamics like the normal random walk, biased random walks and preferential navigation, random walks in the context of digital image processing and maximum entropy random walks. In addition, we explore non-local random walks, like Lévy flights on networks, fractional transport through the new formalism of fractional graph Laplacians, and applications in the context of human mobility. Explicit relations for the stationary probability distribution, the mean first passage time and global times to characterize random walks are obtained in terms of the elements of the matrix of weights and its respective eigenvalues and eigenvectors. Finally, we apply the results to the analysis of particular local and non-local random walk dynamics, and we discuss their capacity to explore several types of networks. Our results allow us to study and compare the global dynamics of different types of random walk models.Keywords
Funding Information
- Universidad Nacional Autónoma de México - Programa de Apoyo a Proyectos de Investigación e Innovación Tecnológica (IN116220)
This publication has 121 references indexed in Scilit:
- Urban characteristics attributable to density-driven tie formationNature Communications, 2013
- A Tale of Many Cities: Universal Patterns in Human Urban MobilityPLOS ONE, 2012
- Path Laplacian matrices: Introduction and application to the analysis of consensus in networksLinear Algebra and its Applications, 2012
- The physics of communicability in complex networksPhysics Reports, 2012
- Non-random walks in monkeys and humansJournal of The Royal Society Interface, 2011
- Spatial networksPhysics Reports, 2011
- Some features of the spread of epidemics and information on a random graphProceedings of the National Academy of Sciences, 2010
- Scale-free foraging by primates emerges from their interaction with a complex environmentProceedings Of The Royal Society B-Biological Sciences, 2006
- Introduction: 100years of Brownian motionChaos: An Interdisciplinary Journal of Nonlinear Science, 2005
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998