Out-of-core coherent closed quasi-clique mining from large dense graph databases
Out-of-core coherent closed quasi-clique mining from large dense graph databases
复制标题
从大型密集图数据库中进行核外相干封闭准集团挖掘
DOI：
10.1145/1242524.1242530
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Lizhu Zhou
中科院分区：
文献类型：
--
作者：
Jianyong Wang;Zhiping Zeng;George Karypis;Lizhu Zhou
由于图能够表示不同对象之间更一般、更复杂的关系，图挖掘在数据挖掘中发挥了重要的作用，引起了数据挖掘界越来越多的关注。此外，频繁相干子图可以提供关于图数据库内部结构的有价值的知识，而从大型密集图数据库中挖掘频繁出现的相干子图已经有了一些应用，近年来在图挖掘领域受到了相当大的关注。在这篇文章中，我们研究了如何有效地从大型密集图数据库中挖掘出凝聚闭拟团的完全集，这是一个特别具有挑战性的任务，因为向下闭包性质已经不再成立。通过充分研究拟团的一些性质，我们提出了几种新的优化技术，可以有效地修剪无希望和冗余子搜索空间。同时，我们设计了一个高效的闭包检查方案，以便于仅发现闭合的准团。由于大型数据库不能存放在内存中，我们还设计了一种具有高效索引结构的核外解决方案，用于从大型密集图数据库中挖掘一致性闭合准团。我们称之为可卡因*。深入的性能研究表明，Cocain*对于大型密集图形数据库是非常高效和可伸缩的。
Due to the ability of graphs to represent more generic and more complicated relationships among different objects, graph mining has played a significant role in data mining, attracting increasing attention in the data mining community. In addition, 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 witnessed several applications and received considerable attention in the graph mining community recently. In this article, 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 fact that 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 subsearch spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of closed quasi-cliques only. Since large databases cannot be held in main memory, we also design an out-of-core solution with efficient index structures for mining coherent closed quasi-cliques from large dense graph databases. We call this Cocain*. Thorough performance study shows that Cocain* is very efficient and scalable for large dense graph databases.
登录
查看更多内容
DOI：
10.1145/1007568.1007607
发表时间：
2004-06
期刊：
--
影响因子：
--
作者：
Xifeng Yan;Philip S. Yu;Jiawei Han
通讯作者：
Xifeng Yan;Philip S. Yu;Jiawei Han
DOI：
10.1145/1150402.1150506
发表时间：
2006-08
期刊：
--
影响因子：
--
作者：
Zhiping Zeng;Jianyong Wang;Lizhu Zhou;G. Karypis
通讯作者：
Zhiping Zeng;Jianyong Wang;Lizhu Zhou;G. Karypis
DOI：
10.1145/1014052.1014088
发表时间：
2004-08
期刊：
Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining
影响因子：
--
作者：
Chen Wang;Wei Wang;J. Pei;Yongtai Zhu;Baile Shi
通讯作者：
Chen Wang;Wei Wang;J. Pei;Yongtai Zhu;Baile Shi
DOI：
10.1145/191246.191314
发表时间：
1994-11
期刊：
--
影响因子：
--
作者：
M. Klemettinen;H. Mannila;Pirjo Ronkainen;Hannu (TT) Toivonen;A. I. Verkamo
通讯作者：
M. Klemettinen;H. Mannila;Pirjo Ronkainen;Hannu (TT) Toivonen;A. I. Verkamo
DOI：
10.1145/1150402.1150416
发表时间：
2006-08
期刊：
--
影响因子：
--
作者：
G. Buehrer;S. Parthasarathy;A. Ghoting
通讯作者：
G. Buehrer;S. Parthasarathy;A. Ghoting