复杂系统与复杂性科学第8卷第3期2011年9月Vol.8No.3Sep.2011:167223813(2011)0320044210介数中心性和平均最短路径长度整合近似算法何宇,赵洪利,姚曜,赵东杰,付(装备指挥技术学院,北京1010416)芸摘要:基于Brandes算法给出了复杂网络中介数中心性和平均最短路径长度的整合近似算法,通过理论分析和Rocketfuel项目实测数据的实验分析,验证了该整合算法能够快速有效地估计出复杂网络的介数中心性和平均最短路径长度,为进一步的研究工作奠定了基础。:TP301.6文献标识码:AAnIntegratedApproximationAlgorithmfortheBetweennessCentralityandAverageShortest2PathHEYu,ZHAOHong2li,YAOYao,ZHAODong2激e,FUYunAbstract:Anintegratedapproximationalgorithmforthebetweennesscentralityandaverageshor2test2pathlengthincomplexnetworksisgiveninthispaper.Byacademicandexperimentalanaly2sis,thealgorithmhasagoodperformance,whichwillgivehelptothefurtherstudies.Keywords:complexnetworks;betweennesscentrality;averageshortest2pathlength;引言0现实生活中存在的大量复杂系统都可以通过不同的网络加以描述,网络科学业已成为众多学科汇聚的交叉点。复杂网络分析方法逐渐渗透到各领域,用以描述系统中各个体之间的关系及系统的集体行为,其研究者来自图论、统计物理学、通信(计算机)网络、生态学、社会学以及经济学等多个领域。近年来,关于复杂网络的研究正处于蓬勃发展的阶段,取得了丰硕的成果。介数中心性和平均最短路径长度揭示了复杂网络的重要性质,是复杂网络研究中的重要测度。对通信网络而言,网络的介数中心性和平均最短路径长度在一定程度上反映了节点所需的信息处理能力和信网络研究中不可避免的问题。近年来,国内外学者对复杂网络测度估算的问题进行了广泛深入研究。Carpenter等人[3]在分析恐怖分子网络时指出了介数中心性估算是需要解决的重要问题;Brandes[4]通过收稿日期:2010211203基金项目:部委级资助项目(513300403)作者简介:何宇(19832),男,四川南充人,博士研究生,主要研究方向为通信与信息系统、复杂系统。对介数中心性算法的深入研究,在2001年提出了高效的介数中心性算法;Brandes和Pich[5]提出了基于抽样原理的介数中心性估计算法;Geisberger等人[6]提出了针对不重要节点也具有较好效果的介数中心性估计算法;Bader[7]针对网络中某一节点提出了基于抽样原理的自适应介数中心性估计算法;唐晋韬等人[8]根据图的结构性质,利用通过网络中枢节点的路径来近似最短路径,从而基于近似路径求得介数中心性的近似值。根据路径距离的定义,网络最短路径估计可以分为跳数路径估计和物理距离估计两类,物理距离估计通常需要先将网络节点映射到坐标系统然后再进行距离估计[9210]。Zhao等人[11]基于网络坐标系统思想设计了Orion图坐标系统来估计网络的物理距离;Kleinberg[12]通过使用界标点讨论了真实介数中心性近似算法分析针对网络连通图G(V,E)(|V|=n,|E|1=m),任意两节点s,t∈V,σst=σts表示节点s与节点t之间最短路径的数量,σst(v)表示节点s与节点t之间经过节点v的最短路径的数量。网络G中节点v的介数中心性为[14]∑σst(v)∑δst(v)B(v)==σs≠v≠t∈Vsts≠v≠t∈V目前,已知最快的介数中心性计算算法是由UlrikBrandes于2001年提出的,这里称为Brandes介数中心性算法。在无权条件下,该算法的计算复杂度为O(mn);在加权条件下,该算法的计算复杂度为O(mn+推论1[4]性满足以网络G中节点s∈V为源点,节点s到网络中其他节点的最短路径对应节点v的介数中心σsvδs·(v)∑σ(1+δs·(w))=sww,v∈Ps(w)Brandes介数中心性算法的核心思想为:任取一个节点为源节点,通过深度优先算法查找源节点到网络中其他节点之间的最短路径,计算这些最短路径对应节点的介数中心性。累加网络中以每个节点为源节点计算得到的介数中心性,从而得到网络中所有节点的最终介数中心性。根据Brandes介数中心性算法,设以节点vi为源节点对网络(网络中节点数为n)进行一次深度优先遍历,节点vi到网络中其他节点的最短路径对应节点v的介数中心性为bi(v)=δvi3(v),则节点v的介数中心≤bi(v)≤n-200≤B(v)≤(n-1)(n-2)随机选取一个节...