Efficient mining of frequent sub graphs
K. Lakshmi, T. Meyappan · 2017
Graph mining is an emerging area of research. Graphs are used for modeling many real world systems, involving related entities. It is useful in many application domains like chemo-informatics, bioinformatics, social network analysis and Web mining. Frequent sub graph mining deals with mining or extracting sub graphs that are present in many graphs from a large collection of graphs. It is found that the way, graphs are represented has a great impact in the efficiency of a graph mining algorithm. In this paper, we propose a new method for graph representation, that can be used to represent both directed and undirected graphs, with unique node labels. Our algorithm incorporates two new ideas, (i) representation of graphs as a list key, value pairs and (ii) use of an optimization parameter, graph threshold - the number of intermediate frequent sub graphs that are to be in the main memory for further mining of frequent sub graphs. We evaluated the performance of our algorithm using synthetic data set and real time Gnutella network dataset. The experimental results show that our algorithm performs better than gSpan and also mine frequent sub graphs from larger size graphs, that cannot be handled by gSpan.