| 講演名 | 2020-12-04 [Invited Talk] How many vertices does a random walk miss in a network with moderately increasing the number of vertices? 来嶋 秀治(九大), 清水 伸高(東大), 白髪 丈晴(中大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | 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. |
| キーワード(和) | |
| キーワード(英) | Cover timeDynamic graphEvolving graphTemporal graph |
| 資料番号 | COMP2020-23 |
| 発行日 | 2020-11-27 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2020/12/4(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | [Invited Talk] How many vertices does a random walk miss in a network with moderately increasing the number of vertices? |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / Cover timeDynamic graphEvolving graphTemporal graph |
| 第 1 著者 氏名（和/英） | 来嶋 秀治 / Shuji Kijima |
| 第 1 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 2 著者 氏名（和/英） | 清水 伸高 / Nobutaka Shimizu |
| 第 2 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：The Univ. of Tokyo) |
| 第 3 著者 氏名（和/英） | 白髪 丈晴 / Takeharu Shiraga |
| 第 3 著者 所属（和/英） | 中央大学(略称：中大) Chuo University(略称：Chuo Univ.) |
| 発表年月日 | 2020-12-04 |
| 資料番号 | COMP2020-23 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | COMP-276 |
| ページ範囲 | pp.29-29(COMP), |
| ページ数 | 1 |
| 発行日 | 2020-11-27 (COMP) |