介数中心性计算是复杂网络分析中的一个基本问题,它用来衡量一个节点在复杂网络中的重要程度。近年来,介数中心性已经广泛用于社交网络分析,打击恐怖组织网络,治理城市交通网络等。对于介数中心性的计算,不仅是计算机领域研究的热点问题之一,也同样受到其它领域研究人员的关注。然而随着移动互联网的普及,数据量的爆炸式增长,数据的拓扑结构也越来越复杂,传统的图介数计算算法已经无法完全满足图介数计算的需求,甚至在某些情况下由于计算代价过大而显得不切实际,因而研究的热点逐渐转向对图介数的近似计算。本文深入研究了国内外介数中心性的研究现状,发现无论是能够准确计算介数值的算法还是近似计算介数的算法,在大规模图上的计算都有各自的优缺点。准确计算介数值需要计算图中任意一对节点之间的最短路径,需要极大的时间开销。当前对于大规模图介数近似计算的思路主要有两种,一是基于源节点的抽样算法,选取部分源节点进行单源最短路径计算;二是通过对最短路径的近似计算从而提高整个算法的计算速度。在此基础上将二者融合,探索采取何种策略选取源节点以及源节点的选取数量,从已选源节点出发如何在大规模图中近似计算最短路径就成为一种可行的研究方向和解决方案。本文利用复杂网络的小世界特性和无标度特性,即复杂网络中大部分的路径长度都较短,大部分的最短路径都会经过某几个节点度较高的节点。本文提出一种适合大规模图介数近似计算的算法,将节点度高的节点设为中枢节点,利用统计学习中的VC理论对中枢节点的选取数量进行定量计算,从而使得选取数量不再依赖于图数据的规模,而仅仅依赖于图直径。通过任选k条最短路径求出图直径的近似值,计算需要选取的中枢节点数量并根据已记录的节点度从大到小选取。围绕已经选取的中枢节点,用广度优先遍历算法将整个图分为若干个区域,分别在每个区域上执行Mixed策略选取源节点,即依次执行Random策略,MaxMin策略,MaxSum策略,每次执行完一种源节点选取策略后,采用自适应的方式对源节点的选取数量进行控制,直到在所有划分区域上完成源节点选取。根据介数定义公式,用从源节点出发经过中枢节点的较短路径来代替最短路径,从而完成大规模图介数的近似计算。最后通过与其他三种知名介数近似计算算法的实验比较,证明本文提出的大规模图介数近似算法具有良好的效率和准确性。