Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (10): 113-117.

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Improved method based on Apriori-based frequent sub-graph mining algorithm

CHEN Lining,LUO Ke   

  1. Institute of Computer and Communication Engineering,Changsha University of Sciences and Technology,Changsha 410076,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-04-01 Published:2011-04-01


陈立宁,罗 可   

  1. 长沙理工大学 计算机与通信工程学院,长沙 410076

Abstract: AGM(Apriori-based Graph Mining) algorithm is the first one to put the Apriori idea into the use of frequent sub-graph mining.This algorithm is simple and based on recursion statistics.But graph data set is very large and sub-graph isomorphism problem is available,when candidate subgraphs are generated and so many redundant sub-graphs would be generated,which makes the high cost in computing time.An improved method based on AGM is proposed to get the reduction of redundant sub-graphs and make the new algorithm more efficient in computing time,compared to AGM algorithm.This paper examines the computing time for various minimum support,the result of which proves that the improved algorithm cuts down the computing time,compared to AGM algorithm,improving the efficiency of frequent sub-graph mining.

Key words: frequent sub-graph mining, Apriori-based Graph Mining(AGM) algorithm, sub-graph isomorphism

摘要: AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。

关键词: 频繁子图挖掘, AGM算法, 子图同构