基于邻域等价类的同构子图搜索算法  

Isomorphic Subgraph Search Algorithm Based on Neighborhood Equivalence Class

作　　者：张宇彤 王思檬 曹佳[1] 

机构地区：[1]北京林业大学信息学院,北京100083

出　　处：《计算机工程》2017年第9期7-11,共5页Computer Engineering

基　　金：国家自然科学基金"面向中药方剂信息的不可拆原子组合信息及其层次聚类分析研究"(61602042)

摘　　要：节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于Turbo_(ISO)算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,Turbo_(ISO)相比,NEC-COMB可有效提高搜索效率,优化去重效果。Node heterogeneous graph is often used as a data model for complex networks. Isomorphic subgraph search is an important problem in heterogeneous graph mining,but existing algorithms have shortcomings in subgraph removal,which reduces the efficiency of search. Aiming at this problem,based on the concept of Neighborhood Equivalence Class（ NEC） in TurboISO algorithm,this paper proposes an isomorphic subgraph search algorithm,named NEC-COMB. It consists of four parts： the preparation,the node order determination,the subgraph isomorphism matching and the subgraph extraction. In the subgraph isomorphism matching part,f or the nodes in NEC,it uses combination strategy to avoid repeatedly matching the node with equivalent structure only once. Experimental results show that,compared with the classical isomorphic subgraph search algorithms such as VF2,GraphQL and TurboISO,NEC-COMB can improve the search efficiency and optimize the removal effect.

关 键 词：子图同构 子图搜索 异质图 同构匹配 邻域等价类 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]