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

An Approximation Algorithm of Betweenness Centrality Based on Vertex Weighted

作　　者：王敏[1,2] 王蕾 冯晓兵[1] 曹宝香[2] 

机构地区：[1]计算机体系结构国家重点实验室(中国科学院计算技术研究所),北京100190 [2]曲阜师范大学信息科学与工程学院,山东日照276800

出　　处：《计算机研究与发展》2016年第7期1631-1640,共10页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2015AA011505);国家自然科学基金项目(61402445;61303053;61202055;61221062)~~

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]