Hitting Times for Random Walks on Sierpiński Graphs and Hierarchical Graphs
Hitting Times for Random Walks on Sierpiński Graphs and Hierarchical Graphs
复制标题
DOI：
10.1093/comjnl/bxz080
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Yi Qi;Yuze Dong;Zhongzhi Zhang;Zhang Zhang-Zhang
中科院分区：
文献类型：
--
作者：
Yi Qi;Yuze Dong;Zhongzhi Zhang;Zhang Zhang-Zhang
Sierpiński图和层次图是两个被广泛研究的自相似网络，它们都是迭代构建的，在任何迭代中具有相同数量的顶点和边，但显示完全不同的拓扑性质。这两种图都有各种各样的应用：Sierpiński图与wk -递归网络密切相关，wk -递归网络广泛用于局域网和并行处理架构的设计和实现，而分层图可用于复杂网络的建模。本文研究了Sierpiński图和层次图中几种吸收随机游动的命中时间。对于所有考虑的随机漫步，我们确定两个图命中时间的精确解。得到的显式表达式表明，两个图中的命中时间表现出很大的不同。我们证明了图的结构差异是它们命中时间的不同行为的原因。
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.