计算机工程2017，Vol.43Issue(9)：7-11,5.DOI:10.3969/j.issn.1000-3428.2017.09.002
基于邻域等价类的同构子图搜索算法
Isomorphic Subgraph Search Algorithm Based on Neighborhood Equivalence Class
摘要
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 TurboIsoalgorithm,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)分类
信息技术与安全科学引用本文复制引用
张宇彤,王思檬,曹佳..基于邻域等价类的同构子图搜索算法[J].计算机工程,2017,43(9):7-11,5.基金项目
国家自然科学基金“面向中药方剂信息的不可拆原子组合信息及其层次聚类分析研究”(61602042). （61602042）
