How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
复制标题
在适度增加顶点数量的网络中，随机游走会丢失多少个顶点？
DOI：
10.1137/1.9781611976465.8
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shiraga Takeharu
中科院分区：
文献类型：
--
作者：
Kijima Shuji;Shimizu Nobutaka;Shiraga Takeharu
真实的网络通常是动态的。对此，动态网络算法的分析越来越受到网络科学与工程界的关注。十多年来，动态图上的随机游走也得到了积极研究，其中在大多数情况下，边集会发生变化，但顶点集是静态的。在许多实际网络中，顶点集也是动态的。受不断增长的网络上随机游走设置的启发，本文介绍了一种具有越来越多顶点的简单图模型，并分析了与此类图上的覆盖时间相关的随机游走。特别是，我们发现，如果顶点集适度增长，随机游走会渐近覆盖除顶点之外的所有顶点。此外，我们将我们的模型应用于不断增长的优先依恋模型，这是真实网络的一个突出的随机图模型。 资金：这项工作得到了日本科学促进会 KAKENHI 的部分支持 [赠款 JP17K19982、JP19J12876、JP19K20214、JP21H03396 和 JP23K21645]。
Real networks are often dynamic. In response to it, analyses of algorithms ondynamic networksattract more and more attention in network science and engineering. Random walks on dynamic graphs have also been actively investigated for over a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by the setting of random walks on growing networks, this paper introduces a simple model of graphs with an increasing number of vertices and presents an analysis of random walks associated with the cover time on such graphs. In particular, we reveal that a random walk asymptotically covers all butvertices if the vertex set growsmoderately. Moreover, we apply our model to the growing preferential attachment model that is a prominent random graph model for real networks.Funding:This work is partly supported by the Japan Society for the Promotion of Science KAKENHI [Grants JP17K19982, JP19J12876, JP19K20214, JP21H03396, and JP23K21645].