Application of Random Walks in Data Processing

Yujian Zhang; Hechen Zhang

doi:10.54097/hset.v31i.5152

Authors

Yujian Zhang
Hechen Zhang

DOI:

https://doi.org/10.54097/hset.v31i.5152

Keywords:

Random walk, Non-backtracking random walk, Network Embedding.

Abstract

A random walk is known as a process that a random walker makes consecutive steps in space at equal intervals of time and the length and direction of each step is determined independently. It is an example of Markov processes, meaning that future movements of the random walker are independent of the past. The applications of random walks are quite popular in the field of mathematics, probability and computer science. Random walk related models can be used in different areas such as prediction, recommendation algorithm to recent supervised learning and networks. It is noticeable that there are few reviews about randoms for the beginners and how random walks are used nowadays in distinctive areas. Hence, the aim of the article is to provide a brief review of classical random walks, including basic concepts and models of the algorithm and then some applications in the field of computer science for the beginners to understand the significance and future of random walks.

Downloads

Download data is not yet available.

References

K.Pearson, “Theproblemoftherandomwalk,”Nature,vol.72, no.1867, 1905, Art. no. 342.

F. Xia, J. Liu, H. Nie, Y. Fu, L. Wan and X. Kong, "Random Walks: A Review of Algorithms and Applications," in IEEE Transactions on Emerging Topics in Computational Intelligence, vol. 4, no. 2, pp. 95-107, April 2020, doi: 10.1109/TETCI.2019.2952908.

X. Zhao et al., "Joint Classification of Hyperspectral and LiDAR Data Using Hierarchical Random Walk and Deep CNN Architecture," in IEEE Transactions on Geoscience and Remote Sensing, vol. 58, no. 10, pp. 7355-7370, Oct. 2020, doi: 10.1109/TGRS.2020.2982064.

Fitzner, R., van der Hofstad, R. Non-backtracking Random Walk. J Stat Phys 150, 264–284 (2013). https://doi.org/10.1007/s10955-012-0684-6

T. H. Cupertino, M. Guimarães Carneiro, Q. Zheng, J. Zhang, and L. Zhao, “A scheme for high level data classification using random walk and network measures,” Expert Systems with Applications, vol. 92. Elsevier BV, pp. 289–303, Feb. 2018. doi: 10.1016/j.eswa.2017.09.014.

X. Zhao et al., "Joint Classification of Hyperspectral and LiDAR Data Using Hierarchical Random Walk and Deep CNN Architecture," in IEEE Transactions on Geoscience and Remote Sensing, vol. 58, no. 10, pp. 7355-7370, Oct. 2020, doi: 10.1109/TGRS.2020.2982064.

L. Lovasz. Random walks on graphs: A survey. Bolyai Soc. Math. Studies, 2: 1–46, 1993.

Martin Juvan and Bojan Mohar. Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math., 36(2): 153–168, 1992.

Gianna M. Del Corso and Francesco Romani. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Numerical Algorithms, 28(1–4): 117–136, December 2001.

T. Davis. University of florida sparse matrix collection. NA Digest, 97(23), 1997.

U. Von Luxburg, A. Radl, and M. Hein, “Hitting and commute times in large graphs are often misleading,” 2010, arXiv: 1003.1266.