| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-09-08 10:55 スペクトラルグラフ理論を用いた遷移確率と移動頻度が異なる多様な複数ランダムウォークの解析 ○辻 七海・豊田郁弥・作元雄輔・大崎博之（関西学院大）  IA2021-17 |
|
| 抄録 | （和） | ランダムウォークの代表的な指標の一つである初回接触時間はグラフ上の基礎的な問題であるランデブー問題と密接に関わっており，初回接触時間の性質の理解は効率的なランデブーアルゴリズムを設計する上で重要である．これまでに，ランダムウォークを行う 2 つの移動エージェントの解析が行われており，それらの移動エージェントに対する初回接触時間の性質が明らかにされている．ただし，既存研究では，それぞれの移動エージェントが同じ条件のランダムウォークに従うと仮定している．そこで本稿では，既存研究で扱っているランダムウォークの条件を一般化し，条件の異なる多様なランダムウォークを行う移動エージェントに対する初回接触時間の期待値をスペクトラルグラフ理論に基づいて導出する．本稿の解析で扱う移動エージェントは，(a) それぞれ異なる遷移確率に従ったランダムウォークが行えるとともに，(b) それぞれ異なる移動頻度となることができる．また本稿では，シミュレーション実験を実施し，解析によって導出した初回接触時間の期待値が妥当であることを明らかにする． |
| （英） | The first meeting time is defined by the time it takes for multiple mobile agents starting random walks from different nodes on a graph to first meet at the same node, and is closely related to the rendezvous problem, which is a essential graph problem in computer science. Hence, understanding the characteristics of the first meeting time is important to design an efficient rendezvous algorithm on a graph. In the previous work, we analyzed two mobile agents performing random walks, and clarified the characteristics in their first meeting time. However, the previous work assumed that each mobile agent performs a random walk under the same condition. In this paper, we conduct the analysis of two mobile agents performing diverse random walks, and derive the spectral formula for the expected value of the first meeting time. In the diverse random walks, a mobile agent can (a) follow the different transition probabilities, and (b) move with the different frequencies, than another mobile agent. Moreover, we conduct simulation experiments to clarify the validity of the derived spectral formula for the expected value of the first meeting time. | |
| キーワード | （和） | スペクトラルグラフ理論 / ランデブー問題 / ランダムウォーク / 初回接触時間 / / / / |
| （英） | Spectral Graph Theory / Rendezvous Problem / Random Walk / First Meeting Time / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 167, IA2021-17, pp. 14-21, 2021年9月. | |
| 資料番号 | IA2021-17 | |
| 発行日 | 2021-09-01 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2021-17 |
|
| 研究会情報 | |
| 研究会 | IA |
| 開催期間 | 2021-09-08 - 2021-09-08 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | インターネット運用・管理、一般 |
| テーマ（英） | Internet Operation and Management, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2021-09-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | スペクトラルグラフ理論を用いた遷移確率と移動頻度が異なる多様な複数ランダムウォークの解析 |
| サブタイトル（和） | |
| タイトル（英） | Analysis of Diverse Random Walks with Different Transition Probabilities and Different Moving Frequencies Using Spectral Graph Theory |
| サブタイトル（英） | |
| キーワード(1)（和/英） | スペクトラルグラフ理論 / Spectral Graph Theory |
| キーワード(2)（和/英） | ランデブー問題 / Rendezvous Problem |
| キーワード(3)（和/英） | ランダムウォーク / Random Walk |
| キーワード(4)（和/英） | 初回接触時間 / First Meeting Time |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 辻 七海 / Nanami Tsuji / ツジ ナナミ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 豊田 郁弥 / Fumiya Toyoda / トヨダ フミヤ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 作元 雄輔 / Yusuke Sakumoto / サクモト ユウスケ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第4著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-09-08 10:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IA |
| 資料番号 | IA2021-17 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.167 |
| ページ範囲 | pp.14-21 |
| ページ数 | 8 |
| 発行日 | 2021-09-01 (IA) |
[研究会発表申込システムのトップページに戻る]