ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (7): 1631-1640.doi: 10.7544/issn1000-1239.2016.20148355

• 系统结构 • 上一篇    下一篇

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

王敏1,2,王蕾1,冯晓兵1,曹宝香2   

  1. 1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190); 2(曲阜师范大学信息科学与工程学院 山东日照 276800) (wangmin01@ict.ac.cn)
  • 出版日期: 2016-07-01
  • 基金资助: 
    国家“八六三”高技术研究发展计划基金项目(2015AA011505);国家自然科学基金项目(61402445,61303053,61202055,61221062)This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA011505) and the National Natural Science Foundation of China (61402445,61303053,61202055,61221062).

An Approximation Algorithm of Betweenness Centrality Based on Vertex Weighted

Wang Min1,2, Wang Lei1, Feng Xiaobing1, Cao Baoxiang2   

  1. 1(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);2(College of Information Science and Engineering, Qufu Normal University, Rizhao, Shandong 276800)
  • Online: 2016-07-01

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

关键词: 介度中心算法, 计算量, 影响力, 顶点加权, 近似

Abstract: Betweenness centrality (BC) is a widely used indicator to measure the importance of network vertices. Currently the fastest time complexity of the algorithm is O(V×E). When computing the BC of vertices in networks, we need to do n times searches of single source shortest path. In big data era, networks have more nodes and edges, and the amount of calculation of BC algorithm is large. The huge amount of calculation makes the algorithm need a long time to compute each vertices’ BC value, and the algorithm cannot be applied in practice. The related work focuses on approximation to reduce the running time of BC algorithm, but they also can not reduce the amount of calculation of BC algorithm significantly. In order to further reduce the amount of the calculation of BC algorithm, we propose a vertex weighted approximation algorithm to reduce the amount of calculation of BC algorithm, and the algorithm can make the calculation process be repeated many times to accumulate on a calculation by vertex weighted and select high-impact vertex as source to compute BC. We can reduce the amount of calculation significantly in this way, and meet the requirement of lower error rate and high performance. The approximation algorithm of BC based on vertex weighted can achieve 25 times speedup, and the error rate is lower than percentage of 0.01.

Key words: betweenness centrality (BC) algorithm, calculation, influence, vertex weighted, approximation

中图分类号: