TY - GEN

T1 - How many vertices does a random walk miss in a network with moderately increasing the number of vertices?

AU - Kijima, Shuji

AU - Shimizu, Nobutaka

AU - Shiraga, Takeharu

N1 - Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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 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 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 the vertices all but a constant number if the vertex set grows moderately.

AB - 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 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 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 the vertices all but a constant number if the vertex set grows moderately.

UR - http://www.scopus.com/inward/record.url?scp=85102102094&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85102102094&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85102102094

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 106

EP - 122

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -