top-k中心度查询算法研究

《top-k中心度查询算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER’SDISSERTATION论文题目Top-k中心度查询算法研究作者姓名王磊学位类别工程硕士指导教师陈子阳教授2016年5月中图分类号：TP312学校代码：10216UDC：654密级：公开工程硕士学位论文Top-k中心度查询算法研究硕士研究生：王磊导师：陈子阳教授副导师：徐凤东高级工程师申请学位：工程硕士工程领域：计算机技术所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinComputerTechnologyRESEARCHONTOP-KCENTRALITYQUERYALGORITHMS

2、ByWangLeiSupervisor：ProfessorChenZiyangYanshanUniversityMay,2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《Top-k中心度查询算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学硕士学位论文使用授权书《Top-k中心度查询算法研究》系本人在燕山大学攻读硕士

3、学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分内容。保密□，在年解密后适用本授权书。本学位论文属于不保密□。（请在以上相应方框内打“√”）作者签名：日期：年月日导师签名：日期：年月日摘要摘要如何快速地找出中心度最高的k个点是有关图模型研究的热点问题之一，在现实生活中有着广泛的应用，比如超市选址、

4、城市规划、热点新闻报道、数据挖掘以及病毒营销策略等。通过对现有方法进行分析，发现现有方法的低效性主要是由于顶点处理顺序的代价过高和处理顶点数量过多造成的。本文针对现有中心度计算方法效率低的问题展开研究，具体内容如下。首先，针对顶点处理顺序的代价过高提出一种基于拓扑排序的top-k中心度查询算法。该算法采用拓扑顺序替代已有方法的顶点处理顺序，减少已有方法求解顶点处理顺序所带来的昂贵的时间代价。其优点是简单、高效，但是应用具有一定的局限性，对于结构比较复杂的图计算代价会很高。其次，针对处理顶点数量过多的问题，提出基于估算筛选的中心度查询算法。该算法通过一次广度优先遍历估

5、算出每个点中心度的上界值，通过上界值的大小确定顶点的处理顺序。在计算过程中，通过维护top-k中心度的真实值，可以有效地过滤掉无需计算中心度真实值的点，使候选集需要计算真实中心度值的点变少，从而减少计算代价，提高了算法性能。最后，在不同类型特征和规模大小的图上进行实验对比分析，从时间消耗、k值变化等方面对本文方法的高效性进行了验证。关键词：中心度；拓扑排序；扩展顺序；广度优先遍历-I-燕山大学工程硕士学位论文AbstractHowtoquicklyfindthekpointswiththehighestcentralityisoneofthehotissuesrel

6、atedtographmodelstudywhichhasawiderangeofapplicationsinreallife,suchassupermarketsite,urbanplanning,dataminingandviralmarketingstrategies,etc.Byanalyzingtheexistingmethods,itisfoundthatthelowefficiencyoftheexistingmethodsismainlyduetothehighcostofvertexprocessingsequenceandtheexcessive

7、numberofprocessingvertices.Thispaperfocusesontheproblemoflowefficiencyoftheexistingcentralitycomputingmethod,andthespecificresearchcontentsareasfollows.Firstly,weproposeanewalgorithmforthefirstproblem,namelyToM,whichusesthetopologicalordertodeterminetheorderofprocessingsequenceofvert