# Random walks and diffusion on networks

arXiv: https://arxiv.org/abs/1612.03281 · HTML: https://mlsanity.com/paper/1612.03281/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2016.

## Built on by (most cited first, 28 of 28)

- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs](https://mlsanity.com/paper/2203.16939/) (2022)
- [Residual2Vec: Debiasing graph embedding with random graphs](https://mlsanity.com/paper/2110.07654/) (2021)
- [Koopman-based spectral clustering of directed and time-evolving graphs](https://mlsanity.com/paper/2204.02951/) (2022)
- [mGNN: Generalizing the Graph Neural Networks to the Multilayer Case](https://mlsanity.com/paper/2109.10119/) (2021)
- [Structural Balance and Random Walks on Complex Networks with Complex Weights](https://mlsanity.com/paper/2307.01813/) (2023)
- [A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks](https://mlsanity.com/paper/2105.09494/) (2021)
- [The Brownian motion in the transformer model](https://mlsanity.com/paper/2107.05264/) (2021)
- [Multiscale methods for signal selection in single-cell data](https://mlsanity.com/paper/2206.07760/) (2022)
- [Link prediction with continuous-time classical and quantum walks](https://mlsanity.com/paper/2208.11030/) (2022)
- [A Diffusive Data Augmentation Framework for Reconstruction of Complex Network Evolutionary History](https://mlsanity.com/paper/2501.06485/) (2025)
- [Adaptive Local Clustering over Attributed Graphs](https://mlsanity.com/paper/2503.20488/) (2025)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation](https://mlsanity.com/paper/2603.05375/) (2026)
- [Synwalk -- Community Detection via Random Walk Modelling](https://mlsanity.com/paper/2101.08623/) (2021)
- [Thematic recommendations on knowledge graphs using multilayer networks](https://mlsanity.com/paper/2105.05733/) (2021)
- [An adaptation of InfoMap to absorbing random walks using absorption-scaled graphs](https://mlsanity.com/paper/2112.10953/) (2021)
- [Sampling for network function learning](https://mlsanity.com/paper/2209.07342/) (2022)
- [Graph sampling for node embedding](https://mlsanity.com/paper/2210.10520/) (2022)
- [Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Prior](https://mlsanity.com/paper/2210.15410/) (2022)
- [Strong and Weak Random Walks on Signed Networks](https://mlsanity.com/paper/2406.08034/) (2024)
- [Matrix-weighted networks for modeling multidimensional dynamics](https://mlsanity.com/paper/2410.05188/) (2024)
- [From ChebNet to ChebGibbsNet](https://mlsanity.com/paper/2412.01789/) (2024)
- [Network classification through random walks](https://mlsanity.com/paper/2505.21706/) (2025)
- [A Framework Based on Graph Cellular Automata for Similarity Evaluation in Urban Spatial Networks](https://mlsanity.com/paper/2511.00768/) (2025)
- [Inferring Network Evolutionary History via Structure-State Coupled Learning](https://mlsanity.com/paper/2601.02121/) (2026)
- [Adaptive Fidelity Estimation for Quantum Programs with Graph-Guided Noise Awareness](https://mlsanity.com/paper/2601.14713/) (2026)
- [Conditional Entropy of Heat Diffusion on Temporal Networks](https://mlsanity.com/paper/2605.21514/) (2026)

## Abstract (arXiv)

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.