FP-GraphMiner - A Fast Frequent Pattern Mining Algorithm for Network Graphs

R Vijayalakshmi, R Nadarajan, John Roddick, M Thilaga, P Nirmala

    Research output: Contribution to journalArticlepeer-review

    23 Citations (Scopus)

    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 fre- quent 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 occur- rence. A series of experiments performed on sparse, dense and complete graph data sets and a comparison with MARGIN, gSpan and FSMA us- ing real time network data sets confirm the efficiency of the proposed FP-GraphMiner algorithm.

    Original languageEnglish
    Pages (from-to)753-776
    Number of pages24
    JournalJournal of Graph Algorithms and Applications
    Volume15
    Issue number6
    DOIs
    Publication statusPublished - 2011

    Keywords

    • Frequent pattern mining
    • Frequent subgraph
    • Graph database
    • Graph mining
    • Maximal frequent subgraph
    • Maximum common subgraph

    Fingerprint Dive into the research topics of 'FP-GraphMiner - A Fast Frequent Pattern Mining Algorithm for Network Graphs'. Together they form a unique fingerprint.

    Cite this