社交网络中的子图查询研究

《社交网络中的子图查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文社交网络中的子图查询研究ResearchofSubgraphQueryonSocialNetwork作者：张青导师：孟凡荣教授中国矿业大学二〇一四年五月万方数据中图分类号TP311学校代码10290UDC004密级公开中国矿业大学硕士学位论文社交网络中的子图查询研究ResearchofSubgraphQueryonSocialNetwork作者张青导师孟凡荣申请学位工学硕士学位培养单位计算机科学与技术学院学科专业计算机应用技术研究方向数据挖掘答辩委员会主席评阅人二○一四年五月万方数据学位论文使用授权声明本人完全了解中国矿业大学有关保留、使用学位论文的规定，同意本人所撰写的学位论文的

2、使用授权按照学校的管理规定处理：作为申请学位的条件之一，学位论文著作权拥有者须授权所在学校拥有学位论文的部分使用权，即：①学校档案馆和图书馆有权保留学位论文的纸质版和电子版，可以使用影印、缩印或扫描等复制手段保存和汇编学位论文；②为教学和科研目的，学校档案馆和图书馆可以将公开的学位论文作为资料在档案馆、图书馆等场所或在校园网上供校内师生阅读、浏览。另外，根据有关法规，同意中国国家图书馆保存研究生学位论文。（保密的学位论文在解密后适用本授权书）。作者签名：导师签名：年月日年月日万方数据学位论文原创性声明Declarationofthesisoriginality本人郑重声明：所呈交的学位论文《社

3、交网络中的子图查询研究》，是本人在导师指导下，在中国矿业大学攻读学位期间进行的研究工作所取得的成果。据我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：年月日67万方数据论文审阅认定书研究生在规定的学习年限内，按照研究生培养方案的要求，完成了研究生课程的学习，成绩合格；在我的指导下完成本学位论文,经审阅，论文中的观点、数据、表述和结构为我所认同，论文撰写格式符合学校的相关规定，同意将本论文作为学位申请论文送专家评审。导师签字：年月日

4、万方数据致谢首先，非常诚挚地感谢我的导师孟凡荣教授，本文是在孟老师的悉心指导下完成的。孟老师治学严谨，求实进取，学识渊博，让我在研究生期间不仅学到了许多专业知识，而且也学会了不少做人的道理，对我的人生观产生了深远的影响。在研究生三年学习期间，孟老师在学习、工作上给了我大量的指导和教诲，在此致以深深的感谢。感谢夏士雄院长、孟凡荣老师给我们提供良好的科研环境，以及生活上和学习上的无私帮助和支持。感谢孟凡荣老师和闫秋艳老师，从论文选题直到论文终稿的完成，都离不开两位老师的指导和帮助。在撰写论文期间，闫老师反复地为我修改，给我提出一些建设性意见，她严谨的治学态度让我敬佩。感谢周勇老师在平时的学习和研究

5、中给予了我莫大的帮助和关怀，在此致以诚挚的感谢。感谢袁冠老师、朱牧师兄在我发表小论文时给予的帮助和指导，他们的意见和建议对我小论文的顺利发表起到了非常重大的作用。感谢牛强老师及实验室各位老师对我的指导和关心。感谢邢艳师姐、李雯师姐对我学习生活的帮助。感谢陪伴我度过三年快乐时光实验室诸位同学。感谢翟静师妹、殷和双师妹、姚彦旭师弟和包伟伟师弟等对我研究的大力支持与帮助。与你们共同学习生活的这三年美好时光我永远也不会忘记。感谢一直关心和支持我的亲人和朋友，他们的鞭策、鼓励、理解和帮助是我克服困难、不断进步的精神支柱，也将是我勇往直前的精神动力，我的任何成绩都是和他们的支持分不开的。在此，我要深深地祝

6、福他们！本论文虽然几经修改，但由于才疏学浅，疏漏之处在所难免，还望各位老师批评指正，衷心地感谢在百忙之中评阅论文和参加答辩的各位专家、教授！万方数据摘要随着社交网络的不断发展，图数据处理的重要地位日益突显。相对于传统的数据类型，图数据更加复杂，表达的语义更加丰富。针对如此复杂的数据类型，寻找到高效的查询处理方法，对于提高社交网络的分析效率和图数据的质量非常重要。然而，在实际情况中图往往存在噪声或者由于对事物的认识存在盲点，图中存在着不确定性，因此图数据又可以分为确定图和不确定图。本文根据上述两种图分别给出针对确定图的子图查询算法和针对不确定图的子图查询算法。首先，对于确定图的子图查询，本文针对

7、以往的算法大多采用静态消耗测算模式的问题，根据信息熵在信息度量中的作用，将条件信息熵作为启发式匹配的依据，将信息熵的概念引入到图数据查询中，建立以信息熵为度量标准的动态测算模型，并以该动态测算模型为中心研究并实现了基于信息熵的子图匹配算法。该算法减少了邻接点的匹配次数，提高了子图查询的效率。实验表明：基于信息熵的子图匹配算法具有更高的查询效率，且在幂函数分布的数据集上效果更明显。其次，对于不确定图