Cited By
View all- Nguyen LLe NNguyen HPham TVo B(2022)Frequent Closed Subgraph Mining: A Multi-thread ApproachIntelligent Information and Database Systems10.1007/978-3-031-21743-2_6(64-77)Online publication date: 28-Nov-2022
An Optimization of Closed Frequent Subgraph Mining Algorithm
Pages 3 - 15
Abstract
Graph mining isamajor area of interest within the field of data mining in recent years. Akey aspect of graph mining is frequent subgraph mining. Central to the entire discipline of frequent subgraph mining is the concept of subgraph isomorphism. One major issue in early subgraph isomorphism research concerns computational complexity. Normally, the subgraph isomorphism problem is NP-complete. Previous studies of frequent subgraph mining have not solved NP-complete problem in the subgraph isomorphism. In this paper, we proposeanew algorithm which can deal with this problem. The proposed algorithm can solve the subgraph isomorphism in polynomial time in some settings. Moreover, the new algorithm is proved theoretically more effective than previous studies in closed frequent subgraph mining.
References
[1]
1. Demetrovics, J., V. D. Thi, N. L. Giang. On Finding All Reducts of Consistent Decision Tables. - Cybernetics and Information Technologies, Vol. 14, 2014, No 4, pp. 3-10.
[2]
2. Eppstein, D. Subgraph Isomorphism in Planar Graphs and Related Problems. - In SODA, Vol. 95, 1995, pp. 632-640.
[3]
3. Garey, M. R., D. S. Johnso n. Computers and Intractability: An Introduction to the Theory of Np-Completeness. San Francisco, 1979.
[4]
4. Han, J., H. Cheng, D. Xin, X. Yan. Frequent Pattern Mining: Current Status and Future Directions. - Data Mining and Knowledge Discovery, Vol. 15, 2007, No 1, pp. 55-86.
[5]
5. Hopcroft, J. E., R. E. Tarjan. Isomorphism of Planar Graphs. - In: Complexity of Computer Computations. Springer, 1972, pp. 131-152.
[6]
6. Huan J., W. Wang, J. Prins. Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism. - In: 3rd IEEE International Conference on Data Mining, 2003 (ICDM’2003), IEEE, 2003, pp. 549-552.
[7]
7. Huan, J., W. Wang, J. Prins, J. Yang. Spin: Mining Maximal Frequent Subgraphs from Graph Databases. - In: Proc. of 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2004, pp. 581-586.
[8]
8. Inokuchi, A., T. Washio, H. Motoda. An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data. - In: European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2000, pp. 13-23.
[9]
9. Kuramochi M., G. Karypi s. Frequent Subgraph Discovery. - In: Proc. of IEEE International Conference on Data Mining, 2001. ICDM 2001, IEEE, 2001, pp. 313-320.
[10]
10. Mc Kay, B. D., et al. Practical Graph Isomorphism. Department of Computer Science, Vanderbilt University Tennessee, US, 1981.
[11]
11. Read, R. C., D. G. Cornei l. The Graph Isomorphism Disease. - Journal of Graph Theory, Vol. 1, 1977, No 4, pp. 339-363.
[12]
12. Savage, J. E. Models of Computation. Exploring the Power of Computing, 1998.
[13]
13. Thi, V. D., N. L. Giang. A Method to Constructa Decision Table froma Relation Scheme. - Cybernetics and Information Technologies, Vol. 11, 2011, No 3, pp. 32-41.
[14]
14. Thomas, L. T., S. R. Valluri, K. Karlapalem. Margin: Maximal Frequent Subgraph Mining. - ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 4, 2010, No 3, pp. 10.
[15]
15. Ullmann, J. R. An Algorithm for Subgraph Isomorphism. - Journal of the ACM (JACM), Vol. 23, 1976, No 1, pp. 31-42.
[16]
16. Washio, T., H. Motoda. State of the Art of Graph-Based Data Mining. - ACM Sigkdd Explorations Newsletter, Vol. 5, 2003, No 1, pp. 59-68.
[17]
17. Yan, X., J. Han. GSPAN: Graph-Based Substructure Pattern Mining. - In: Proc. of 2002 IEEE International Conference on Data Mining, 2002. ICDM 2003, IEEE, 2002, pp. 721-724.
[18]
18. Yan, X., J. Han. Closegraph: Mining Closed Frequent Graph Patterns. - In: Proc. of 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2003, pp. 286-295.
Index Terms
- An Optimization of Closed Frequent Subgraph Mining Algorithm
Index terms have been assigned to the content through auto-classification.
Recommendations
Frequent Subgraph Mining from Streams of Uncertain Data
C3S2E '15: Proceedings of the Eighth International C* Conference on Computer Science & Software EngineeringIn the current era of Big data, high volumes of high-value data---such as social network data---can be generated at a high velocity. The quality and accuracy of these data depend on their veracity: uncertainty of the data. A collection of these ...
Closed frequent similar pattern mining
The concept of closed frequent similar pattern mining is introduced.Several lemmas to prune the search space are introduced and proved.A novel closed frequent similar pattern mining algorithm (CFSP-Miner), is proposed.CFSP-Miner is more efficient than ...
Graph-Based Bioinformatics Mining Research and Application
KAM '11: Proceedings of the 2011 Fourth International Symposium on Knowledge Acquisition and ModelingIn the biological technology domain, the biologist discovered frequent sub graph mining may reduce the price of structure match experiment in the protein gene structure match experiment. Molecular model can be abstracted as a set of graph, it usually ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© by J. Demetrovics.
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.
Publisher
Walter de Gruyter GmbH
Berlin, Germany
Publication History
Published: 01 March 2017
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025
Other Metrics
Citations
Cited By
View all- Nguyen LLe NNguyen HPham TVo B(2022)Frequent Closed Subgraph Mining: A Multi-thread ApproachIntelligent Information and Database Systems10.1007/978-3-031-21743-2_6(64-77)Online publication date: 28-Nov-2022