期刊文献+

基于邻域等价类的同构子图搜索算法 被引量:2

Isomorphic Subgraph Search Algorithm Based on Neighborhood Equivalence Class
下载PDF
导出
摘要 节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于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.
出处 《计算机工程》 CAS CSCD 北大核心 2017年第9期7-11,共5页 Computer Engineering
基金 国家自然科学基金"面向中药方剂信息的不可拆原子组合信息及其层次聚类分析研究"(61602042)
关键词 子图同构 子图搜索 异质图 同构匹配 邻域等价类 subgraph isomorphism subgraph search heterogeneous graph isomorphism matching Neighborhood Equivalence Class(NEC)
  • 相关文献

参考文献3

二级参考文献35

  • 1李锋,陆韬.任意图同构判定及其应用[J].复旦学报(自然科学版),2006,45(4):480-484. 被引量:12
  • 2李先通,李建中,高宏.一种高效频繁子图挖掘算法[J].软件学报,2007,18(10):2469-2480. 被引量:35
  • 3Michihiro Kuramochi,George Karypis.An Efficient Algorithm for Discovering Frequent Subgraphs. IEEE Transactions on Knowledge and Data Engineering . 2004
  • 4Wernicke S.Efficient detection of network motifs. IEEE/ACM Transactions on Computational Biology and Bioinformatics . 2006
  • 5http://dip.doe-mbi.uda.edu .
  • 6www.weizmann.ac.il/mcb/UriAlon/groupNetworksData.html/ .
  • 7J. Torán.On the hardness of graph isomorphism. SIAM J. Comput. (SICOMP) . 2004
  • 8McKay B D.Practical graph isomorphism. Congressus Numeranium . 1981
  • 9Mason O,Verwoerd M.Graph theory and networks in biology. http://www.hamilton.ie/systems-biology/files/2006/graph_theory_and_networks_in_biology.pdf . 2007
  • 10Yan X,Han J.gSpan:Graph-based substructure pattern mining. Proceedings of the IEEE International Conference on Data Mining . 2002

共引文献8

同被引文献12

引证文献2

二级引证文献5

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部