| 講演名 | 2022-12-13 ［ショートペーパー］異なる遷移確率を持つランダムウォークに対する初回接触時間の理解に向けて 辻 七海(関西学院大), 作元 雄輔(関西学院大), 大崎 博之(関西学院大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ク?ラフ上のランタ?ムウォークは様々なク?ラフアルコ?リス?ムに活用されており，その理解は効率的なランテ?フ?ーアルコ?リス?ムを設計する上て?重要て?ある．これまて?に我々は，ランタ?ムウォークの代表的な指標の一つて?ある初回接触時間に着目し，異なる遷移確率に従う複数のランタ?ムウォークか?混在する状況下て?の初回接触時間の計算式を導出してきた.本稿て?は，導出された初回接触時間の計算式に対する更なる解析を行い，初回接触時間の性質を明らかにする. |
| 抄録(英) | Random walks on graphs have been used in various graph algorithms, and its understanding is important to design an efficient rendezvous algorithm on graphs. We have focused the first meeting time of multiple random walks following different transition probabilities, and derived the spectral formula of the expected first meeting time. In this paper, we further analyze the derived spectral formula, and clarify the characteristics of the first meeting time. |
| キーワード(和) | スペクトラルグラフ理論 / ランデブー探索 / ランダムウォーク / 初回接触時間 |
| キーワード(英) | Spectral Graph Theory / Rendezvous Search / Random Walk / First Meeting Time |
| 資料番号 | IA2022-59 |
| 発行日 | 2022-12-05 (IA) |
| 研究会情報 | |
| 研究会 | IN / IA |
|---|---|
| 開催期間 | 2022/12/12(から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. |
| 委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 義久 智樹(阪大) |
| 委員長氏名（英） | Kunio Hato(Internet Multifeed) / Tomoki Yoshihisa(Osaka Univ.) |
| 副委員長氏名（和） | 村瀬 勉(名大) / 作元 雄輔(関西学院大) / 屏 雄一郎(KDDI総合研究所) / 山本 寛(立命館大) |
| 副委員長氏名（英） | Tsutomu Murase(Nagoya Univ.) / Yusuke Sakumoto(Kwansei Gakuin Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| 幹事氏名（和） | 城 哲(KDDI総合研究所) / 渡部 康平(長岡技科大) / 秦泉寺 久美(NTT) / 濱田 浩気(NTT) / 大平 健司(阪大) / 坂野 遼平(工学院大) / 野林 大起(九工大) |
| 幹事氏名（英） | Tetsu Jyo(KDDI Research) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Kumi Jinzenji(NTT) / Koki Hamada(NTT) / Kenji Ohira(Osaka Univ.) / Ryohei Banno(Kogakuin Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) |
| 幹事補佐氏名（和） | / 小谷 大祐(京大) / 中村 遼(福岡大) / 中村 遼(東大) |
| 幹事補佐氏名（英） | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamura(Fukuoka Univ.) / Ryo Nakamura(Univ. of Tokyo) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［ショートペーパー］異なる遷移確率を持つランダムウォークに対する初回接触時間の理解に向けて |
| サブタイトル（和） | |
| タイトル（英） | [Short Paper] For Understanding the First Meeting Time of Multiple Random Walks with Different Transition Probabilities |
| サブタイトル（和） | |
| キーワード(1)（和/英） | スペクトラルグラフ理論 / Spectral Graph Theory |
| キーワード(2)（和/英） | ランデブー探索 / Rendezvous Search |
| キーワード(3)（和/英） | ランダムウォーク / Random Walk |
| キーワード(4)（和/英） | 初回接触時間 / First Meeting Time |
| 第 1 著者 氏名（和/英） | 辻 七海 / Nanami Tsuji |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 作元 雄輔 / Yusuke Sakumoto |
| 第 2 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 3 著者 氏名（和/英） | 大崎 博之 / Hiroyuki Osaki |
| 第 3 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 発表年月日 | 2022-12-13 |
| 資料番号 | IA2022-59 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IA-306 |
| ページ範囲 | pp.60-63(IA), |
| ページ数 | 4 |
| 発行日 | 2022-12-05 (IA) |