A Directed Labeled Graph Frequent Pattern Mining Algorithm based on Minimum Code
出版社：
- 会议名称：The 3rd International Conference on Multimedia and Ubiquitous Engineering (MUE 2009)
- 举办地点：Qingdao,China
- 举办日期：JUNE 2009
- 页数：353-359
摘要内容：
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. But in the real world ,a lot of connections have direction and label,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 indentify 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.
关键词：
- frequent pattern mining； labeled directed graph； minimum code
