一种高效频繁子图挖掘算法2007,181024692480.pdf

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software, Vol.18, No.10, October 2007, pp.2469−2480 DOI: 10. 1360/jos1 82469 Tel/Fax : +86-10 © 2007 by Journal of Software. All rights reserved. ∗ 一种高效频繁子图挖掘算法 + 李先通, 李建中 , 高 宏 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) An Efficient Frequent Subgraph Mining Algorithm + LI Xian-Tong, LI Jiang-Zhong , GAO Hong (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) + Corresponding author: Phn: +86-451 E-mail: lijzh@, Li XT, Li JZ, Gao H. An efficient frequent subgraph mining algorithm. Journal of Softwar e, 2007,18(10) : 2469−2480. /1000-9825/18/2469.htm Abstract: With the successful development of frequent item set and frequent sequence mining, the technology of data mining is natural to extend its way to solve the problem of structural pattern mining —Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry, biology, computer networks, and World-Wide Web . In this paper we propose a new algorithm GraphGen for mining frequent subgraphs . GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm before, the 3 n complexity is O(n ·2 ), n is the number of frequent edges in a graph dataset. The complexity of GraphGen is ⎛ n2.5 ⎞ O⎜ 2n ⋅ ⎟, which is improved O( n ⋅log n) times than the best one. Experiment results prove this theoretical ⎜ ⎟ ⎝ log n ⎠ an