基于环分布的频繁子图挖掘算法  

A Ring Distribution Based Algorithm for Finding Frequent Subgraphs

作　　者：董安国[1,2] 高琳[2] 邱在秦[3] 常安定[1] 赵建邦[2] 

机构地区：[1]长安大学理学院,西安710064 [2]西安电子科技大学计算机学院,西安710071 [3]西安石油大学理学院,西安710065

出　　处：《工程数学学报》2009年第6期977-984,共8页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(60574039);陕西省自然科学计划项目(SJ08-ZT15);长安大学科技发展基金(07J04)

摘　　要：频繁子图挖掘主要涉及到子图搜索和子图同构问题。对子图搜索问题,本文提出了环分布的概念,并构造了基于环分布的子图搜索算法;对子图同构问题,本文利用度序列和特征值构造了两种算法,分别用于对有向图和无向图的同构判别。利用同构算法对搜索出的子图进行同构分类,根据分类结果得到频繁子图。实验结果表明,本算法的效率优于现有算法。Frequent subgraph mining includes subgraph search and isomorphism problems. For the subgraph searching, we propose the definition of a ring distribution and provide a novel subgraph search algorithm based on the ring distribution. Furthermore, by using the degree sequence and eigenvalue, we present two algorithms for subgraph isomorphism in directed and undirected graphs, respectively. Finally, we experimentally evaluate the performance of our algorithms by using real networks. The simulation results show that our algorithm is more effective than existing algorithms.

关 键 词：频繁子图 子图搜索 子图同构 特征值 度序列 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论] Q811.4[自动化与计算机技术—计算机科学与技术]