Random Walks: A Review of Algorithms and Applications
arXiv:2008.03639 · doi:10.1109/TETCI.2019.2952908
Abstract
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.
arXiv comment13 pages, 4 figures
References in corpus (23)
- Efficient Estimation of Word Representations in Vector Space
- DeepWalk: Online Learning of Social Representations
- Link Prediction in Complex Networks: A Survey
- Quantum Amplitude Amplification and Estimation
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- Exponential algorithmic speedup by quantum walk
- Link Prediction Based on Local Random Walk
- Simulating dynamic quantum phase transitions in photonic quantum walks
- The quantum to classical transition for random walks
- Connecting the discrete and continuous-time quantum walks
- Google in a Quantum Network
- Scientific Article Recommendation: Exploiting Common Author Relations and Historical Preferences
- Quantum Google in a Complex Network
- Deterministic realization of collective measurements via photonic quantum walks
- Knowledge Acquisition: A Complex Networks Approach
- Comparing the writing style of real and artificial papers
- Concentric network symmetry grasps authors' styles in word adjacency networks
- A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
- Hitting and commute times in large graphs are often misleading
- Quantum walks: Schur functions meet symmetry protected topological phases
Cited by in corpus (32)
- Graph Learning: A Survey
- Data-driven Computational Social Science: A Survey
- Attention Is Not the Only Choice: Counterfactual Reasoning for Path-Based Explainable Recommendation
- CenGCN: Centralized Convolutional Networks with Vertex Imbalance for Scale-Free Graphs
- Quantum walks with sequential aperiodic jumps
- Keyword Decisions in Sponsored Search Advertising: A Literature Review and Research Agenda
- Analysis of node2vec random walks on networks
- Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
- Quantum Financial Modeling on Noisy Intermediate-Scale Quantum Hardware: Random Walks using Approximate Quantum Counting
- Continuous-time quantum walks for MAX-CUT are hot
- CloudWalker: Random walks for 3D point cloud shape analysis
- Artificial Potential Field-Based Path Planning for Cluttered Environments
- Matching Algorithms: Fundamentals, Applications and Challenges
- Fully Autonomous Programming using Iterative Multi-Agent Debugging with Large Language Models
- Discrete-time quantum walk dispersion control through long-range correlations
- Coined quantum walks on the line: Disorder, entanglement, and localization
- Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks
- A simple coin for a entangled walk
- Non-Markovianity in Discrete-Time Open Quantum Random Walk on Arbitrary Graphs
- Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs
- Decoherence and classicalization of continuous-time quantum walks on graphs
- Quantum Algorithm for Testing Graph Completeness
- Classical and Quantum Random Walks to Identify Leaders in Criminal Networks
- Finite-size scaling properties of classical random walk on various two-dimensional lattices
- Directionality and quantum backfire in continuous-time quantum walks from delocalized states: Exact results
- Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise
- A study of the Antlion Random Walk
- Universality and classification of elementary thermal operations
- A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
- Response to glassy disorder in coin on spread of quantum walker
- Network Representation Learning: From Traditional Feature Learning to Deep Learning
- Revisiting quantum walk advantages: A mean hitting time perspective