講演抄録/キーワード |
講演名 |
2019-09-06 10:05
ランダム正則グラフにおける分岐型ランダムウォークのモデル化 ○間屋口琢朗・阪口亮太・大崎博之(関西学院大) IA2019-17 |
抄録 |
(和) |
情報ネットワークやソーシャルネットワークに代表される大規模ネットワークにおけるさまざまな情報探 索・配送・拡散の問題は、グラフ上の単一もしくは複数の移動エージェントによるランダムウォークによってモデル 化できる。複数の移動エージェントを用いた多重ランダムウォークの冗長性を軽減する手法として、ランダムウォー クに従って移動するエージェントの数を、エージェントの分裂・集約によって動的に変化させるという、分岐型ラン ダムウォーク (Branching Random Walk) が提案されている。分岐型ランダムウォークでは、ある始点ノードから移動 を開始したエージェントが、自身の隣接ノードから b 個のノードをランダムに選択し、それらのノードへと分裂する ことにより遷移する。複数のエージェントが同一のノードへと同時に遷移した場合、それらのエージェントは集約さ れる。分岐型ランダムウォークは比較的新しいグラフ上の移動モデルであり、その数理的な特性はこれまで十分に明 らかにされていない。そこで本稿では、ランダム正則グラフにおける、分岐型ランダムウォークのダイナミクスを記 述することにより、分岐パラメーター b と、初回到着時間および平均被覆時間との関係を解析的に明らかにする。 |
(英) |
Several popular problems in information networking and social networking such as search, distribution, and dis- semination can be modeled by random walk of single or multiple agents on a graph. As an approach to remedy the redundancy in multiple random walks, Branching Random Walk (BRW) has been proposed, in which the number of agents of random walks is dynamically changed by the branching-and-aggregation mechanism. An agent starting its walk from an originating node randomly selects b nodes among its neighbor nodes, and it activates those neighbor nodes (branching). If multiple agents simultaneous visit the same node, those agents are unified into a single agent (aggregation). BRW is a relatively new mobility model on a graph. Hence, to the best of our knowledge, understanding of its mathematical properties is quite limited. In this paper, we describe the dynamics of BRW on a random regular graph, and clarify the relation between the branching parameter b and the mean and the distribution of hitting times and the mean cover time. |
キーワード |
(和) |
分岐型ランダムウォーク / グラフ上の移動モデル / 時間変動 / 初回到着時間 / 被覆時間 / / / |
(英) |
Branching Random Walk / Mobility Model on Graph / Dynamical Process / Hitting Time / Cover Time / / / |
文献情報 |
信学技報, vol. 119, no. 197, IA2019-17, pp. 33-37, 2019年9月. |
資料番号 |
IA2019-17 |
発行日 |
2019-08-29 (IA) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IA2019-17 |