Hitting Times for Random Walks on Sierpiński Graphs and Hierarchical Graphs. (17th April 2020)

• Record Type: Journal Article
• Authors: Qi, Yi; Dong, Yuze; Zhang, Zhongzhi; Zhang, Zhang
• Is Part Of: Computer journal. Volume 63:Number 9(2020)
• Page Start: 1385
• Page End: 1396
• Publication Date: 2020-04-17
• Subjects: WK-recursive network -- interconnection network -- Sierpiński graphs -- hierarchical graphs -- hitting times -- random walks -- Markov chains; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz080
• Languages: English
• ISSNs: 0010-4620

Abstract

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.