-
Views
-
Cite
Cite
Yi Qi, Yuze Dong, Zhongzhi Zhang, Zhang Zhang, Hitting Times for Random Walks on Sierpiński Graphs and Hierarchical Graphs, The Computer Journal, Volume 63, Issue 9, September 2020, Pages 1385–1396, https://doi.org/10.1093/comjnl/bxz080
- Share Icon Share
Abstract
The Sierpiński graphs and hierarchical graphs are two much studied self-similar networks, both of which are iteratively constructed and have the same number of vertices and edges at any iteration, but display entirely different topological properties. Both graphs have a large variety of applications: Sierpiński graphs have a close connection with WK-recursive networks that are employed extensively in the design and implementation of local area networks and parallel processing architectures, while hierarchical graphs can be used to model complex networks. In this paper, we study hitting times for several absorbing random walks in Sierpiński graphs and hierarchical graphs. For all considered random walks, we determine exact solutions to hitting times for both graphs. The obtained explicit expressions indicate that the hitting times in both graphs behave quite differently. We show that the structural difference of the graphs is responsible for the disparate behaviors of their hitting times.