计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (32): 155-158.

• 数据库、信号与信息处理 • 上一篇    下一篇

CoClique:从生物网络中挖掘频繁关联相似模式

雷小刚,尚学群,王 淼   

  1. 西北工业大学 计算机学院,西安 710129
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-11 发布日期:2011-11-11

CoClique:mining frequent correlated-quasi-cliques from biology network

LEI Xiaogang,SHANG Xuequn,WANG Miao   

  1. Department of Computer Science and Engineering,Northwestern Polytechnical University,Xi’an 710129,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-11-11 Published:2011-11-11

摘要: 以前的许多研究已经充证明了挖掘频繁子图是非常有意义的。从单个图中很难挖掘出一些潜在的很有意义的频繁模式,因而应该从多个图中去挖掘频繁模式。以前的研究诸如相似模式(Quasi-Clique)不能解决图中的中心问题。介绍了一个新的概念关联相似模式(Correlated-Quasi-Clique)同时也介绍了一个有效的算法,CoClique,该算法可以解决挖掘过程中所存在的中心问题并且提高挖掘频繁关联相似模式的效率。同时,也提出了一些有效的剪枝策略来缩小搜索空间。在真实数据集上的实验分析结果证明了所提出的算法比以前的算法更有效,结果更好。

关键词: 图挖掘, 中心问题, 相似模式, 关联相似模式

Abstract: Many of the previous studies show convincing arguments that mining frequent subgraphs is especially useful.Many hidden frequent patterns which are very interesting can not be found by mining single graph.Therefore,it needs mine frequent patterns from multiple graphs.Previous studies as quasi-clique have little success with the hub problem.This paper introduces a new conception correlated-quasi-clique and develops a novel algorithm,CoClique,to address the hub problem and improve the efficiency of frequent correlated-quasi-cliques mining.Meanwhile,it exploits several effective techniques to prune the search space.An extensive experimental evaluation on real databases demonstrates that the algorithm outperforms previous methods.

Key words: graph mining, hub problem, quasi-clique, correlated-quasi-clique