文献

J-GLOBAL ID：202002267003232550   整理番号：20A1795601

スパースカットによる高密度部分グラフの発見【JST・京大機械翻訳】

Finding a Dense Subgraph with Sparse Cut

著者 (2件)： Miyauchi Atsushi (RIKEN AIP, Tokyo, Japan) ,  Kakimura Naonori (Keio University, Kanagawa, Japan)
資料名： ACM Proceedings  (ACM Proceedings)
号： CIKM ’18  ページ： 547-556  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： コミュニティ検出はグラフマイニングにおける基本的タスクの1つであり,それは多様なドメインにおいて多くの実世界アプリケーションを持っている。本研究では,内部で高密度に接続され,グラフの残りにまばらに接続されたコミュニティを見つけるための最適化モデルを提案した。モデルは,平均カットサイズを最小にしながら密度を最大化する最も密な部分グラフ問題を拡張した。最初に,提案モデルが効率的に解くことができることを示した。次に,線形プログラミングと最大フローアルゴリズムに基づく2つの多項式時間厳密アルゴリズムを設計した。さらに,実際に大きなサイズのグラフを処理するために,出力の理論的性能保証でほぼ線形時間で実行されるスケーラブルな欲張りアルゴリズムを提示する。さらに,本モデルはモジュール性密度と呼ばれる品質関数に密接に関連しているので,このアルゴリズムはグラフにおける大域的コミュニティ構造を見つけるのにも使用できることを示した。よく知られた実世界グラフを用いた完全実験により,このアルゴリズムがグラフにおける適切なコミュニティを見つけるのに非常に有効であることを示した。例えば,Web-Googleでは,このアルゴリズムは,最密部分グラフ問題に対するベースラインアルゴリズムにより得られた解と比較して,99.1%以上の密度および3.1%未満のカットサイズを持つ解を見つける。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  線形計画法 ,  コミュニティ ,  *部分グラフ ,  応用プログラム ,  線形性 ,  基準線 ,  Web【情報システム】
準シソーラス用語： グラフマイニング ,  Google ,  欲張りアルゴリズム ,  多項式時間 ,  最適化モデル ,  厳密アルゴリズム ,  コミュニティ構造 , 【Automatic Indexing@JST】

著者キーワード (7件)： 近似アルゴリズム ,  コミュニティ検出 ,  最も密な部分グラフ ,  正確なアルゴリズム ,  グラフ ,  モジュール性密度 ,  まばらなカット

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 部分グラフ ,  発見