電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2019-09-06 10:05
ランダム正則グラフにおける分岐型ランダムウォークのモデル化
間屋口琢朗阪口亮太大崎博之関西学院大
技報オンラインサービス実施中
抄録 (和) 情報ネットワークやソーシャルネットワークに代表される大規模ネットワークにおけるさまざまな情報探 索・配送・拡散の問題は、グラフ上の単一もしくは複数の移動エージェントによるランダムウォークによってモデル 化できる。複数の移動エージェントを用いた多重ランダムウォークの冗長性を軽減する手法として、ランダムウォー クに従って移動するエージェントの数を、エージェントの分裂・集約によって動的に変化させるという、分岐型ラン ダムウォーク (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 Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 IA  
開催期間 2019-09-05 - 2019-09-06 
開催地(和) 北海道大学 人文・社会科学総合教育研究棟 1階 W102 
開催地(英) Hokkaido Univ. Humanities and Social Sciences Classroom Bldg, W102 
テーマ(和) インターネット運用・管理、一般 (JANOG協催) 
テーマ(英) Internet Operation and Management, etc. 
講演論文情報の詳細
申込み研究会 IA 
会議コード 2019-09-IA 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) ランダム正則グラフにおける分岐型ランダムウォークのモデル化 
サブタイトル(和)  
タイトル(英) A Study on Modeling Branching Random Walk on Random Regular Graph 
サブタイトル(英)  
キーワード(1)(和/英) 分岐型ランダムウォーク / Branching Random Walk  
キーワード(2)(和/英) グラフ上の移動モデル / Mobility Model on Graph  
キーワード(3)(和/英) 時間変動 / Dynamical Process  
キーワード(4)(和/英) 初回到着時間 / Hitting Time  
キーワード(5)(和/英) 被覆時間 / Cover Time  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 間屋口 琢朗 / Takuro Mayaguchi / マヤグチ タクロウ
第1著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第2著者 氏名(和/英/ヨミ) 阪口 亮太 / Ryota Sakaguchi / サカグチ リョウタ
第2著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第3著者 氏名(和/英/ヨミ) 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ
第3著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-09-06 10:05:00 
発表時間 25 
申込先研究会 IA 
資料番号 IEICE-IA2019-17 
巻番号(vol) IEICE-119 
号番号(no) no.197 
ページ範囲 pp.33-37 
ページ数 IEICE-5 
発行日 IEICE-IA-2019-08-29 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会