How Many Vertices Does a Random Walk Miss in a Network with a Moderately Increasing Number of Vertices?

• 成果类型: Article; Early Access
• 署名作者: Kijima, Shuji; Shimizu, Nobutaka; Shiraga, Takeharu
• 署名单位: Shiga University; Chuo University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0060
• 发表日期: 2025
• 关键词: finite markov-chains; cover time; graphs

摘要

Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract 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 but n epsilon vertices if the vertex set grows moderately. Moreover, we apply our model to the growing preferential attachment model that is a prominent random graph model for real networks.