An Approximation Algorithm of Betweenness Centrality Based on Vertex Weighted
-
摘要: 介度中心(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.
-
Keywords:
- betweenness centrality (BC) algorithm /
- calculation /
- influence /
- vertex weighted /
- approximation
-
计量
- 文章访问数: 1154
- HTML全文浏览量: 0
- PDF下载量: 580
下载:
