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

发布时间：2018-03-11 13:26

  本文选题：子图同构　切入点：子图搜索　出处：《计算机工程》2017年09期 　论文类型：期刊论文

【摘要】：节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于Turbo_(ISO)算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,Turbo_(ISO)相比,NEC-COMB可有效提高搜索效率,优化去重效果。
[Abstract]:Node heterogeneous graph is often used as the data model of complex network. Isomorphism subgraph search is an important problem in heterogeneous graph mining process. Based on the concept of neighborhood equivalence class (NECs) in TurboShop ISO algorithm, an isomorphism subgraph search algorithm, NEC-COMB, is proposed. The algorithm consists of four parts: preprocessing, node order determination, subgraph isomorphism matching and subgraph extraction. In the case of subgraph isomorphism matching, a combination strategy is used for nodes in NEC to avoid repeated matching of equivalent nodes. The experimental results show that NEC-COMB can effectively improve the search efficiency and optimize the de-duplication effect compared with the classical algorithm VF2G GraphQL Turbo-COMB.
【作者单位】： 北京林业大学信息学院;
【基金】：国家自然科学基金“面向中药方剂信息的不可拆原子组合信息及其层次聚类分析研究”(61602042)
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 庞彦军;吴和琴;;未确知等价类与未确知空间[J];河北煤炭建筑工程学院学报;1993年02期

2 韩绍岑;;有限集合上函数的强等价类[J];四川师范学院学报(自然科学版);1989年01期

3 王杰;关于排列的型[J];北京大学学报(自然科学版);1990年05期

4 韩绍岑;关于Polya-de Bruijn计数定理局限性的评注[J];数学研究与评论;1991年01期

5 徐凤生;于秀清;张环理;;S-粗等价类与知识动态挖掘-发现[J];山东大学学报(理学版);2013年03期

6 赵树理;王军昌;史开泉;;逆P-等价类的逆P-推理分离-还原[J];山东大学学报(理学版);2013年01期

7 林培榕;张其森;李进金;;基于交可约等价类的概念格属性约简[J];模式识别与人工智能;2010年05期

8 王建丰;陈佐利;;一类图的伴随等价类的应用[J];河北科技师范学院学报;2007年03期

9 韩绍岑,查晓亚;Pòlya计数定理之精细化[J];科学通报;1986年09期

10 韩绍岑;有限集合上函数的强等价类[J];科学通报;1989年18期

相关硕士学位论文 前1条

1 别全涛;在部分Motzkin格路中模子结构长不超过2的等价类[D];大连海事大学;2017年

，

本文编号：1598363