Coherent closed quasi-clique discovery from large dense graph databases
Coherent closed quasi-clique discovery from large dense graph databases
复制标题
DOI：
10.1145/1150402.1150506
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
Zhiping Zeng;Jianyong Wang;Lizhu Zhou;G. Karypis
中科院分区：
文献类型：
--
作者：
Zhiping Zeng;Jianyong Wang;Lizhu Zhou;G. Karypis
频繁相干子图可以提供关于图数据库内部结构的有价值的知识，从大型密集图数据库中挖掘频繁相干子图已经有了很多应用，并且最近在图挖掘领域受到了相当大的关注。在本文中，我们研究了如何有效地挖掘完整的凝聚闭准集团从大型密集图数据库，这是一个特别具有挑战性的任务，由于向下封闭属性不再成立。通过充分研究拟团的一些性质，提出了几种新的优化技术，可以有效地修剪无用和冗余的子搜索空间。同时，我们设计了一个有效的封闭检查计划，以方便只封闭的准集团的发现。我们还开发了一个一致的闭准团挖掘算法，Cocain 1深入的性能研究表明，Cocain是非常有效的，可扩展的大型密集图数据库。
Frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has been witnessed several applications and received considerable attention in the graph mining community recently. In this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. By fully exploring some properties of quasi-cliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. We also develop a coherent closed quasi-clique mining algorithm, Cocain1 Thorough performance study shows that Cocain is very efficient and scalable for large dense graph databases.