Study On Steady Frequent Subgraph Mining Algorithm

Frequent subgraph mining algorithm is one of the important problems in graph theory research and algorithm design,which is aimed to find the subgraph structure frequently appearing in the graph.Frequent subgraph mining has been widely used in many fields,such as social network,biomedicine,information network,etc.With the arrival of the era of big data in recent years,the data size increases and the meaningful information in the data mining is becoming very important.Because the frequent subgraph mining algorithm can dig out frequent subgraph of the data structure,the research and production brought huge benefits.At present,due to frequent changes of graph data,frequent subgraph mining algorithms based on static graphs are no longer applicable.Therefore,frequent subgraph mining algorithms for dynamic graphs have emerged.In this paper,a variety of frequent subgraph mining algorithms are studied in this paper,and it is found that the existing frequent subgraph mining algorithms are generally oriented to static graphs.These algorithms need to scan the database multiple times,and the algorithm can not be applied to the highly requirement of running time and space.However,for large-scale dynamic graph,the algorithm is no longer applicable to time and space complexity.Aiming at this,this paper proposes a stable frequent subgraph mining algorithm based on pattern growth.The algorithm introduces the sliding window technology,which used to save the every moment figure structure,when the sliding window is full of graph structure,mining the frequent subgraph from the graph structure in the window.The algorithm will generate a DS table for the graph structure in the window.Constructing a FP-tree based on the DS table,and then mining all the frequent itemsets.For the problem of frequent itemsets pruning,this paper proposes a frequent itemsets pruning algorithm based on vertex,pruning off the unconnected frequent itemsets and getting frequent subgraphs.In this paper,a method based on connectivity density is proposed to determine the stability of frequent subgraphs.The method takes the stability of the graph is embedded into the pruning process of frequent subgraph mining,and used the stability of the graph to determine the matching degree of the graphs.Because if the frequent subgraphs are excavated in each window,the connected density will not change,resulting the frequent subgraph will not change in the short time.By comparing with other algorithms,this paper proves the validity of the proposed algorithm.