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

講演抄録/キーワード
講演名 2018-11-28 14:40
未知のネットワークにおける複数のランダムウォークを用いた協力型探索法の検討
作元雄輔首都大東京)・大崎博之関西学院大
技報オンラインサービス実施中
抄録 (和) 通信を開始する際には,通信要求を持つノードは相手先ノードを特定しなければならない.各ノードが一部のノード(隣接ノード) しか調べられないような未知のネットワークでは,相手先ノードを特定するために,要求ノードから隣接ノードを辿って探索する方法が用いられている.ランダムウォーク探索法は,要求ノードから確率的に辿る(ランダムウォークを行う) 複数のエージェントを用いて相手先ノードを発見しようとするものであり,フラッディング探索法よりも低負荷で相手先ノードを発見できることが示されている.ただし,探索時間の期待値は相手先ノードの次数に反比例するため,相手先ノードの次数が大きくばらつく場合には,最小となる探索時間の期待値は小さくなるという長所がある一方で,相手先ノードをランダムに選択した時の平均的な探索時間の期待値は大きくなるという短所がある.本稿では,要求ノードと相手先ノードが共にランダムウォークエージェントを用いて協力的に探索する方法を検討し,既存のランダムウォーク探索法の長所を保持しつつも短所が改善できることを示す.その際に,次数分布のばらつきが大きいネットワークにおいては,協力型探索法は既存のランダムウォーク探索法に比べて平均探索時間の期待値が O(1/log n) だけ小さいことを明らかにする.また,シミュレーション実験を通して,導出したオーダの妥当性を検証するとともに,協力型探索法が高い効率性を持つことを明らかにする. 
(英) To begin the communication between two nodes, the node with the communication request must specify the location of the partner node. If the network is unstructured where each node can access some nodes (adjacent node), the request node should search the partner node by tracing adjacent nodes. Random walk search is the method using multiple agents to perform random work starting from the request node. The previous works show that the cost of the random walk search is smaller than that of the well-known flooding search, and the expected search time has the inverse relationship to the degree of the partner node. Because of the inverse relationship, when node degrees vary largely, the random walk search has the advantage that the minimum of the expected search time is small, but the disadvantage that the average of the expected search time is long. In this paper, we discuss the cooperative search using random walks starting from the request node and the partner node, and show that the cooperative search alleviates the disadvantage of the conventional random walk search while keeping its advantage. We derive that the order of the average search time of the cooperative search, and clarify that the order is O(1/log n) smaller than that of the conventional random walk search. Through the simulation experiment, we verify the derived order, and investigate the efficiency of the cooperative search.
キーワード (和) スペクトラルグラフ理論 / ノード探索 / フラッディング / ランダムウォーク / / / /  
(英) Spectral Graph Theory / Node Search / Flooding / Random Walk / / / /  
文献情報 信学技報, vol. 118, no. 326, IA2018-36, pp. 1-8, 2018年11月.
資料番号 IA2018-36 
発行日 2018-11-21 (IA) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 IA  
開催期間 2018-11-28 - 2018-11-28 
開催地(和) 秋葉原コンベンションホール 5階カンファレンスフロア(5B) 
開催地(英) Akihabara Convention Hall, 5th Floor (Conference Room 5B) 
テーマ(和) 学生セッション、一般(日本学術振興会 インターネット技術第163委員会 共催) 
テーマ(英) Student Sessions, etc. (cosponsored by JSPS 163rd Committee on Internet Technology) 
講演論文情報の詳細
申込み研究会 IA 
会議コード 2018-11-IA 
本文の言語 日本語 
タイトル(和) 未知のネットワークにおける複数のランダムウォークを用いた協力型探索法の検討 
サブタイトル(和)  
タイトル(英) A Study on the Cooperative Search Using Multiple Random Walks in Unstructured Network 
サブタイトル(英)  
キーワード(1)(和/英) スペクトラルグラフ理論 / Spectral Graph Theory  
キーワード(2)(和/英) ノード探索 / Node Search  
キーワード(3)(和/英) フラッディング / Flooding  
キーワード(4)(和/英) ランダムウォーク / Random Walk  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 作元 雄輔 / Yusuke Sakumoto / サクモト ユウスケ
第1著者 所属(和/英) 首都大学東京 (略称: 首都大東京)
Tokyo Metropolitan University (略称: Tokyo Metropolitan Univ.)
第2著者 氏名(和/英/ヨミ) 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ
第2著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2018-11-28 14:40:00 
発表時間 25 
申込先研究会 IA 
資料番号 IEICE-IA2018-36 
巻番号(vol) IEICE-118 
号番号(no) no.326 
ページ範囲 pp.1-8 
ページ数 IEICE-8 
発行日 IEICE-IA-2018-11-21 


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

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


IEICE / 電子情報通信学会