STATISTICAL ANALYSIS OF RANDOM WALKS ON NETWORK
DOI:
https://doi.org/10.37943/AITU.2021.99.34.007Keywords:
random work, hitting time, commute time, cover timeAbstract
This paper describes an investigation of analytical formulas for parameters in random walks. Random walks are used to model situations in which an object moves in a sequence of steps in randomly chosen directions. Given a graph and a starting point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at random, and move to it etc. It is a fundamental dynamic process that arises in many models in mathematics, physics, informatics and can be used to model random processes inherent to many important applications. Different aspects of the theory of random walks on graphs are surveyed. In particular, estimates on the important parameters of hitting time, commute time, cover time are discussed in various works. In some papers, authors have derived an analytical expression for the distribution of the cover time for a random walk over an arbitrary graph that was tested for small values of n. However, this work will show the simplified analytical expressions for distribution of hitting time, commute time, cover time for bigger values of n. Moreover, this work will present the probability mass function and the cumulative distribution function for hitting time, commute time.
References
Zlatanov, N., & Kocarev, L. (2009). Random walks on networks: Cumulative distribution of cover time. Physical Review E, 80(4), 041102
Kang, U., Tong, H., & Sun, J. (2012, April). Fast random walk graph kernel. In Proceedings of the 2012 SIAM international conference on data mining (pp. 828-838). Society for Industrial and Applied Mathematics.
Adeleye, O., Yu, J., Ruan, J., & Sheng, Q. Z. (2020, February). Evaluating random walk-based network embeddings for web service applications. In Australasian Database Conference (pp. 198-205). Springer, Cham.
Amancio, D.R., Silva, F.N., & Costa, L. D.F. (2015). Concentric network symmetry grasps authors’ styles in word adjacency networks. EPL (Europhysics Letters), 110(6), 68001.
Li, X., Han, Z., Wang, L., & Lu, H. (2015). Visual tracking via random walks on graph model. IEEE transactions on Cybernetics, 46(9), 2144-2155.
Dong, X., Shen, J., Shao, L., & Van Gool, L. (2015). Sub-Markov random walk for image segmentation. IEEE Transactions on Image Processing, 25(2), 516-527.
Spitzer, F. (2013). Principles of random walk (Vol. 34). Springer Science & Business Media.
Backstrom, L., & Leskovec, J. (2011, February). Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining (pp. 635-644).
Condamin, S., Bénichou, O., Tejedor, V., Voituriez, R., & Klafter, J. (2007). First-passage times in complex scale-invariant media. Nature, 450(7166), 77-80.
Nghiem, T.P., Maulana, K., Waluyo, A.B., Green, D., & Taniar, D. (2013, March). Bichromatic reverse nearest neighbors in mobile peer-to-peer networks. In 2013 IEEE International Conference on Pervasive Computing and Communications (PerCom) (pp. 160-165). IEEE.
Arunachalam, A., & Sornil, O. (2015, February). An analysis of the overhead and energy consumption in flooding, random walk and gossip based resource discovery protocols in MP2P networks. In 2015 Fifth International Conference on Advanced Computing & Communication Technologies (pp. 292-297). IEEE.
Gurkan, T., Resul, D., Ramakrishnan B., Kilicaslan Y. (2017) Big Data Analysis for M2M Networks: Research Challenges and Open Research Issues. International Journal of Computer Networks and Applications (IJCNA), 27-34.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who publish a manuscript in this journal agree to the following terms:
- The authors reserve the right to authorship of their work and transfer to the journal the right of first publication under the terms of the Creative Commons Attribution License, which allows others to freely distribute the published work with a mandatory link to the the original work and the first publication of the work in this journal.
- Authors have the right to conclude independent additional agreements that relate to the non-exclusive distribution of the work in the form in which it was published by this journal (for example, to post the work in the electronic repository of the institution or publish as part of a monograph), providing the link to the first publication of the work in this journal.
- Other terms stated in the Copyright Agreement.