文献

J-GLOBAL ID：202102259278552854   整理番号：21A3269331

大規模グラフにおける最大クリークの高速数え上げについて【JST・京大機械翻訳】

On fast enumeration of maximal cliques in large graphs

著者 (5件)： Jin Yan (School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China) ,  Xiong Bowen (School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China) ,  He Kun (School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China) ,  Zhou Yangming (School of Information Science and Engineering, East China University of Science and Technology, Shanghai, China) ,  Zhou Yi (School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China)
資料名： Expert Systems with Applications  (Expert Systems with Applications)
巻： 187  ページ： Null  発行年： 2022年 
JST資料番号： W0178A  ISSN： 0957-4174  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最尤法(MCE)はグラフ理論や様々なネットワークアプリケーションにおける基本的で挑戦的な問題である。過去数十年間,多数のアルゴリズムが提案されてきたが,大きなグラフにおける実用効率の改善に焦点を当てた。この目的のために,Bron-Kerboschフレームワークに基づくFACENと呼ばれる効率的なアルゴリズムを提案した。メモリと時間消費を最適化するために,著者らは隣接リストと部分的隣接マトリックスを有するハイブリッドデータ構造を適用し,縮退順序に基づく動的ピボット選択規則を導入する。FACENを,様々な情報源から合計64のベンチマーク事例で評価した。計算結果から,提案アルゴリズムは電流主導MCE法と非常に競合することを示した。特に,提案アルゴリズムは,数百万の頂点とエッジを持つテストされた実世界ソーシャルネットワーク上のすべての最大クリークを列挙できる。非常に大きなグラフに対して,著者らは,下限を有するMCE変異体を解くための追加実験を提供し,FACENの利点を調べた。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  記憶装置 ,  最適化 ,  電流 ,  グラフ理論 ,  情報源 ,  データ構造 ,  最尤法 ,  選択則 ,  縮退 ,  ベンチマーク
準シソーラス用語： 社会的ネットワーク ,  ネットワークアプリケーション ,  *最大クリーク , 【Automatic Indexing@JST】

著者キーワード (5件)： 最大クリーク数え上げ ,  正確なアルゴリズム ,  NP困難 ,  Bron-Kerboschアルゴリズム ,  社会ネットワーク

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

タイトルに関連する用語 (3件)： 大規模 ,  グラフ ,  最大クリーク