逐步最右扩展的频繁子图挖掘算法  

Frequent Subgraph Mining Algorithm of Gradually Right-most Extension

作　　者：张俊峰[1] 周焱[1] 薛冰[1] 刘荣辉[1,2] 

机构地区：[1]河南城建学院计算机科学与工程系,河南平顶山467036 [2]东华大学管理学院,上海200051

出　　处：《河南科技大学学报（自然科学版）》2011年第1期41-44,48,共5页Journal of Henan University of Science And Technology:Natural Science

基　　金：国家自然科学基金项目(70971020);河南省重点科技攻关项目(092102210251)

摘　　要：gSpan算法是一种高效的频繁子图挖掘算法,它通过最右扩展图的标准编码得到图集中的所有频繁子图,但它需要通过子图同构判断来计算支持度,由于子图同构问题是NP完全问题,其计算比较复杂。针对上述问题提出一种优化的算法IgSpan,通过改进的ADI++存储结构将图的最右扩展和支持度的计算相结合,避免直接的子图同构判断,经实验验证改进后的算法提高了频繁子图挖掘的效率。The gSpan algorithm has a better efficiency in the implementation as an efficient algorithm for frequent subgraph mining.It uses right-most extension to mine frequent subgraph.But it calculates the support of subgraph by subgraph isomorphism which is a NP complete problem and the calculation is complex.A new algorithm IgSpan was proposed,which could avoid subgraph isomorphism by using improved ADI++ storage structure to combine the expanded subgraph with the calculation of support.Experiments show that the algorithm improves the efficiency of frequent graph mining.

关 键 词：频繁子图 子图同构 标准编码 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]