Efficient frequent subgraph mining algorithm

被引：9

作者：

Li, Xian-Tong ^{[1
]}

Li, Jian-Zhong ^{[1
]}

Gao, Hong ^{[1
]}

机构：

[1] School of Computer Science and Technology, Harbin Institute of Technology

来源：

Ruan Jian Xue Bao/Journal of Software | 2007年 / 18卷 / 10期

关键词：

Frequent pattern mining; Frequent subgraph; Spanning tree; Subgraph isomorphism; Subtree isomorphism;

D O I：

10.1360/jos182469

中图分类号：

学科分类号：

摘要：

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. This paper proposes a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm available, the complexity is O(n3·2n), n is the number of frequent edges in a graph dataset. The complexity of GraphGen is O(2n·(n2.5/logn)), which is improved O(√n·logn) times than the best one. Experimental results prove this theoretical analysis.

引用

页码：2469 / 2480

页数：11

共 17 条

[1]

Borgelt C., Berhold M.R., Mining molecular fragments: Finding relevant substructures of molecules, Proc. of the ICDM 2002, (2002)

[2]

Holder L.B., Cook D.J., Djoko S., Substructures discovery in the subdue system, Proc. of the AAAI'94 Workshop Knowledge Discovery in Databases, pp. 169-180, (1994)

[3]

Inokuchi A., Washio T., Okada T., Motoda H., Applying algebraic mining method of graph substructures to mutageniesis data analysis, Proc. of the PAKDD, (2000)

[4]

Inokuchi A., Washio T., Okada T., An apriori-based algorithm for mining frequent substructures from graph data, Proc. of the PKDD 2000, pp. 13-23, (2000)

[5]

Kuramochi M., Karypis G., Frequent subgraph discovery, Proc. of the ICDM 2001, (2001)

[6]

Yan Y., Han J., gSpan: Graph-Based substructure pattern mining, Proc. of the 2002 Int'l Conf. on Data Mining (ICDM 2002), (2002)

[7]

Washio T., Motoda H., State of the art of graph-based data mining, Proc. of the SIGKDD 2003, (2003)

[8]

Yan X., Han J., CloseGraph: Mining closed frequent graph patterns, Proc. of the 9th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD2003), (2003)

[9]

Han J., Wang W., Prins J., Efficient mining of frequent subgraphs in the presence of isomorphism, Proc. of the IEEE Int'l Conf. on Data Mining (ICDM 2003), (2003)

[10]

Jin R., Wang C., Polshakov D., Parthasarathy S., Agrawal G., Discovering frequent topological structures from graph datasets, Proc. of the KDD 2005, pp. 606-611, (2005)

← 1 2 →