The DOI matches its Crossref record; 85 of the 87 references it cites were found in a registry or an index.
Random Walks: A Review of Algorithms and Applications
Open accessAbstract
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“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
Citations
Cites
Efficient Estimation of Word Representations in Vector Space
Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013) · arXiv · doi:10.48550/arxiv.1301.3781 · Cited by 26,568
(1999) · Cited by 12,854
node2vec: Scalable Feature Learning for Networks
Grover, A., & Leskovec, J. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939754 · Cited by 10,926
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,984
GroupLens: an open architecture for collaborative filtering of netnews
Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994) · Proceedings of the 1994 ACM conference on Computer supported cooperative work - CSCW '94 · doi:10.1145/192844.192905 · Cited by 5,058
Semi-Supervised Learning Literature Survey
Zhu, X. (2005) · Cited by 3,828
Semi-supervised learning using Gaussian fields and harmonic functions
Zhu, X., Zoubin Ghahramani, A., & Lafferty, J. (2003) · Cited by 3,509
The link‐prediction problem for social networks
Liben‐Nowell, D., & Kleinberg, J. M. (2007) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20591 · Cited by 3,063
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2010) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,863
Random Walks for Image Segmentation
Grady, L. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.233 · Cited by 2,624
Item-based top- N recommendation algorithms
Deshpande, M., & Karypis, G. (2004) · ACM Transactions on Information Systems · doi:10.1145/963770.963776 · Cited by 2,249
Spitzer, F. (1964) · Springer eBooks · doi:10.1007/978-1-4684-6257-9 · Cited by 2,066
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Aharonov, Y., Davidovich, L., & Zagury, N. (1993) · Physical Review A · doi:10.1103/physreva.48.1687 · Cited by 1,622
Random Walks on Graphs: A Survey
Lovász, L. (2001) · Cited by 1,415
Quantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Cui, P., Wang, X., Pei, J., & Zhu, W. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2849727 · Cited by 1,274
Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.46 · Cited by 1,265
Fast Random Walk with Restart and Its Applications
Tong, H., Faloutsos, C., & Pan, J.-Y. (2006) · Proceedings · doi:10.1109/icdm.2006.70 · Cited by 1,218
Quantum computation and decision trees
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.58.915 · Cited by 1,215
Karypis, G., & Kumar, V. (1997) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 1,213
Quantum random-walk search algorithm
Shenvi, N., Kempe, J., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.67.052307 · Cited by 1,150
Random Walks and Electric Networks
Doyle, P., & Snell, J. (1984) · Carus Mathematical Monographs · doi:10.5948/upo9781614440222 · Cited by 1,061
Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search
Haveliwala, T. H. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1208999 · Cited by 1,046
Quantum random walks - an introductory overview
Kempe, J., & Einstein, A. (2003) · Cited by 1,035
Bäckström, L., & Leskovec, J. (2011) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/1935826.1935914 · Cited by 989
The Problem of the Random Walk
Pearson, K. (1905) · Nature · doi:10.1038/072294b0 · Cited by 974
Reversible Markov Chains and Random Walks on Graphs
Aldous, D., & Fill, J. A. (2014) · Cited by 948
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
Computing and applying trust in web-based social networks
Golbeck, J., & Hendler, J. (2005) · University Libraries (University of Maryland) · Cited by 834
Exponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 814
Jamali, M., & Ester, M. (2009) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1557019.1557067 · Cited by 771
A Random Walks View of Spectral Segmentation.
Meilă, M., & Shi, J. (2001) · Cited by 628
Link prediction based on local random walk
Liu, W., & Lü, L. (2010) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/89/58007 · Cited by 580
Observation of topological edge states in parity–time-symmetric quantum walks
Xiao, L., Zhan, X., Bian, Z. H., Wang, K. K., Zhang, X., Wang, X. P., Li, J., Mochizuki, K., Kim, D., Kawakami, N., et al. (2017) · Nature Physics · doi:10.1038/nphys4204 · Cited by 576
A Survey of Link Prediction in Social Networks
Hasan, M. A., & Zaki, M. J. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3_9 · Cited by 570
Partially labeled classification with Markov Random Walks
Szummer, M., & Jaakkola, T. (2001) · Cited by 557
Quantum walks: a comprehensive reviewPreprint
Venegas-Andraca, S. E. (2012) · Cited by 533
Quantum Amplitude Amplification and Estimation
Gilles Brassard, A., Høyer, P., Mosca, M., & Tapp, A. (2000) · doi:10.48550/arxiv.quant-ph/0005055 · Cited by 514
Automatic multimedia cross-modal correlation discovery
Pan, J.-Y., Yang, H.-J., Faloutsos, C., & Duygulu, P. (2004) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1014052.1014135 · Cited by 484
Extrapolation methods for accelerating PageRank computations
Kamvar, S. D., Haveliwala, T. H., Manning, C. D., & Golub, G. H. (2003) · International World Wide Web Conference (WWW) · doi:10.1145/775152.775190 · Cited by 410
Lindley, D. V., & Spitzer, F. (1965) · Journal of the Royal Statistical Society Series D (The Statistician) · doi:10.2307/2987393 · Cited by 350
Lazy Random Walks for Superpixel Segmentation
Shen, J., Du, Y., Wang, W., & Li, X. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2302892 · Cited by 339
Neighborhood Formation and Anomaly Detection in Bipartite Graphs
Sun, J., Qu, H., Chakrabarti, D., & Faloutsos, C. (2006) · Proceedings · doi:10.1109/icdm.2005.103 · Cited by 313
Liu, Y., Zeng, X., He, Z., & Zou, Q. (2017) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2016.2550432 · Cited by 284
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
Fogaras, D., Rácz, B., Csalogány, K., & Sarlós, T. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129104 · Cited by 283
ItemRank: a random-walk based scoring algorithm for recommender engines
Gori, M., & Pucci, A. (2007) · Use Siena air (University of Siena) · Cited by 277
The Problem of the Random Walk
Pearson, K. (1905) · Nature · doi:10.1038/072342a0 · Cited by 239
Shape Representation and Classification Using the Poisson Equation
Gorelick, L., Galun, M., Sharon, E., Basri, R., & Brandt, A. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.253 · Cited by 235
Multilabel Random Walker Image Segmentation Using Prior Models
Grady, L. J. (2005) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2005.239 · Cited by 219
Simulating Dynamic Quantum Phase Transitions in Photonic Quantum Walks
Wang, K., Qiu, X., Xiao, L., Zhan, X., Bian, Z., Yi, W., & Xue, P. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.020501 · Cited by 213
Sub-Markov Random Walk for Image Segmentation
Dong, X., Shen, J., Shao, L., & Gool, L. V. (2015) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2505184 · Cited by 210
Trust-based recommendation systems
Andersen, R., Borgs, C., Chayes, J., Feige, U., Flaxman, A. D., Kalai, A. T., Mirrokni, V., & Tennenholtz, M. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367525 · Cited by 210
Quantum to Classical Transition for Random Walks
Brun, T. A., Carteret, H. A., & Ambainis, A. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.130602 · Cited by 188
A random walk method for alleviating the sparsity problem in collaborative filtering
Yıldırım, H., & Krishnamoorthy, M. S. (2008) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/1454008.1454031 · Cited by 187
Grady, L. J., & Funka-Lea, G. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27816-0_20 · Cited by 184
Connecting the discrete- and continuous-time quantum walks
Strauch, F. W. (2006) · Physical Review A · doi:10.1103/physreva.74.030301 · Cited by 180
Research Paper Recommender Systems: A Random-Walk Based Approach
Gori, M., & Pucci, A. (2006) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1109/wi.2006.149 · Cited by 172
Paparo, G. D., & Martin-Delgado, M. A. (2012) · Scientific Reports · doi:10.1038/srep00444 · Cited by 136
Data Clustering by Markovian Relaxation and the Information Bottleneck Method
Tishby, N., & Slonim, N. (2000) · Cited by 133
Kang, U., Tong, H., & Sun, J. (2012) · Proceedings of the 2012 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.71 · Cited by 127
MVCWalker: Random Walk-Based Most Valuable Collaborators Recommendation Exploiting Academic Factors
Xia, F., Chen, Z., Wang, W. W., Li, J., & Yang, L. T. (2014) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2014.2356505 · Cited by 109
Self-citationScientific Article Recommendation: Exploiting Common Author Relations and Historical Preferences
Xia, F., Liu, H., Lee, I., & Cao, L. (2016) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2016.2555318 · Cited by 109
Self-citationFast and exact top-k search for random walk with restart
Fujiwara, Y., Nakatsuji, M., Onizuka, M., & Kitsuregawa, M. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2140436.2140441 · Cited by 104
A random walks perspective on maximizing satisfaction and profit
Brand, M. (2005) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.2 · Cited by 96
Quantum algorithms for element distinctness
Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Sántha, M., & de Wolf, R. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933880 · Cited by 94
Quantum Google in a Complex Network
Paparo, G. D., Müller, M., Comellas, F., & Martin-Delgado, M. A. (2013) · Scientific Reports · doi:10.1038/srep02773 · Cited by 92
Azran, A. (2007) · International Conference on Machine Learning · doi:10.1145/1273496.1273503 · Cited by 92
Deterministic realization of collective measurements via photonic quantum walks
Hou, Z., Tang, J.-F., Shang, J., Zhu, H., Li, J., Yuan, Y., Wu, K., Xiang, G., Li, C., & Guo, G. (2018) · Nature Communications · doi:10.1038/s41467-018-03849-x · Cited by 92
A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large GraphsPreprint
Sarkar, P., & Moore, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.5259 · Cited by 76
Knowledge acquisition: A Complex networks approach
de Arruda, H. F., Silva, F. N., Costa, L. D. F., & Amancio, D. R. (2017) · Information Sciences · doi:10.1016/j.ins.2017.08.091 · Cited by 75
Fouss, F., Pirotte, A., & Saerens, M. (2005) · doi:10.1109/wi.2005.9 · Cited by 74
Comparing the topological properties of real and artificially generated scientific manuscripts
Amancio, D. R. (2015) · Scientometrics · doi:10.1007/s11192-015-1637-z · Cited by 69
Fast nearest-neighbor search in disk-resident graphs
Sarkar, P., & Moore, A. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835871 · Cited by 53
Concentric network symmetry grasps authors' styles in word adjacency networks
Amancio, D. R., Silva, F. N., & Costa, L. D. F. (2015) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/110/68001 · Cited by 48
Image Segmentation using Commute times
Qiu, H., & Hancock, E. R. (2005) · British Machine Vision Conference (BMVC) · doi:10.5244/c.19.94 · Cited by 34
Visual Tracking via Random Walks on Graph Model
Li, X., Han, Z., Wang, L., & Lu, H. (2015) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2015.2466437 · Cited by 32
Hitting and commute times in large graphs are often misleadingPreprint
Ulrike Von Luxburg, A., Radl, A., & Hein, M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.1266 · Cited by 32
Random Walks in Social Networks and their Applications: A Survey
Sarkar, P., & Moore, A. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3_3 · Cited by 29
Recommendation Technologies: Survey of Current Methods and Possible Extensions
Adomavičius, G., & Tuzhilin, A. (2004) · Faculty Digital Archive (New York University Florence) · Cited by 20
Quantum Walks: Schur Functions Meet Symmetry Protected Topological Phases
Cedzich, C., Geib, T., Grünbaum, F. A., Velázquez, L., Werner, A. H., & Werner, R. F. (2021) · Communications in Mathematical Physics · doi:10.1007/s00220-021-04284-8 · Cited by 18
Robust Multi-body Motion Tracking Using Commute Time Clustering
Qiu, H., & Hancock, E. R. (2006) · Lecture notes in computer science · doi:10.1007/11744023_13 · Cited by 16
Research works printed but not linked: 2
- wang, 2019, Phys Rev Lett, 122
- 10.1007/978-1-4419-8462-3_3 · DOI
Cited by
Sorted by citations
Xia, F., Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., & Liu, H. (2021) · IEEE Transactions on Artificial Intelligence · doi:10.1109/tai.2021.3076021 · Cited by 534
Self-citationEdge Computing for Internet of Everything: A Survey
Kong, X., Wu, Y., Wang, H., & Xia, F. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3200431 · Cited by 323
Self-citationGraph Neural Networks for Intrusion Detection: A Survey
Bilot, T., Madhoun, N. E., Agha, K. A., & Zouaoui, A. (2023) · IEEE Access · doi:10.1109/access.2023.3275789 · Cited by 294
Fake Reviews Detection: A Survey
Mohawesh, R., Xu, S., Tran, S. N., Ollington, R., Springer, M., Jararweh, Y., & Maqsood, S. (2021) · IEEE Access · doi:10.1109/access.2021.3075573 · Cited by 238
Deepfake video detection: challenges and opportunities
Kaur, A., Noori Hoshyar, A., Saikrishna, V., Firmin, S., & Xia, F. (2024) · Artificial Intelligence Review · doi:10.1007/s10462-024-10810-6 · Cited by 214
“Deepfake leverages the power of artificial intelligence (AI) (Liu et al. 2018; Xia et al. 2019) to manipulate or generate visual and audio content with a high potential to deceive (Kietzmann et al. 2020).”
Self-citation
Metadata
- 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
- green
- arxiv.org
- Licence
- 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 › Computational Theory and Mathematics › 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
