摘要：随着计算机和互联网的迅猛发展，面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大，这对网络分析算法的性能提出了更高的要求。介数值作为图的重要结构性质，广泛应用于基于图的聚类、分类算法，如何降低其计算的复杂性是急需解决的问题。目前，常用的方法是利用对最短路径长度的近似来降低网络分析算法的复杂性，但已有的近似方法没有考虑现实大规模网络的复杂网络特性，对最短路径长度的近似方法也不能直接用于介数值的近似。本文提出了一种新的介数近似计算方法，其基本思想是结合复杂网络的结构特性，利用通过网络中枢节点的路径来近似最短路径，以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算提供了一种新颖的思路。通过与传统的介数计算方法和近似方法进行实验比较，验证了本文的算法能够大幅降低计算复杂性，并保持较高的近似有效性，并通过对实验数据的分析得到了若干有益的结论，为进一步的研究工作奠定了基础。

关键词：复杂网络 介数值 最短路径 计算复杂度 近似算法 

单位：国防科技大学计算机学院 湖南长沙410073