摘要： 节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于TurboISO算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,TurboISO相比,NEC-COMB可有效提高搜索效率,优化去重效果。

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

Abstract: 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,for 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.

Key words: subgraph isomorphism, subgraph search, heterogeneous graph, isomorphism matching, Neighborhood Equivalence Class(NEC)

中图分类号: 

• TP391.41