文献

J-GLOBAL ID：201702217063709886   整理番号：17A0314886

MIRACLE:大きなグラフのための複数の独立したランダムウォーク地域並列検出アルゴリズム【Powered by NICT】

MIRACLE: A multiple independent random walks community parallel detection algorithm for big graphs

著者 (5件)： Liu Xiaoming (Ministry of Education Key Lab for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China) ,  Zhou Yadong (Ministry of Education Key Lab for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China) ,  Hu Chengchen (Ministry of Education Key Lab for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China) ,  Guan Xiaohong (Ministry of Education Key Lab for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China) ,  Guan Xiaohong (Center for Intelligent and Networked Systems and TNLIST Lab, Tsinghua University, Beijing 100084, China)
資料名： Journal of Network and Computer Applications  (Journal of Network and Computer Applications)
巻： 70  ページ： 89-101  発行年： 2016年07月 
JST資料番号： H0842A  ISSN： 1084-8045  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： コミュニティ検出は様々なタイプの複雑なネットワークの共通の問題である。ソーシャルネットワークのような大規模な実際のネットワークの出現により,コミュニティ検出は非常に大きな計算コストの新技術挑戦と事前情報の欠如を満たした。いくつかの文献は,最近これらの新しい課題を解決しようとするが,それらはまだ並列性と実行時間の限界がある。データ急激に増加しの尺度では,並列性が必要であるいくつかのコードが存在するが。本研究では,グラフにおけるランダム歩行のプロセスを分析し,歩行者が訪れる頂点を処理することにより得られ,辺の重みは頂点接続の近さを測定するための指標であり得ることを観測した。この知見に基づき,筆者らは最初に真の意味で大きな重み無し無向グラフのための新しい並列計算コミュニティ検出アルゴリズムを提案した。アルゴリズムは三段階,複数の独立した酔歩を用いたランダム歩行を含むから構成され,エッジとコミュニティを検出するための計算量。このアルゴリズムの時間計算量は事前情報なしにO(n logn)である。並列計算アルゴリズムを効率的に実行するために,著者らはまた新規グラフを提案した分配モデル。実験を行いその結果,提案アルゴリズムは,群集構造および実世界効果的に(少なくとも実行時間を400倍)におけるコミュニティの重複部分を検出し,大きなグラフ時代におけるコミュニティ検出の課題を扱うことができることを示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *アルゴリズム ,  無向グラフ ,  計算量 ,  並列演算 ,  ネットワーク ,  *酔歩 ,  コミュニティ ,  歩行者 ,  時間計算量 ,  計算コスト ,  *検出アルゴリズム
準シソーラス用語： 実行時間 ,  事前知識 ,  社会的ネットワーク ,  コミュニティ検出 , 【Automatic Indexing@JST】

著者キーワード (5件)： コミュニティ検出 ,  複雑ネットワーク ,  社会的ネットワーク ,  ランダム歩行 ,  並列計算

分類 (1件)： 計算機網  (JC03000K)

タイトルに関連する用語 (4件)： グラフ ,  ランダムウォーク ,  地域 ,  検出アルゴリズム