Graph Generation and Diffusion using Random Walks
DOI:
https://doi.org/10.54097/hset.v16i.2628Keywords:
Monte Carlo method, random walk, graph theory, graph generation, simple random graphs.Abstract
Simulations are often used in the study of metro network systems and the interactions of passengers with such systems in the real life. Graph theory is used to represent such metro systems. Simple random graphs are generated using a random graph generation algorithm revolving around random walks. The goal is to use such graphs to analyze the effects of the topologies of the graph parallel to the events which happen in real metro systems. This is done through random walks on the graphs by Monte Carlo Simulation of those random walkers. The simulations showed that the degree of a node in the graph has a near linear relationship with the number of times a specific node has been visited.
Downloads
References
Chen, H. (2020, December 26). Shanghai adds 7,000th train to Metro fleet. Shanghai Daily. https://www.shine.cn/news/metro/2012252178
Kansky, K. J. (1963). Structure of transportation networks: relationships between network geometry and regional characteristics (Doctoral dissertation, The University of Chicago).
Gattuso, D., & Miriello, E. (2005). Compared analysis of metro networks supported by graph theory. Networks and Spatial Economics, 5(4), 395-414.
Pons, P., & Latapy, M. (2005, October). Computing communities in large networks using random walks. In International symposium on computer and information sciences (pp. 284-293). Springer, Berlin, Heidelberg.
Masuda, N., Porter, M. A., & Lambiotte, R. (2017). Random walks and diffusion on networks. Physics reports, 716, 1-58.
Zhu, Y., Zhao, L., Li, W., Wang, Q. A., & Cai, X. (2016). Random walks on real metro systems. International Journal of Modern Physics C, 27(10), 1650122.
Stoilova, S., & Stoev, V. (2015). An application of the graph theory which examines the metro networks. Transport Problems, 10.
Psaltoglou, A., & Calle, E. (2018). Enhanced connectivity index–A new measure for identifying critical points in urban public transportation networks. International Journal of Critical Infrastructure Protection, 21, 22-32.
Xie, P., Ma, M., Li, T., Ji, S., Du, S., Yu, Z., & Zhang, J. (2022). Spatio-Temporal Dynamic Graph Relation Learning for Urban Metro Flow Prediction. arXiv preprint arXiv:2204.02650.
Bloem‐Reddy, B., & Orbanz, P. (2018). Random‐walk models of network formation and sequential Monte Carlo methods for graphs. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(5), 871-898.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
