图模式挖掘中的子图同构算法  

Algorithms for Subgraph Isomorphism in Graph Pattern Mining

作　　者：董安国[1,2] 高琳[2] 赵建邦[2] 

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

出　　处：《数学的实践与认识》2011年第13期105-112,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金(60933009);陕西省自然科学计划项目(SJ08-ZT15)

摘　　要：图模式挖掘问题在Web挖掘、生物信息学、社会关系等众多领域有广泛的应用,它涉及到子图的搜索以及子图的同构问题.这两个问题都具有相当高的计算复杂度,现有的子图同构问题大多采用最小编码算法,但对无标签图特别是对无标签无向图,该算法效率较底,从而子图的同构成为图模式挖掘问题的一个瓶颈.针对无标签图,以代数理论为基础,分别利用度序列和特征值构造了两种子图同构算法,用于对有向图和无向图的同构判别.最后对2个真实生物网络进行了仿真实验,结果表明,算法的效率优于现有算法.Graph pattern mining has a wide range of applications in different domains, such as web mining, bioinformatics, and social relationship, which involved subgraph searching and isomorphism. Both problems all have high complexity. The existing approaches to subgraph isomorphism are almost based on minimum coding. The efficiency of the approaches is lower in unlabeled graphs, especially in undirected unlabeled graphs. Therefore, subgraph isomorphism is the bottle-neck in graph pattern mining. In this paper, for unlabeled graph,we present two novel algorithms for subgraph isomorphism of directed and undirected graph. The algorithms are based on algebra theory by making use of degree sequence of a vertex and eigenvalue of adjacency matrix. We experimentally evaluate the performance of our algorithms using two real networks. The simulation results show that our algorithm is effective compared with the existing algorithm.

关 键 词：图模式 频繁子图 子图同构 特征值 

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