高效子图匹配算法研究

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

1、■Ｉｆ—．，！：苗Ｌ迸．学校代码：１０００４密级：公开’獻交道乂肇ｊＢＥＩＪＩＮＧＪＩＡＯＴＯＮＧＵＮＩＶＥＲＳＩＴＹ．．Ｍ｜硕±学位论文高效子图匹配算法研究美：漏－—＇＂■ｒｏａｅ作者姓名戴昕＾学科专业计龍科学与技术指导教师聽帛旨ｉｊ龍＾培养院系计算机与信息技术学院．．ＪＢＭ＾Ｉ－－Ｉ龍释３窗匿１Ｋ１１，ｍｍ＾＾－六年兰．二零零驅．月＾ｉ｜齡《道乂攀硕古学位论文高效子图匹配算法研究ＲｅｓｅａｒｃｈｏｎＥ

2、ｆｆｉｃｉｅｎｔＳｕｂｇｒａｐｈＭａｔｃｈｉｎｇＡｌｇｏｒｉｔｈｍ作者：戴昕导师：徐保民北京交通大学２０１６年３月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编Ｗ供查阅和借阅。同意学校向国家有关部口或机构送交论文的复印件和磁盘。学校可Ｗ为存在馆际合作关系的兄弟高校用户提供文献传递服务和交换服务。（保密的学位

3、论文在解密后适用本授权说明）＂学位论文作者签名．；０导师签名；勒＾签字曰期１長：７年月Ｖ：年＾（）曰签字曰期月曰）与：学校代码：１０００４密级公开北京交通大学硕±学位论文高效子图匹配算法研究ＲｅｓｅａｒｃｈｏｎＥｆｆｉｃｉｅｎｔＳｕｂｒａｈＭａｔｃｈｉｎＡｌｏｒｉｔｈｍｇｐｇｇ作者姓名：戴昕学号：１３１２０３８５导师姓名；徐保民职称：副教授学位类别：：工学学位级别硕±学科专业：计算机科学与技术研究方向：子图匹配北京交通大学２０１６年３月

4、ｉｉｉ致谢２００８一自年的那个秋天起，我己在交大度过了八个春秋。看着芳华园的银杏二Ｈ食堂变一，０５，看成了学生活动中也年年辞旧迎新从次次被染成金色着。级一１５，到级，我见过的交大学子也有十代人了。纵然有太多话要说给交大此时却也只能道一声感谢。２０１２年初考、研失败，不得不在凄凉的屯态下结束了浑浑麗驅的四年本科生涯。幸运的是，家人，老师和同学们鼓励我不要气優，继续报考本校的研究生。２０１２的下半年是在逸夫７层的自习室里度过的，，那时我己不是交大的学生但那段时一间却是我在交大最为努力用功的

5、岁月。必须要感谢那年鼓励我陪伴我的家人，老师和同学，，是你们让我不断前行最终与交大再续前缘。２０１３年，硕±研究的新旅程开始了，我很幸运成为徐保民老师的学生。徐老师不仅仅传授给我专业知识和研究方法，，更重要的是激发了我对学术生涯的兴趣给与充分的自由去寻找感兴趣的研究方向。已经不记得有多少次和徐老师在教室，，，甚至下班回家的地铁上讨论我的课题实验室校园的小道上。老师令人敬佩的耐也和热情始终激励着我在学术的道路上前行。Ｈ年来，徐老师不仅仅指导着我的学业一，而且鼓励我进步深造。特别在时间安排上，照顾

6、我为留学读博做准备。我要感谢徐老师，他对我的培养不仅仅在过去与当下，也在未来，而这些都会成为今后人生中的宝贵财富。我要感谢这八年来共同成长的同学，他们有的己经走向社会称为栋梁，有的还在追求自己的学业。特别的，我要感谢宏亮，罗干两位同学陪伴我走过了整个＝一１２交大生涯，感谢牛品寂同学年的同窗之谊。过去年里级田雪涛，我院本科学弟对本文的研究工作作出了诸多贡献，感激之情无需言表。实验室的各位兄弟一一姐妹带给我无数快乐的时光，亦当谢之。，我要感谢我的父母最后，感谢他们永远守望在我的人生道路上。

7、ｉｖ北京交通大学硕±学位论文摘要摘要图作为一种数据结构能够简洁有力地刻画出普遍事物间的联系此基于图，因的数据挖掘与管理技术无论在学术研究还是工业应用上都享有重要的地位。这其中最基本的任务是如何在图数据集中找到给定的查询图，也就是子图匹配问题。对于正在蓬勃发展的图数据库一，生物信息学和社会网络分析等领域而言，个高效的子图匹配算法的重要性不言而喻。子图匹配的数学基础是图论中的经典问题Ｉ一，子图同构，个著名的ＮＰ问题。可想而知设计高效的子图匹配算法面临着相当一一。巨大大的挑战目前，

8、子图匹配算法的研究工作主要有两个问题。其是针对张边数较多的图如何进行有效的过滤，其二是如何选择顶点搜索顺序来加快子图同构搜索的速度。特别是后者是近年来子图匹配研究的焦点。一针对上述情况，本文提出了个多段图模型（ＭＧＳＭ）用于指导顶点搜索顺序的选择。根据这个模型得到优化搜索顺序的两个关键点：特征选择和代价（