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

A novel top-down algorithm of mining maximal frequent subgraph

作　　者：陈晓[1] 刘凤春[1] 李建晶[1] 张准[1] 

机构地区：[1]河北联合大学迁安学院,河北迁安064400

出　　处：《计算机工程与科学》2013年第4期157-162,共6页Computer Engineering & Science

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

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]