文献

J-GLOBAL ID：201602217326522974   整理番号：16A0659870

極大クリーク列挙を用いた高速なkクリークコミュニティのオンライン探索

Fast Online Search of k-Clique Communities by Maximal Clique Enumeration

著者 (3件)： 矢野洋祐 (国立情報学研) ,  照山順一 (国立情報学研) ,  吉田悠一 (国立情報学研)
資料名： 日本データベース学会和文論文誌(Web)  (DBSJ Japanese Journal (Web))
巻： 14-J  ページ： ROMBUNNO.5 (WEB ONLY)  発行年： 2016年03月 
JST資料番号： U0795A  ISSN： 2189-0374  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 現実世界のグラフにはコミュニティという密な部分構造が存在することが知られており,その検出はネットワークを解析する上で重要である。しかし,巨大なグラフにおいて全てのコミュニティを検出することは困難なため,近年になって指定された頂点を含むようなコミュニティを探索する問題が提唱された。kクリークコミュニティは頂点が複数のグループに属することを許すクリークに基づいたコミュニティモデルである。本論文では,クエリ頂点を含むkクリークコミュニティを列挙する問題に対して新しいアルゴリズムを提案する。提案手法は,必要な極大クリークのみを注意深く列挙しながらそれらの隣接関係を計算することにより高速なコミュニティの列挙を実現する。実験により,提案手法が既存手法より高速に動作することを示した。(著者抄録)

シソーラス用語： *情報検索 ,  *クリーク ,  *コミュニティ ,  解析 ,  最適化 ,  設計 ,  グラフ ,  性質
準シソーラス用語： Webグラフ ,  アルゴリズム設計 ,  *オンラインコミュニティ ,  *オンライン情報検索 ,  クエリ最適化 ,  ネットワーク解析 ,  隣接関係

分類 (2件)： 通信網  (ND07030A) ,  計算理論  (JB02000A)

引用文献 (19件)：

• Gergely Palla, Imre Derényi, Illés J. Farkas and Tamás Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature 435(7043):814-818, 2005.
• Balázs Adamcsek, Gergely Palla, Illás J. Farkas, Imre Derényi and Tamás Vicsek, “CFinder: Locating cliques and overlapping modules in biological networks,” Bioinformatics 22:1021-1023, 2006.
• Fergal Reid, Aaron McDaid and Neil Hurley, “Percolation computation in complex networks,” In ASONAM, 274-281, 2012.
• Xin Huang, Hong Cheng, Lu Qin, Wentao Tian and Jeffrey Xu Yu, “Querying k-truss community in large and dynamic graphs,” In SIGMOD, 1311-1322, 2014.
• Michael R. Garey and David S. Johnson, “Computers and intractability; A guide to the theory of NP-Completeness”, 1990.

タイトルに関連する用語 (4件)： クリーク ,  コミュニティ ,  オンライン ,  探索