A Directed Labeled Graph Frequent Pattern Mining Algorithm based on Minimum Code

摘要

Most of existing frequent subgraph mining algorithms are used to deal with undirected unlabeled marked graph. A few of them aim at directed graph or labeled graph because it is very complex to consider that. But in the real world, a lot of connections have directions and labels, so directed labeled graph mining is more meaningful. Now we are analyzing a financial network which can be modeled by a directed weighted graph. We are interested in the patterns which are frequent. The graph pattern means a uniform expression of graphs which has different marked nodes but same structure. In our application we consider direction and weight as part of the pattern. It's different from subgraph because subgraph mining consider the labels of nodes. This paper proposes a new algorithm mSpan for directed labeled graph frequent pattern mining. Based on FP-growth, the algorithm gets a minimum edge code and an abstract node code sequence to identify a directed graph pattern uniquely through minimum extension. It can solve the graph pattern isomorphic problem and the redundant extension problem. The experiment shows that mSpan can mine all frequent directed, labeled graph patterns.