基于顶点加权的介度中心近似算法研究

摘要：

介度中心(Betweenness Centrality)是衡量网络节点重要程度的一个广泛使用的指标,最快的介度中心算法需要计算n次单源最短路径,时间复杂度是O(V*E).介度中心算法的瓶颈就在于计算量太大,导致运行时间太长,无法在实际中应用,因此需要从近似算法的角度降低介度中心算法的计算量.目前介度中心近似算法在计算自然图时对计算量的降低并不显著.为了进一步降低介度中心算法的计算量,本文提出一种基于顶点加权的介度中心近似算法,该算法采用顶点加权的方式将多次重复计算过程累加到一次计算过程上,结合选择高影响力源点的方法可以大大降低介度中心算法的计算量,加速比平均达到了25倍,并且最大误差百分比小于0.01％.

关键词： 网络节点 介度中心近似算法 顶点加权 计算量

作者: 王敏 王蕾 冯晓兵 曹宝香

作者单位: 中国科学院计算技术研究所计算机体系结构国家重点实验室,北京 100190;曲阜师范大学信息科学与工程学院,山东 日照 276800 中国科学院计算技术研究所计算机体系结构国家重点实验室,北京 100190 曲阜师范大学信息科学与工程学院,山东 日照 276800

会议类型: 国内会议

会议名称: 2014全国高性能计算学术年会

会议地点: 广州

会议语种:中文

页码: 165-174

在线出版日期: 2014-11-06（万方平台首次上网日期，不代表论文的发表时间）