Exact determination of MFPT for random walks on rounded fractal networks with varying topologies

• DOI: 10.1093/comnet/cnae020
• Publication Date: 2024-05-22T16:30:50Z
• Authors: Yuanyuan Liu; Jing Chen; Weigang Sun
• Keywords: 0103 physical sciences; 01 natural sciences

Abstract Random walk is a stochastic process that moves through a network between different states according to a set of probability rules. This mechanism is crucial for understanding the importance of nodes and their similarities, and it is widely used in page ranking, information retrieval and community detection. In this study, we introduce a family of rounded fractal networks with varying topologies and conduct an analysis to investigate the scaling behaviour of the mean first-passage time (MFPT) for random walks. We present an exact analytical expression for MFPT, which is subsequently confirmed through direct numerical calculations. Furthermore, our approach for calculating this interesting quantity is based on the self-similar structure of the rounded networks, eliminating the need to compute each Laplacian spectrum. Finally, we conclude that a more efficient random walk is achieved by reducing the number of polygons and edges. Rounded fractal networks demonstrate superior efficiency in random walks at the initial state, primarily due to the minimal distances between vertices.