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

来源：计算机研究与发展杂志2016年第7期北京时间：

作者：王敏,王蕾,冯晓兵,曹宝香,

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

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