大图上子图匹配算法研究

《大图上子图匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER’SDISSERTATION论文题目大图上子图匹配算法研究作者姓名李开宇学位类别工程硕士指导教师王璿副教授2016年5月中图分类号：TP312学校代码：10216UDC：654密级：公开工程硕士学位论文(工程设计型)大图上子图匹配算法研究硕士研究生：李开宇导师：王璿副教授副导师：徐凤东高级工程师申请学位：工程硕士工程领域：计算机技术所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinComputerTechnologyTHERE

2、SEARCHONSUBGRAPHMATCHINGALGORITHMINLARGEGRAPHDATABASESByLiKaiyuSupervisor:AssociateProfessorWangXuanYanshanUniversityMay,2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《大图上子图匹配算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的

3、个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日摘要摘要子图匹配是图算法研究的一个主要问题。子图匹配问题的定义是给出查询图，从大图数据库中找到与查询图结构相同且节点标签相同的所有子图。但在实际的应用中，用户往往只关心一些匹配得分较高的结果。因此便引入了Top-K子图匹配问题。Top-K子图匹配问题与子图匹配问题相似，不同之处在于Top-K子图匹配问题会对结果进行排序，最终返回k个得分较高的子图。因此对于返回全部子图匹配的问题，Top-K子图匹配问题显得更有针

4、对性。本文针对图数据处理中的Top-K子图匹配查询进行研究，具体研究内容如下。首先，子图匹配方法主要采用过滤-验证模式进行查询，则过滤效果和验证效果将是影响算法效率的两个主要因素。通过对现有的子图匹配问题处理方法的分析，发现在过滤阶段现有方法主要存在以下问题：(1)等价节点重复枚举问题；(2)基于路径结构过滤开销过大的问题；(3)匹配顺序不当问题。在验证阶段则存在大量冗余验证问题。其次，在过滤阶段，提出PFilter算法，针对等价节点重复枚举问题，提出图压缩策略，将等价节点压缩从而减少枚举。针对基于路径

5、过滤开销过大的问题，提出只考察直接邻居作为过滤方法，从而减少开销。针对匹配顺序不当问题，提出对查询图中候选节点最少的节点作为匹配起始节点，向图的两端进行深度优先探查。再次，在验证阶段，提出PGetScore算法，针对造成大量冗余验证的问题，提出利用RWM(rankingwhilematching)思想，对算法进行提前终止，从而减少冗余验证。最后，通过实验从处理时间、压缩节点数目等方面对本文提出的方法的高效性进行了验证。关键词：子图匹配；等价节点压缩；过滤方法；匹配顺序；RWM方法-I-燕山大学工程硕士学

6、位论文AbstractSubgraphmatchingisaprincipalquestioningraphtheory.Thedefinitionofsubgraphmatchingisgivingaquerygraph,findingallsubgraphsinlargegraphdatabaseswhichhavethesamestructureandnodelabelwiththequerygraph.Inpractice,wearealwaysconcernedwiththesubgraphs

7、whichgetahigherscore.SoweproposethethoughtaboutTop-Ksubgraphmatching.It`ssimiliartosubgraphmatching,butinTop-ksubgraphmatching,itwillsortthefinalresultandshowusKsubgraphswhichhasthehigherscorecomparedwithothers.SoTop-Ksubgraphmatchingismorepertinent.Thep

8、aperistheresearchoftheTop-Ksubgraphmatchingsearchinlargegraphdatabases,andtheresearchcontentsareasfollows.Firstlyweusefiltering-matchingmethodtofindthesubgraphmatching.Theefficiencyofthealgorithmisconcernedwiththefiltereff