DocumentCode :
673238
Title :
An improved unique canonical labeling for frequent subgraph mining
Author :
Kavitha, D. ; Haritha, D. ; Prasad, V. Kamakshi ; Murthy, J.V.R.
Author_Institution :
PVPSIT, Vijayawada, India
fYear :
2013
fDate :
21-22 Sept. 2013
Firstpage :
1
Lastpage :
6
Abstract :
Frequent subgraph mining is a fundamental task and widely explored in many research application domains such as computational biology, social network analysis, chemical structure analysis and web mining. The problem of frequent subgraph mining is a challenge as the number of possible subgraphs and verifying the isomorphism of the subgraphs is exponential problem. Canonical labeling is a standard approach to handle graph (subgraph) isomorphism that has high complexity and is NP-complete. In this paper we propose a systematic approach and formulate an algorithm to construct canonical label for a graph (subgraph) that uniquely identifies a graph based on the special invariant properties of graphs. Our experimental evaluation shows that this algorithm effectively addresses canonical labeling, isomorphism of graphs and reduces the computational cost.
Keywords :
computational complexity; data mining; graph theory; pattern classification; NP-complete; canonical labeling; computational cost; exponential problem; frequent subgraph mining; special invariant properties; subgraph isomorphism; Algorithm design and analysis; Computational complexity; Computer science; Data mining; Labeling; Symmetric matrices; Graph mining; adjacency matrix; canonical label; frequent subgraph mining; isomorphism;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Advanced Computing Technologies (ICACT), 2013 15th International Conference on
Conference_Location :
Rajampet
Print_ISBN :
978-1-4673-2816-6
Type :
conf
DOI :
10.1109/ICACT.2013.6710534
Filename :
6710534
Link To Document :
بازگشت