MH-DAGMiner: maximal hierarchical sub-DAG mining in directed weighted networks

摘要

With the easy availability of network data, there is an increasing need for extracting the compact and meaningful directed acyclic graph (DAG) patterns from network databases. There exists no specific method of sub-DAG pattern mining from the network databases with cyclic graphs. This paper presents a novel method, MH-DAGMiner, for mining maximal hierarchical sub-DAG patterns from a directed and weighted network database. To avoid the exhaustive steps of candidate generation, frequency counting and non-maximal patterns pruning, we propose a novel and effective FP-DAG structure based on edge grouping. We propose the optimum branching method to identify the vertex hierarchy within each maximal edge group generated from FP-DAG, and discover the maximal hierarchical sub-DAG patterns. The effectiveness of MH-DAGMiner is tested using several real-world network datasets and synthetic graph datasets. We analyzed the quality of MH-DAGMiner in comparison with a Naive-DAGMiner method which mines DAG patterns from a preprocessed cyclic graph (DAG) database. MH-DAGMiner is found to be more effective than Naive-DAGMiner with lower average information loss. MH-DAGMiner is also found to be more effective than the state-of-the-art benchmarking algorithms such as gSpan, FP-GraphMiner, and MFSH-TreeMiner where maximal hierarchical DAG patterns are identified with a post-processing step.