多维复杂网络中的K步介数中心性近似算法研究

《多维复杂网络中的K步介数中心性近似算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０密级：公开学号：４０３１５３１９１６＠ｉ￡￥ＡｆＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ中文题目：多维复杂网络中的Ｋ步介数中心性近似算法研究－ｗｅｅｎｎｅｓｓＡＲｅｓｅａｒｃｈｏｎＫｓｔｅＢｅｔＣｅｎｔｒａｌｉｔｒｏｘｉｍａｔｉｏｎｐｙｐｐ英文题目：ＡｌｇｏｒｉｔｈｍｆｏｒＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ张瑜论文作者：张昕副教授指导

2、教师：专业：计算机应用技术成时间二〇一八年四月：备ｍ辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的＾论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体已经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承袒。ｙ以ｉｒ；学位论文作者签名：年月日＾／学位论文版权使用授权书本学位论文作者完全了解学校

3、有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权辽宁大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《屮国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理。保

4、密（），在年后解密适用本授权书。（保密：请在括号＿＿“”内划Ｖ）：授权人签名指导教师签名：日期：＞／名年ｉ月＞曰日期：年上月日／申请辽宁大学硕士学位论文多维复杂网络中的K步介数中心性近似算法研究ResearchonK-stepBetweennessCentralityApproximationAlgorithmforMultidimensionalComplexNetworks作者：张瑜指导教师：张昕副教授专业：计算机应用技术答辩日期：2018年5月22日二〇一八年五月·中国辽宁摘要摘要近年来

5、，随着互联网的发展、复杂网络规模不断的扩大，网络的结构呈多样化、多维度共存的趋势发展，因此，研究复杂网络的多维度结构具有重要的意义及应用价值。现有的复杂网络的相关研究成果大部分都是关于单一维度网络的，并不能适用于多维复杂网络上。在复杂网络分析中关键节点是一个重要的研究方向，而介数中心性算法占有重要的地位，因此本文在原有的研究成果基础上把介数中心性算法扩展到了多维复杂网络上。本文首先重新定义了多维网络上的介数中心性，计算多维K步介数中心性是对整个图计算最短路径，为了减少计算量采用了K步思想，但由于单一维度网络上的最

6、短路径不能适用于多维网络上，所以我们给出了多维K步最短路径的一系列的定义，且多维K步最短路径是跨维度全网遍历的，在此基础上，给出了每一维度上节点的K步介数中心性，从而进一步的定义了多维K步介数中心性。为了便于计算把在多维网络上的节点度进行了形式规范化。本文从减少多维K步最短路径的重复的相似计算和网络的无标度特性相结合的角度考虑降低多维K步介度中心性算法的计算量，提出的多维K步介数中心性近似算法分为3个阶段：首先是根据度选择源节点阶段，节点度与介数中心性大致呈正相关，故选取度高的x%节点作为了源节点进行遍历计算；其

7、次是源节点加权处理阶段，我们采用高度数节点的计算过程代替低度数节点的计算过程的方法来减少计算多维K步介数中心性时存在的大量重复相似计算；最后是多维K步介数中心值计算阶段，根据上一步中获得的权值决定重复累加的次数。算法近似一方面体现在采用了K步思想，另一方面体现在算法第2阶段源节点加权处理阶段，把低度节点的遍历次数作为高度数节点的权值，在算法回溯时，用依赖值乘以权值累加到多维K步介数中心值的计算中。本文在多个真实多维网络上对多维K步介数中心性近似算法进行了实验与分析，根据实际网络确定适用的K值及x值，利用误差评价指

8、标得到的实验结果证明了该算法在保证了节点重要程度准确率的前提下，又提高了算法的效率。关键词：复杂网络，多维网络，K步最短路径，K步介数中心性，近似算法IABSTRACTABSTRACTInrecentyears,withthedevelopmentoftheInternetandtheexpansionofcomplexnetworks,thestructureofthe