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

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