Cited by 295Quantum Computing Algorithms and ArchitectureComplex Network Analysis TechniquesGraph Theory and Algorithms

Random Walks: A Review of Algorithms and Applications

Open access
Xia, Feng, Liu, Jiaying, Nie, Hansong, Fu, Yonghao, Wan, Liangtian, Kong, Xiangjie·2020·IEEE Transactions on Emerging Topics in Computational Intelligence

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 article, 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.

Integrity signals

Registry

Crossref · 10.1109/tetci.2019.2952908

Cites

85 of 85 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Deepfake leverages AI to manipulate or generate visual and audio content with a high potential to deceive.

    “Deepfake leverages the power of artificial intelligence (AI) (Liu etal. 2018; Xia etal. 2019) to manipulate or generate visual and audio content with a high potential to deceive (Kietzmann etal. 2020).”

    From Deepfake video detection: challenges and opportunities (2024) · cites this paper as Xia et al. 2019

Cites

Flagged first, then by citations

2 of the 87 references couldn’t be matched to a known paper.

Cited by

Sorted by citations

Authors
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X.
Affiliations
  • Federation University (AU)
  • Dalian University of Technology (CN)
Venue
IEEE Transactions on Emerging Topics in Computational Intelligence
Published
2020-04
Volume
4
Issue
2
Pages
95-107
ISSN
2471-285X (ISSN-L)
OpenAlex
W2990908872
Cited by
295
References
87
Citations by year
2026: 48 · 2025: 64 · 2024: 52 · 2023: 54 · 2022: 44 · 2021: 25 · 2020: 8
FWCI
8.88
Type
journal article
Language
en
Open access
Locations
  • IEEE Transactions on Emerging Topics in Computational Intelligence (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • FedUni ResearchOnline (Federation University Australia) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Natural Science Foundation of China (61872054)
  • Fundamental Research Funds for the Central Universities (DUT19LAB23, DUT18JC09)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
Keywords
random walks, quantum walks, classical random walks, network topology inference, node proximity, link prediction, graph embedding, semi-supervised learning, recommendations, time complexity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review