Research On Algorithms For Maximal Frequent Subgraph Mining

Data mining is a process of through analysis the large number of information to found meaningful relationships and trends and patterns. Currently, as a branch of data mining, graph mining's research tasks include frequent subgraph and maximal frequent subgraph mining. Compared with frequent subgraph mining the maximal frequent subgraph mining did not lose information and get fewer results these contribute to understanding and application the mining results. In the current algorithm exists a problem that is subgraph isomorphism. This is also the focus of this paper:Firstly, the efficiency of count the canonical code is very low, in this paper based on the principle of vertex unchanged proposed a new method for count canonical code to improve the efficieny of it. This paper proposed a new method that is using directed acyclic graph (DAG) to count the support. There are some relationships between the vertices, in this paper we using these relationships to judge a graph whether exist a super graph in the graph set. Then count the support of this graph.Secondly, contrary to the problem of subgraph isomorphism when judge the two k-frequent subgraph whether have the same k-1 subgraph this paper proposed algorithm FSG-MaxGraph for mining maximal frequent subgraph. This algorithm proposed two theorems and using these theorems to judge before delete one edge this can reduce the times of subgraph isomorphism.Thirdly, contrary to the problem of mining difficulty is very big this paper proposed algorithm Top-Down. In this algorithm we through change the policy of mining to achieve an objective of avoid mining all the frequent subgraph.Lastly, in this paper in order to validate the efficiency and correctness of algorithm FSG-MaxGraph and Top-Down we do a lot of experiments. We combine with the theory and experiment to judge in which instance these algorithm have higher efficiency.