• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2013, Vol. 35 ›› Issue (4): 157-162.

• 论文 • 上一篇    下一篇

一种新的自顶向下挖掘最大频繁子图的算法

陈晓,刘凤春,李建晶,张准   

  1. (河北联合大学迁安学院, 河北 迁安 064400)
  • 收稿日期:2011-11-24 修回日期:2012-05-03 出版日期:2013-04-25 发布日期:2013-04-25
  • 基金资助:

    国家自然科学基金资助项目(60673136);河北省教育厅2009年自然科学研究指令项目(2009101);河北省应用基础研究计划重点基础研究资助项目(10963527D);河北省自然基金资助项目(F2012209019)

A novel top-down algorithm of
mining maximal frequent subgraph   

CHEN Xiao,LIU Fengchun,LI Jianjing,ZHANG Zhun   

  1.  (Qian’an College,Hebei United University,Qian’an 064400,China)
  • Received:2011-11-24 Revised:2012-05-03 Online:2013-04-25 Published:2013-04-25

摘要:

传统挖掘频繁子图的方法,不论是基于Aprior的还是基于FP增长的,均采用自底向上的挖掘方法,该方法需要多次迭代和判断子图同构,大大降低了算法的效率。为解决传统频繁子图挖掘方法中存在的问题,提出一种新的基于自顶向下的挖掘最大频繁子图的算法。首先定义标号图的属性信息,并基于标号图属性信息定义进而提出判断图同构的必要条件,从而减少同构的判断次数,提高算法的效率;其次,在挖掘过程中利用图的对称性质标识对称的顶点,从而减少不必要的删除操作及冗余图的存储;最后,实验证明,该算法优于现有最大频繁子图挖掘算法,且不丢失任何模式和有用信息。

关键词: 最大频繁子图, 自顶向下, 图同构, 对称性, 树结构

Abstract:

The traditional Aprior or FPgrowth based methods of mining frequent subgraph are bottomup methods, which necessitates multiple iterations and subgraph isomorphism determination, thus reducing the efficiency of the algorithm. To solve the existing problems of the traditional methods of mining frequent subgraph, a novel topdown algorithm of mining maximal frequent subgraph was proposed in this paper. Firstly, the attributed information of labeled graph is defined, and the prerequisites for isomorphism judgment are specified on the basis of the preceding definition, hence reducing the number of judgment isomorphism and improving the efficiency of the algorithm. Secondly, the symmetric vertexes are labeled according to the symmetry of graph in the process of mining, hence decreasing the unnecessary deletions and the redundant storage of graphs. Finally, the algorithm, without losing any patterns and useful information, is proved in the experiments to be superior to the existing maximal frequent subgraph mining algorithms.        

Key words: maximal frequent subgraph;topdown;graph isomorphism;symmetry;tree structure