Random walks and diffusion on networks

By Naoki Masuda, M. A. Porter, Renaud Lambiotte. arXiv.org, 2016

692 citations recorded by the source corpus.

Abstract Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/71e19982137412e433c0c6cd74ac7fe126dbcfd4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

COVID-19 lockdown induces disease-mitigating structural changes in mobility networks (2020, background): “therefore represents the average minimal mean first passage time between any nodes i and j in an edge-centered random walk on a network with of m nodes [43].”
What are higher-order networks? (2021, background): “We finally remark that can define a symmetric variant via the similarity transform W −1/2 n+1 LnW 1/2 n+1 [126, 148, 248], from which it is easy to see that the Hodge Laplacian Ln is positive semi-definite for any n. Based on the Hodge Laplacians, as defined in Equation (3.2), we can compute most in”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “[310] Naoki Masuda, Mason A Porter, and Renaud Lambiotte.”
The statistical physics of real-world networks (2018, background): “The resulting von Neuman entropy thus depends on the spectrum of the Laplacian, and can be seen as the result of constraining the properties of diffusion dynamics on the network [180, 181].”
Diffusion Improves Graph Learning (2019, neutral): “[46] and Fouss et al.”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, methodology): “This close relationship between Markov chains and graphs has led to a broad adoption of diffusion-based algorithms in network science [87], with applications to ranking connected objects [59], analyzing disease spreading [111], and respondentdriven sampling [112].”
Taskonomy: Disentangling Task Transfer Learning (2018, background): “The elements of the principal eigenvector are a measure of centrality, and are proportional to the amount of time that an infinite-length randomwalk on W ′ t will spend at any given source [59].”