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

Algorithms for Subgraph Isomorphism in Graph Pattern Mining

图模式挖掘问题在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.