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 条

[11]

Inokuchi A., Mining generalized substructures from a set of labeled graphs, Proc. of the 4th IEEE Int'l Conf. on Data Mining (ICDM 2004), pp. 415-418, (2004)

[12]

Cohen M., Gudes E., Diagonally subgraphs pattern mining, Proc. of the DMKD 2004, (2004)

[13]

Shamir R., Tsur D., Faster subtree isomorphism, Proc. of the 5th Israel Symp. Theory of Computing and Systems. IEEE, pp. 126-131, (1997)

[14]

Ueda N., Aoki-Kinoshita K.F., Yamaguchi A., Akutsu T., Mamitsuka H., A probabilistic model for mining labeled ordered trees: Capturing patterns in carbohydrate sugar chains, IEEE Trans. on Knowledge and Data Engineering, 17, 8, pp. 1051-1064, (2005)

[15]

Buss S.R., Alogtime algorithms for tree isomorphism, comparison and canonization, Computational Logic and Proof Theory, Proc. of the 5th G-del Colloquium'97, pp. 18-33, (1997)

[16]

Yang R., Kalnis P., Tung A.K.H., Similarity evaluation on tree-structured data, Proc. of the SIGMOD 2005, (2005)

[17]

Ruckert U., Kramer S., Frequent free tree discovery in graph data, Symp. on Applied Computing archive, Proc. of the 2004 ACM Symp. on Applied Computing, pp. 564-570, (2004)

← 1 2 →