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

Frequent Subgraph Mining Algorithm of Gradually Right-most Extension

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.