FSP:一种基于图论的频繁结构模式挖掘算法  

FSP:A Graph-based Frequent Structure Pattern Mining Algorithm

作　　者：沙金[1] 纪宁[2] 陈立松[1] 

机构地区：[1]石家庄铁道学院计算机系,河北石家庄050043 [2]华北电力大学电气工程学院,河北保定071003

出　　处：《微电子学与计算机》2007年第2期93-95,98,共4页Microelectronics & Computer

基　　金：河北省自然科学基金项目(E2004000206)

摘　　要：研究在图集中挖掘频繁结构模式的方法,并提出了一种发现频繁结构的新算法FSP(Frequent Structure Pattern Mining),通过在图中建立了一种新的字典顺序,并把每个图映射成唯一的最小DFS编码作为图的规范形式,从而把图转换成一个序列。基于这种字典顺序,FSP算法不需要生成候选,采用深度优先搜索策略挖掘频繁连通子图。试验结果显示,FSP算法在性能上优于以前的算法。Investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called FSP （frequent structure pattern mining）. FSP builds a new lexieographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographie order.FSP adopts the depth-first search strategy to mine frequent connected suhgraphs efficiently, without candidate generation. Our performance study shows that FSP substantially outperforms previous algorithms.

关 键 词：数据挖掘 频繁结构模式 DFS编码 深度优先搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]