# Random Walks: A Review of Algorithms and Applications

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2020.

## Built on by (most cited first, 30 of 38)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2410.13080/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [When to Pre-Train Graph Neural Networks? From Data Generation Perspective!](https://mlsanity.com/paper/2303.16458/) (2023)
- [Graph Learning for Anomaly Analytics: Algorithms, Applications, and Challenges](https://mlsanity.com/paper/2212.05532/) (2022)
- [CenGCN: Centralized Convolutional Networks with Vertex Imbalance for Scale-Free Graphs](https://mlsanity.com/paper/2202.07826/) (2022)
- [Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks](https://mlsanity.com/paper/2311.01038/) (2023)
- [Long-range Brain Graph Transformer](https://mlsanity.com/paper/2501.01100/) (2025)
- [ArchGym: An Open-Source Gymnasium for Machine Learning Assisted Architecture Design](https://mlsanity.com/paper/2306.08888/) (2023)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [CloudWalker: Random walks for 3D point cloud shape analysis](https://mlsanity.com/paper/2112.01050/) (2021)
- [Machine Learning on Dynamic Graphs: A Survey on Applications](https://mlsanity.com/paper/2401.08147/) (2024)
- [Network Representation Learning: From Traditional Feature Learning to Deep Learning](https://mlsanity.com/paper/2103.04339/) (2021)
- [Heterogeneous Graph Learning for Explainable Recommendation over Academic Networks](https://mlsanity.com/paper/2202.07832/) (2022)
- [Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs](https://mlsanity.com/paper/2406.03097/) (2024)
- [Fully Autonomous Programming using Iterative Multi-Agent Debugging with Large Language Models](https://mlsanity.com/paper/2503.07693/) (2025)
- [Graph Tokenization for Bridging Graphs and Transformers](https://mlsanity.com/paper/2603.11099/) (2026)
- [A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks](https://mlsanity.com/paper/2105.09494/) (2021)
- [Physics-Informed Graph Learning](https://mlsanity.com/paper/2202.10679/) (2022)
- [Multi-omics Sampling-based Graph Transformer for Synthetic Lethality Prediction](https://mlsanity.com/paper/2310.11082/) (2023)
- [REAL: A Reasoning-Enhanced Graph Framework for Long-Term Memory Management of LLMs](https://mlsanity.com/paper/2606.10694/) (2026)
- [VRConvMF: Visual Recurrent Convolutional Matrix Factorization for Movie Recommendation](https://mlsanity.com/paper/2202.10241/) (2022)
- [Keyword Decisions in Sponsored Search Advertising: A Literature Review and Research Agenda](https://mlsanity.com/paper/2302.12372/) (2023)
- [Disease Gene Prioritization With Quantum Walks](https://mlsanity.com/paper/2311.05486/) (2023)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [ClusterRCA: An End-to-End Approach for Network Fault Localization and Classification for HPC System](https://mlsanity.com/paper/2506.20673/) (2025)
- [Deep Learning for Crack Detection: A Review of Learning Paradigms, Generalizability, and Datasets](https://mlsanity.com/paper/2508.10256/) (2025)
- [Performance Evaluation, Optimization and Dynamic Decision in Blockchain Systems: A Recent Overview](https://mlsanity.com/paper/2211.15907/) (2022)
- [Random Feedback Alignment Algorithms to train Neural Networks: Why do they Align?](https://mlsanity.com/paper/2306.02325/) (2023)
- [Social Recommendation through Heterogeneous Graph Modeling of the Long-term and Short-term Preference Defined by Dynamic Time Spans](https://mlsanity.com/paper/2312.14306/) (2023)

## Abstract (arXiv)

A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this paper, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.