Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
FP-GraphMiner-A Fast Frequent Pattern Mining Algorithm for Network Graphs
R. Vijayalakshmi, R. Nadarajan, John F. Roddick, M. Thilaga, and P. Nirmala
Vol. 15, no. 6, pp. 753-776, 2011. Regular paper.
Abstract In recent years, graph representations have been used extensively for modelling complicated structural information, such as circuits, images, molecular structures, biological networks, weblogs, XML documents and so on. As a result, frequent subgraph mining has become an important subfield of graph mining. This paper presents a novel Frequent Pattern Graph Mining algorithm, FP-GraphMiner, that compactly represents a set of network graphs as a Frequent Pattern Graph (or FP-Graph). This graph can be used to efficiently mine frequent subgraphs including maximal frequent subgraphs and maximum common subgraphs. The algorithm is space and time efficient requiring just one scan of the graph database for the construction of the FP-Graph, and the search space is significantly reduced by clustering the subgraphs based on their frequency of occurrence. A series of experiments performed on sparse, dense and complete graph data sets and a comparison with MARGIN, gSpan and FSMA using real time network data sets confirm the efficiency of the proposed FP-GraphMiner algorithm. Keywords: frequent pattern mining, frequent subgraph, graph database, graph mining, maximal frequent subgraph, maximum common subgraph.
Submitted: February 2011.
Reviewed: May 2011.
Revised: May 2011.
Reviewed: August 2011.
Revised: August 2011.
Accepted: October 2011.
Final: October 2011.
Published: November 2011.
Communicated by Giuseppe Liotta