论文标题
一个随机步行在网络中的随机步行数量中等增加了几个顶点？
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
论文作者
论文摘要
真正的网络通常是动态的。为此，{\ em Dynamic Networks}对算法的分析吸引了越来越多的网络科学和工程学注意事项。十多年来，在动态图上的随机步行也已经积极研究，在大多数情况下，边缘集更改，但顶点集是静态的。在许多真实网络中，顶点集也是动态的。本文由在动态图上进行随机步行的新技术进行了激励，本文引入了一个简单的图形模型，并增加了顶点的数量，并介绍了与此类图上覆盖时间相关的随机步行的分析。特别是，我们揭示了一个随机行走渐近地覆盖顶点，但如果顶点集生长{\ em中等}，则除了一个常数数字外。
Real networks are often dynamic. In response to it, analyses of algorithms on {\em dynamic networks} attract more and more attentions in network science and engineering. Random walks on dynamic graphs also have been investigated actively in more than 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 a new technology of the analysis of random walks on dynamic graphs, this paper introduces a simple model of graphs with increasing the 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 the vertices all but a constant number if the vertex set grows {\em moderately}.
