作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

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

张宇彤,王思檬,曹佳   

  1. (北京林业大学 信息学院,北京 100083)
  • 收稿日期:2017-02-24 出版日期:2017-09-15 发布日期:2017-09-15
  • 作者简介:张宇彤(1991—),男,硕士研究生,主研方向为复杂网络、数据处理;王思檬,硕士研究生;曹佳,副教授。
  • 基金资助:
    国家自然科学基金“面向中药方剂信息的不可拆原子组合信息及其层次聚类分析研究”(61602042)。

Isomorphic Subgraph Search Algorithm Based on Neighborhood Equivalence Class

ZHANG Yutong,WANG Simeng,CAO Jia   

  1. (School of Information Science and Technology,Beijing Forestry University,Beijing 100083,China)
  • Received:2017-02-24 Online:2017-09-15 Published:2017-09-15

摘要: 节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于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)

中图分类号: