| Presentation | 2020-12-04 [Invited Talk] How many vertices does a random walk miss in a network with moderately increasing the number of vertices? Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 studied the number of unvisited vertices of a random walk on a growing graph where a new vertex is attached at an interval defined by some duration function. In this talk, I’d like to show some interesting relationship between duration functions and the number of unvisited vertices. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Cover timeDynamic graphEvolving graphTemporal graph |
| Paper # | COMP2020-23 |
| Date of Issue | 2020-11-27 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2020/12/4(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Vice Chair | Hirotaka Ono(Nagoya Univ) |
| Secretary | Hirotaka Ono(NAIST) |
| Assistant | Yota Otachi(Nagoya Univ) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Invited Talk] How many vertices does a random walk miss in a network with moderately increasing the number of vertices? |
| Sub Title (in English) | |
| Keyword(1) | Cover timeDynamic graphEvolving graphTemporal graph |
| 1st Author's Name | Shuji Kijima |
| 1st Author's Affiliation | Kyushu University(Kyushu Univ.) |
| 2nd Author's Name | Nobutaka Shimizu |
| 2nd Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
| 3rd Author's Name | Takeharu Shiraga |
| 3rd Author's Affiliation | Chuo University(Chuo Univ.) |
| Date | 2020-12-04 |
| Paper # | COMP2020-23 |
| Volume (vol) | vol.120 |
| Number (no) | COMP-276 |
| Page | pp.pp.29-29(COMP), |
| #Pages | 1 |
| Date of Issue | 2020-11-27 (COMP) |