| 講演名 | 2021-12-17 ［ショートペーパー］グラフ上の不可逆ランダムウォークの初回到着時間および被覆時間に関する一検討 河岸 哲哉(関西学院大), 萩倉 丈(関西学院大), 松尾 涼太郎(関西学院大), 大崎 博之(関西学院大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年、グラフ上のランダムウォークの数理的な特性が明らかにされつつあり、不可逆ランダムウォークや、自己回避型ランダムウォーク、分岐型ランダムウォークなど、単純ランダムウォークの派生モデルの研究も活発に行われている。不可逆ランダムウォークは、単純ランダムウォークに、直前に訪問したノードへの再訪を禁止するという単純な機構を持たせたものである。不可逆ランダムウォークは、単純ランダムウォークよりも良好な特性を持つことが知られている。しかし、グラフ構造が不可逆ランダムウォークの特性に与える影響はこれまで十分に明らかにされていない。そこで本稿では、2 種類の特性の異なるグラフ (ランダム正則グラフおよびコンフィギュレーションモデルによって生成されたグラフ) 上での不可逆ランダムウォークの平均初回到着時間、およびランダム正則グラフ上での不可逆ランダムウォークの平均被覆時間を導出する。さらにいくつかの数値例により、グラフ構造が不可逆ランダムウォークの平均初回到着時間および平均被覆時間に与える影響を分析する。 |
| 抄録(英) | Recently, mathematical properties of random walks on a graph have been studied. Also, several extended models of a simple random walk, such as the non-backtracking random walk, the self-avoiding random walk, and the branching random walk, have been actively studied. The non-backtracking random walk is a simple random walk with a simple mechanism of prohibiting revisits to nodes that have been visited immediately before. The non-backtracking random walk is known to have better properties than a simple random walk. However, the effect of graph structure on the properties of the non-backtracking random has not been clarified well. In this paper, we derive the mean first passage time of the non-backtracking random walk on two types of graphs (i.e., random regular graphs and graphs generated by the configuration model) and the mean cover time of the non-backtracking random walk on random regular graphs. Furthermore, we analyze the impact of the graph structure on the mean first passage time and the mean cover time of the non-backtracking random walk by several numerical examples. |
| キーワード(和) | ランダムウォーク / 平均初回到着時間 / 平均被覆時間 / 不可逆ランダムウォーク / ランダム正則グラフ / コンフィギュレーションモデル |
| キーワード(英) | Random Walk / Mean First Passage Time / Mean Cover Time / Non-backtracking random walk / Random Regular Graph / Configuration Model |
| 資料番号 | IA2021-41 |
| 発行日 | 2021-12-09 (IA) |
| 研究会情報 | |
| 研究会 | IN / IA |
|---|---|
| 開催期間 | 2021/12/16(から2日開催) |
| 開催地（和） | 広島大学東千田キャンパス |
| 開催地（英） | Higashi-Senda campus, Hiroshima Univ. |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、IPv6 、マルチキャスト、ルーティング、DDoS及び一般※※※ 本研究会の2日目は情報指向ネットワーク技術特別研究会(ICN)とも併催です。※※※ |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| 委員長氏名（和） | 石田 賢治(広島市大) / 義久 智樹(阪大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Tomoki Yoshihisa(Osaka Univ.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 近堂 徹(広島大) / 屏 雄一郎(KDDI総合研究所) / 山本 寛(立命館大) |
| 副委員長氏名（英） | Kunio Hato(Internet Multifeed) / Toru Kondo(Hiroshima Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| 幹事氏名（和） | 谷口 展郎(NTT) / 星野 文学(長崎県立大) / 渡部 康平(長岡技科大) / 城 哲(KDDI総合研究所) / 大平 健司(阪大) / 坂野 遼平(工学院大) / 渡辺 俊貴(NEC) |
| 幹事氏名（英） | Noburo Taniguchi(NTT) / Fumitaka Hoshino(Univ. of Nagasaki) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Tetsu Jyo(KDDI Research) / Kenji Ohira(Osaka Univ.) / Ryohei Banno(Kogakuin Univ.) / Toshiki Watanabe(NEC) |
| 幹事補佐氏名（和） | / 小谷 大祐(京大) / 中村 遼(福岡大) / 野林 大起(九工大) |
| 幹事補佐氏名（英） | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamurai(Fukuoka Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［ショートペーパー］グラフ上の不可逆ランダムウォークの初回到着時間および被覆時間に関する一検討 |
| サブタイトル（和） | |
| タイトル（英） | [Short Paper] A Study on First Passage Time and Cover Time of Non-backtracking Random Walk on a Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | 平均初回到着時間 / Mean First Passage Time |
| キーワード(3)（和/英） | 平均被覆時間 / Mean Cover Time |
| キーワード(4)（和/英） | 不可逆ランダムウォーク / Non-backtracking random walk |
| キーワード(5)（和/英） | ランダム正則グラフ / Random Regular Graph |
| キーワード(6)（和/英） | コンフィギュレーションモデル / Configuration Model |
| 第 1 著者 氏名（和/英） | 河岸 哲哉 / Tetsuya Kawagishi |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 萩倉 丈 / Jo Hagikura |
| 第 2 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 3 著者 氏名（和/英） | 松尾 涼太郎 / Ryotaro Matsuo |
| 第 3 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 4 著者 氏名（和/英） | 大崎 博之 / Hiroyuki Ohsaki |
| 第 4 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 発表年月日 | 2021-12-17 |
| 資料番号 | IA2021-41 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | IA-300 |
| ページ範囲 | pp.56-59(IA), |
| ページ数 | 4 |
| 発行日 | 2021-12-09 (IA) |