Title :
A Directed Labeled Graph Frequent Pattern Mining Algorithm Based on Minimum Code
Author :
Li, Yuhua ; Lin, Quan ; Zhong, Gang ; Duan, Dongsheng ; Jin, Yanan ; Bi, Wei
Author_Institution :
Coll. of Comput. Sci. & Technol., Huazhong Univ. of Sci. & Technol., Wuhan, China
Abstract :
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 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.
Keywords :
data mining; directed graphs; abstract node code sequence; directed labeled graph frequent pattern mining algorithm; directed weighted graph; financial network; mSpan algorithm; minimum edge code; subgraph mining; undirected unlabeled marked graph; Bismuth; Computer science; Educational institutions; Finance; Research and development; Social network services; Web pages; frequent pattern mining; labeled directed graph; minimum code;
Conference_Titel :
Multimedia and Ubiquitous Engineering, 2009. MUE '09. Third International Conference on
Conference_Location :
Qingdao
Print_ISBN :
978-0-7695-3658-3
DOI :
10.1109/MUE.2009.67