An Efficient Frequent Subgraph Mining Algorithm
作者： Li Xian
DOI:
关键词: Sequential Pattern Mining 、 Graph 、 Tree (data structure) 、 Data mining 、 Graph (abstract data type) 、 Subgraph isomorphism problem 、 Computer science 、 Data mining algorithm 、 GSP Algorithm 、 Spanning tree
摘要: With the successful development of frequent item set and sequence mining,the technology data mining is natural to extend its way solve problem structural pattern mining—Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry,biology,computer networks,and World-Wide Web. This paper proposes a new algorithm GraphGen for subgraphs. reduces complexity through extension subtree. For best available,the O(n3·2n),n number edges graph dataset. The O2n·n2.5/logn,which improved O((1/2)n·logn) times than one. Experimental results prove this theoretical analysis.
cnki.com.cn参考文章(15)
A. Inokuchi, Mining generalized substructures from a set of labeled graphs international conference on data mining. pp. 415- 418 ,(2004) , 10.1109/ICDM.2004.10041
Akihiro Inokuchi, Takashi Washio, Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data european conference on principles of data mining and knowledge discovery. pp. 13- 23 ,(2000) , 10.1007/3-540-45372-5_2
Samuel R. Buss, Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization Lecture Notes in Computer Science. pp. 18- 33 ,(1997) , 10.1007/3-540-63385-5_30
R. Shamir, D. Tsur, Faster subtree isomorphism Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems. pp. 126- 131 ,(1997) , 10.1109/ISTCS.1997.595164
R. Jin, C. Wang, D. Polshakov, S. Parthasarathy, G. Agrawal, Discovering frequent topological structures from graph datasets knowledge discovery and data mining. pp. 606- 611 ,(2005) , 10.1145/1081870.1081944
Moti Cohen, Ehud Gudes, Diagonally Subgraphs Pattern Mining Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery - DMKD '04. pp. 51- 58 ,(2004) , 10.1145/1008694.1008702
Rui Yang, Panos Kalnis, Anthony K. H. Tung, Similarity evaluation on tree-structured data Proceedings of the 2005 ACM SIGMOD international conference on Management of data - SIGMOD '05. pp. 754- 765 ,(2005) , 10.1145/1066157.1066243
Xifeng Yan, Jiawei Han, CloseGraph: mining closed frequent graph patterns knowledge discovery and data mining. pp. 286- 295 ,(2003) , 10.1145/956750.956784
J. Huan, W. Wang, J. Prins, Efficient mining of frequent subgraphs in the presence of isomorphism international conference on data mining. pp. 549- 552 ,(2003) , 10.1109/ICDM.2003.1250974
C. Borgelt, M.R. Berthold, Mining molecular fragments: finding relevant substructures of molecules international conference on data mining. pp. 51- 58 ,(2002) , 10.1109/ICDM.2002.1183885