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

• 作者: 张宇彤 曹佳 王思檬
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 子图同构 子图搜索 异质图 同构匹配 邻域等价类
• 年，卷（期）: 2017,（9）
• 所属期刊栏目: 先进计算与数据处理
• 页码范围: 7-11
• 页数: 5页
• 分类号: TP391.41
• 字数: 4485字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2017.09.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曹佳	北京林业大学信息学院	15	54	3.0	7.0
2	王思檬	北京林业大学信息学院	4	4	1.0	2.0
3	张宇彤	北京林业大学信息学院	2	3	1.0	1.0