毛国勇， 张 宁

（1.常州工学院 电子信息与电气工程学院，常州 213002；2.上海理工大学 管理学院，上海 200093）

大规模网络分析在许多重要领域，如社会网络、信息传播网络和生物网络等领域中有着广泛的应用［1］，而介数［2］（BC）是分析大规模复杂网络时广泛使用的一个指标.通过这个指标，可以对图中节点的重要程度进行定量分析，可以衡量一个节点在网络通信中的重要性，识别出网络中的关键节点.较高的BC指标表明，一个节点到其它节点有相对较多的最短路径，或者这个节点位于其它两个节点最短路径上的可能性很大.BC反映了相应的节点在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义.例如，在社会关系网或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于发现和保护关键资源、技术和人才具有重要意义.BC的计算是网络分析的重要内容，它占了大部分的计算时间.所以，对这个算法进行并行加速具有重要意义.

1 BC算法简介

节点v的BC为

式中，σst为从节点s到节点t的最短路径总数目；σst（v）为这些路径中经过顶点v的路径条数.计算一个图中所有顶点的BC需要计算所有顶点间的最短路径，所需时间为O（n3）.对于无权图，用Brandes算法计算所需时间为O（n×m）［3］，其中，n为顶点的数目，m为边的数目.

Brandes算法由宽度优先搜索（breadth first search，BFS）、部分和累加、标准化等3个部分构成.对于图1所示的BC算法示例图中的b点，其BC值为

式中，σac（b）为经过b点从a到……