基于包含度的子图匹配方法

来源：软件学报杂志2018年第6期北京时间：

作者：李瑞远,洪亮

单位：李瑞远，西安电子科技大学 计算机学院, 陕西 西安 71007111,洪亮，武汉大学 信息管理学院, 湖北 武汉 430072;武汉大学 深圳研究院, 广东 深圳 51800002

摘要：子图匹配是图论中最基本的操作.研究子图匹配的一个变种，即：在一个节点拥有若干元素的大图数据库中，找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图，称作基于包含度的子图匹配（subgraph matching with inclusion degree，简称SMID）.该查询能够应用于多种场景，包括论文检索、社区发现、企业招聘等.为高效实现SMID，设计了同时包含节点元素和图结构信息的数据签名与查询签名，在离线处理阶段，利用数据签名为数据图建立动态签名树（DS-Tree），以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题，设计了一种DS-Tree压缩方法，在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率，还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明，所提出的方法在效率和扩展性方面优于现有其他方法.

关键词：子图匹配;包含度;图数据库;索引;支配子图

基金资助：国家重点研发计划（2016YFB1000603）；国家自然科学基金（61303025）；深圳市基础研究项目（JCYJ20160523160953223）；NSFC-广东联合基金；国家超级计算广州中心