一种多到一子图同构检测方法  

Approach for Efficient Subgraph Isomorphism Testing for Multiple Graphs

作　　者：张硕[1] 李建中[1] 高宏[1] 邹兆年[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《软件学报》2010年第3期401-414,共14页Journal of Software

基　　金：国家重点基础研究发展计划(973)No.2006CB303005;国家自然科学基金Nos.60533110;60773063;新世纪优秀人才支持计划No.NCET-05-0333~~

摘　　要：提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.This paper proposes an approach for subgraph isomorphism testing from a set of priori given small graphs to a large graph issued on-line. In order to reduce the computational cost, based on DFS Code, an elaborate organization of a set of graphs is presented, and a look-ahead-pruning based algorithm of subgraph isomorphism testing from multiple small graphs to a large graph is proposed. Moreover, an index technique based on data mining is introduced. Analytical and experimental results show the on-line computational cost of the proposed method is much less than the state-of-the-art method and it is about one order of magnitude faster than the existing method with more than one order of magnitude less off-line construction time.

关 键 词：图匹配 子图同构 预处理 图索引 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]