STATISTICAL ANALYSIS OF RANDOM WALKS ON NETWORK

Authors

DOI:

https://doi.org/10.37943/AITU.2021.99.34.007

Keywords:

random work, hitting time, commute time, cover time

Abstract

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.

Author Biography

A. Kalikova, Monash University

MA, Senior-lecturer

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

2021-03-30

How to Cite

Kalikova, A. (2021). STATISTICAL ANALYSIS OF RANDOM WALKS ON NETWORK. Scientific Journal of Astana IT University, 5(5), 77–83. https://doi.org/10.37943/AITU.2021.99.34.007

Issue

Section

Information Technologies
betpas
pendik escort anadolu yakasi escort bostanci escort kadikoy escort kartal escort kurtkoy escort umraniye escort
maltepe escort ataşehir escort ataşehir escort ümraniye escort pendik escort kurtköy escort anadolu yakası escort üsküdar escort şerifali escort kartal escort gebze escort kadıköy escort bostancı escort göztepe escort kadıköy escort bostancı escort üsküdar escort ataşehir escort maltepe escort kurtköy escort anadolu yakası escort ataşehir escort beylikdüzü escort