首页 | 本学科首页   官方微博 | 高级检索  
     检索      

图模式挖掘中的子图同构算法
引用本文:董安国,高琳,赵建邦.图模式挖掘中的子图同构算法[J].数学的实践与认识,2011,41(13).
作者姓名:董安国  高琳  赵建邦
作者单位:1. 长安大学理学院,陕西西安710064;西安电子科技大学计算机学院,陕西西安710071
2. 西安电子科技大学计算机学院,陕西西安,710071
基金项目:国家自然科学基金(60933009); 陕西省自然科学计划项目(SJ08-ZT15)
摘    要:图模式挖掘问题在Web挖掘、生物信息学、社会关系等众多领域有广泛的应用,它涉及到子图的搜索以及子图的同构问题.这两个问题都具有相当高的计算复杂度,现有的子图同构问题大多采用最小编码算法,但对无标签图特别是对无标签无向图,该算法效率较底,从而子图的同构成为图模式挖掘问题的一个瓶颈.针对无标签图,以代数理论为基础,分别利用度序列和特征值构造了两种子图同构算法,用于对有向图和无向图的同构判别.最后对2个真实生物网络进行了仿真实验,结果表明,算法的效率优于现有算法.

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

Algorithms for Subgraph Isomorphism in Graph Pattern Mining
DONG An-Guo,GAO Lin,ZHAO Jian-bang.Algorithms for Subgraph Isomorphism in Graph Pattern Mining[J].Mathematics in Practice and Theory,2011,41(13).
Authors:DONG An-Guo  GAO Lin  ZHAO Jian-bang
Institution:DONG An-Guo~(1,2),GAO Lin~2,ZHAO Jian-bang~2 (1.School of Science,ChangAn University,Xi'an 710064,China) (2.School of Computer Science and Technology,Xidian University,Xi'an 710071,China)
Abstract: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 g...
Keywords:graph pattern  frequent subgraph  subgraph isomorphism  eigenvalue  
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号