王　敏　王　蕾　冯晓兵　曹宝香

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



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

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

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

(wangmin01@ict.ac.cn)

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

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

衡量网络节点的重要程度是网络分析的一个重要方面，在衡量网络节点重要程度时，被广泛使用的一个指标是介度中心(betweenness centrality, BC)[1].介度中心算法有着广泛的使用范围，例如社区划分[2]、查找恐怖组织的领导者[3]、保护网络节点中的关键服务……