文献

J-GLOBAL ID：201702238536998003   整理番号：17A0829237

より高速なグラフの反高密度化による地域探索問題の高速化【Powered by NICT】

Accelerating community-search problem through faster graph dedensification

著者 (5件)： Khan Kifayat Ullah (Dept. of Computer Science and Engineering, Kyung Hee University, Republic of Korea) ,  Tu Nguyen Anh (Dept. of Computer Science and Engineering, Kyung Hee University, Republic of Korea) ,  Akhond Mostafijur Rahman (Dept. of Computer Science and Engineering, Kyung Hee University, Republic of Korea) ,  Nawaz Waqas (Islamic University Almadinah, Saudi Arabia) ,  Lee Young-Koo (Dept. of Computer Science and Engineering, Kyung Hee University, Republic of Korea)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： BigComp  ページ： 340-347  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： コミュニティ探索は大きなグラフから密連結部分グラフの発見,質問ノードの与えられたセットの問題である。いくつかの高プロファイルの研究者が会議を配置する場合,例えば,有用であるまたはいくつかの著名人は関係者を配置すると,それぞれ他の研究者と類似したpersonaltiesを求めて。技術的に,問題は高度に連結した部分グラフを見つけるために最小次数を最大化することである。良く知られている欲張りアルゴリズムをこの目的のために,反復的にある目的関数に対応する最小次数を持つノードを消去する。欲張りグラフにおける密結合領域,ホットスポットと呼ばれるによる非効率的に動作することを観測した。本論文では,dedensifiedグラフ上のコミュニティ探索を行うことの新しい概念を提供する。著者らの目的は,大規模グラフに適用できるように欲張りの大域的探索法を加速するためにホットスポットをスパース化することである。最近の反高密度化のためのグラフにおける圧縮機ノードを加えることが提案されているグラフの反高密度化アプローチ。しかし,ホットスポットを圧縮するために全グラフを横断しなければならないので,この方法は非効率な。この問題を解決するために,局所性高感度ハッシング(LSH)を用いて高速グラフの反高密度化アルゴリズムを提案した。O(|E|)O(N+e_HDN+k)への既存のグラフの反高密度化法の時間計算量を改善し,N,E,e_HDN,Kは,ノード,エッジ,高度ノード(HDN)のエッジ,ハッシュ関数,およびN≫水素化脱窒素(HDN)した。グラフであるdedensifiedと,著者らは群集探索操作を加速するために,用いた。二実世界グラフ上での実験を行い,欲張りアルゴリズムの実行時間の著しい改善を観測し,少ない圧縮機ノードを追加し,グラフの反高密度化のための還元走査を行った。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件)： 人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： グラフ ,  高密度化 ,  地域 ,  探索問題 ,  高速化