New Algorithm for Mining Maximal Frequent Subgraphs
Linna Li · Jisuanji fangzhen · 2008
Frequent subgraph mining is an active research topic in the data mining community. Because of the inherent computational complexity, mining the complete frequent subgrahps remains to be a challenging task. Furthermore, the number of discovered patterns is often too huge to understand and apply. Mining Maximal Frequent Subgraphs is an alternative to address the problem. Based on the classical Apriori algorithm, Apriori-MaxGraph, which was a maximal subgraph mining algorithm, was proposed. Firstly, to lower the complexity of computing canonical code of adjacency matrix of graph, a new vertex sorting strategy was introduced. Meanwhile, the sorting strategy could speed the matching process of sequences of canonical codes. Secondly, aiming at maximal frequent subgraphs, the process of candidate generation was standardized. Finally, bi-directional searching and pruning were exploited. Thus, the search space was reduced greatly, and the efficiency was improved. Experimental results show the proposed algorithm is efficient.