文献

J-GLOBAL ID：201702268391727226   整理番号：17A1269943

線形時間での分散計算ランダムウォーク中間中心性【Powered by NICT】

Distributively Computing Random Walk Betweenness Centrality in Linear Time

著者 (5件)： Hua Qiang-Sheng ,  Ai Ming ,  Jin Hai ,  Yu Dongxiao ,  Shi Xuanhua
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICDCS  ページ： 764-774  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ノードの媒介中心性ネットワークにおける情報の広がりに対するその影響を示した。通常全ての最短経路間のノードを通過する最短経路の数の比として定義した。しかし,情報の普及は酔歩[1]に基づく間の中心度の新しい尺度によって捕捉されるが最短経路を通過しない可能性がある。ノードの酔歩媒介中心性は,他のノードの全ペア間のランダムウォークによって横断される頻度を意味している。本論文では,ノード数をnとした近似比(1 εを用い,各ノードのランダム歩行間の中心度を計算するためのO(n logn)時間分散ランダム化近似アルゴリズムを提案し,εは0と1の間の任意の小さな一定であった。分散アルゴリズムは,広く用いられているCONGESTモデルの下で設計されており,各辺が各ラウンドにおけるO(logn)ビットを移動できるだけである。著者らの知る限り,これはランダムウォーク間の中心度を計算するための,初めての分散アルゴリズムである。CONGESTモデル,Dはネットワーク直径であり,これはΩ(nlogn+D)下で正確な酔歩間の中心度を計算する分散のための非自明な下限を与えた。これはランダムウォークは中間計算下位線形時間で実施することができない厳密に意味する。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *計算 ,  近似法 ,  *線形性 ,  ネットワーク ,  *酔歩 ,  分散アルゴリズム
準シソーラス用語： 近似アルゴリズム ,  中心度 ,  最短経路 ,  *中間中心度 ,  *分散計算 , 【Automatic Indexing@JST】

分類 (2件)： ネットワーク法  (KA03040X) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 線形 ,  分散計算 ,  ランダムウォーク ,  中間中心性