不确定图上top-k子图相似性查询技术研究

《不确定图上top-k子图相似性查询技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文不确定图上Top．k子图相似。tO-查询技术研究作者姓名：王璐璐指导教师：谷峪副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机应用技术论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：如f啦!一答懒螂：杨嚷番评阅人j熬天成夏岙峰东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyTop--kSubgraphSimilarityQueriesOverUncertainGraphsByWangLuluSupervis

2、or：AssociateProfessorGuYuNortheasternUniversityJune2014万方数据独创性声明本人声明，所成交的学位论文是在导师的指导下完成的。论文中去的的研究成果除标注和致谢的地方外，不包含其他人已经发表或者撰写过的研究成果，也不包含本人获得其他学位而是用过的材料。与我一同工作的同志对本研究所做的任何贡献已在论文中作了明确的说明并表示感谢。学位论文作者签名：王璐锵日期：20I斗耸6月24-8学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有所保留、使用学位论文的规定：即学校有权保留并向国家有关部门或者机

3、构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年i学位论文作者签名：王鬻璐签字日期：锄f4罩6月弭日聊虢后踞签字日期：即c够、多。妒万方数据东北大学硕士毕业论文摘要不确定I至l_lzTop．k子图相似性查询技术研究摘要近年来，随着图结构在生物信息网络和社交网络等领域的广泛应用以及各种外界因素对数据获取的干扰，不确定图模型越来越受到研究者的关注。同时，子图的相似性查询作为图上的基本查询之一广泛应用于各种问题中，

4、研究者们设计并实现了大量的算法来处理查询图为给定的确定图的子图相似性查询，然而对于查询图是不确定图和查询结果为Top．k的情况并没有给予足够的重视且遇到了很大的挑战。针对上述问题，本文对不确定图上的Top．k子图相似性查询问题进行研究。首先，本文考虑边之间的存在概率相互独立的不确定图为数据图的情况，由于查询图为数据图中的一个导出子图，故查询图也为边之间的存在概率相互独立的不确定图，然后本文形式化定义了面向不确定图上的Top．k子图相似性查询问题，并针对此问题提出了基于可能世界模型的算法。本文中提出了一些优化算法以进一步提高算法的执行效率，例如根据边之间

5、概率的关系及所求匹配结果的结构特征实现索引优化以减小索引集大小；基于聚簇分块技术对数据图进行预处理以尽量缩小子图匹配范围；根据各个匹配边的概率与编辑距离之间的关系改进计算模型从而避免枚举所有可能世界图来计算概率；根据Top．k的要求提出了基于阈值和Bound剪枝的匹配处理过程等。最后通过大量实验验证所提及的算法及优化算法的有效性。此外，本文考虑边之间的存在概率具有相关性的不确定图为数据图，查询图同数据图类型相同且为其导出子图的情况。该问题是上述问题的改进，定义了带有相关性的不确定图上Top．k子图相似性查询问题。并在上一节的基础之上，结合本节中边之间的

6、关系提出了新的索引建立方法，采用动态获得子结构的算法过程并结合概率上界实现优化剪枝。文中通过实验验证了所提到的算法和优化方法的有效性。总之，本文从越来越接近实际应用的不确定图模型的Top．k子图相似性查询的典型特征和挑战出发，针对不确定图和带有相关性的不确定图上子图相似性查询的关键技术展开研究，如基于动态匹配方式等，并提供了有效的基于不确定图上的Top．k子图查询问题的处理方法。本文的研究工作所采取的算法思想和剪枝策略为相关课题的开展铺平了道路。．II．万方数据东北大学硕士毕业论文摘要关键词：不确定图；子图相似性查询；可能世界图；带相关性的不确定图；动

7、态匹配．．III．．万方数据东北大学硕士学位论文AbstractTop—kSubgraphSimilarityQueriesoverUncertainGraphsAbstractInrecentyears，thegraphstructureiswidelyusedinthefieldofbio-informaticsandsocialnetworksandallkindsofexternalfactorsinterferewiththeobtaineddata,SOresearchershavegreatinterestsintheuncertaing

8、raphs．Atthemeantime，asoneofthefundamentalresear