| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-09-08 10:30 移動の局所性を緩和したグラフ上のランダムウォーク ○北浦敬太・松尾涼太郎・大崎博之（関西学院大）  IA2021-16 |
|
| 抄録 | （和） | グラフ上のランダムウォークは、直線上もしくは平面上のランダムウォークを、グラフ上に拡張した数理的な移動モデルである。近年、グラフ上の離散時間ランダムウォークの数理的な特性の解析や大規模ネットワーク探査への応用など、グラフ上のランダムウォークに関するさまざまな研究が活発に行なわれている。グラフ上のランダムウォークは、移動エージェントが短期間に同一のノードを複数回訪問する可能性が高いという局所性を有している。グラフ上のランダムウォークが有する局所性を緩和させることができれば、ランダムウォークの特性 (例: 初回到着時間や被覆時間) が改善できることが期待される。本稿では、移動エージェントに大量の記憶領域を持たせることなく、ランダムウォークの局所性を緩和することにより、ランダムウォークの特性を改善する手法である周辺回避ランダムウォークを提案する。さらに、周辺回避ランダムウォークを用いることにより単純ランダムウォークや不可逆ランダムウォークと比較して、ランダムウォークの代表的な特性である平均初回到着時間および平均被覆時間がどの程度削減されるのかをシミュレーション実験により調査する。また、コミュニティ構造を有するグラフにおいて、類似した手法である不可逆ランダムウォークと比較したときの周辺回避ランダムウォークの有効性を数理的に分析する。さらに、数値例により、グラフのコミュニティ構造がそれぞれのランダムウォークの特性に与える影響を分析するとともに、解析の妥当性を調査する。 |
| （英） | A random walk on a graph is a mathematical mobility model that extends a random walk on a line or a plane to a graph. In recent years, several researches on random walks on a graph have been actively conducted, such as analyses of mathematical properties of a discrete random walk on a graph and its application to large-scale network exploration. The random walk on a graph has strong locality such that a mobile agent is likely to visit the same node multiple times in a short period of time. If the locality of the random walk on a graph can be mitigated, it is expected that the properties of the random walk (e.g., the average first passage time and the average cover time) can be improved. In this paper, we propose the Vicinity-Avoiding Random Walk, a mobility model based on the random walk with less locality without requiring a large amount of storage in the mobile agent. In addition, we investigate how much the Vicinity-Avoiding Random Walk reduces the average first passage time and the average cover time, which are typical measures of random walks, compared to the simple random walk and the non-backtracking random walk, through simulation experiments. We also analiticaliy investigate the effectiveness of Vicinity-Avoiding Random Walk in comparison with a similar method, non-backtracking random walk in terms of the average first passage time in graphs with community structure. Furthermore, we will also investigate the impact of the community structure of a graph on random walks through a numerical example as well as the validity of our analysis. | |
| キーワード | （和） | ランダムウォーク / 移動の局所性 / 平均初回到着時間 / 平均被覆時間 / / / / |
| （英） | Random Walk / Locality / Average first passage time / Average cover time / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 167, IA2021-16, pp. 7-13, 2021年9月. | |
| 資料番号 | IA2021-16 | |
| 発行日 | 2021-09-01 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2021-16 |
|
| 研究会情報 | |
| 研究会 | IA |
| 開催期間 | 2021-09-08 - 2021-09-08 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | インターネット運用・管理、一般 |
| テーマ（英） | Internet Operation and Management, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2021-09-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | 移動の局所性を緩和したグラフ上のランダムウォーク |
| サブタイトル（和） | |
| タイトル（英） | Random Walk on Graphs with Vicinity Avoidance |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | 移動の局所性 / Locality |
| キーワード(3)（和/英） | 平均初回到着時間 / Average first passage time |
| キーワード(4)（和/英） | 平均被覆時間 / Average cover time |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 北浦 敬太 / Keita Kitaura / キタウラ ケイタ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 松尾 涼太郎 / Ryotaro Matsuo / マツオ リョウタロウ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-09-08 10:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IA |
| 資料番号 | IA2021-16 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.167 |
| ページ範囲 | pp.7-13 |
| ページ数 | 7 |
| 発行日 | 2021-09-01 (IA) |
[研究会発表申込システムのトップページに戻る]