2022年适合复杂网络分析的最短路径近似算法 .pdf

《2022年适合复杂网络分析的最短路径近似算法 .pdf》由会员分享，可在线阅读，更多相关《2022年适合复杂网络分析的最短路径近似算法 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: Journal of Software ,2011,22(10):2279 - 2290 doi: 10.3724/SP.J.1001.2011.03924 http:/ ? 中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563 适合复杂网络分析的最短路径近似算法?唐晋韬+, 王 挺 , 王 戟(国防科学技术大学计算机学院,湖南长沙 410073) Shortest Path Approximate Algorithm for Complex Network AnalysisTANG

2、Jin-Tao+, WANG Ting, WANG Ji(College of Computer, National University of Defense Technology, Changsha 410073, China) + Corresponding author: E-mail: Tang JT, Wang T, Wang J. Shortest path approximate algorithm for complex network analysis. Journal of Software , 2011,22(10):2279 - 2290. http:/ : The

3、tremendous scale of the social networks mined from Internet is the main obstacle of a social network analysis application. The bottleneck of many network analysis algorithms is the extortionate computational complexity of calculating the shortest path. Real-World networks usually exhibit the same to

4、pological features as complex networks such as the “scale-free” and etc, which indicate the intrinsic laws of the shortest paths in complex networks. Based on the topological features of real-world networks, a novel shortest path approximate algorithm which uses an existent short path passing throug

5、h some local center nodes to estimate the shortest path in complex networks, is proposed. This paper illustrates the advantage and feasibility of incorporating the proposed algorithm within the network properties, which suggests a new idea for complex social network analysis. The proposed algorithm

6、has been evaluated both on synthetic network stage and real world network stage. Experimental results show that the proposed algorithm can largely reduce the computational complexity and remain highly effective in complex networks. Key words : social network; approximation algorithm; network propert

7、y; shortest path problem 摘要: 基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出“ 无标度 ” 等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准

8、确性. 关键词 : 社会网络 ;近似算法 ;网络性质 ;最短路径问题中图法分类号: TP301文献标识码 : A ?基金项目: 国家自然科学基金(60873097); 国家重点基础研究发展计划(973)(2005CB321802); 新世纪优秀人才计划(NCET- 06-0926) 收稿时间 :2009-08-19; 修改时间 : 2010-06-09; 定稿时间 : 2010-07-28 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - -

9、- - - 2280 Journal of Software软件学报 V ol.22, No.10, October 2011 随着 Web 2.0 的蓬勃发展 ,互联网正逐步融入人们的日常生活之中,深刻地改变着人们工作和生活的方式,这使得面向互联网的社会网络分析成为新的研究热点.随着数据挖掘技术的进步,研究者从互联网上挖掘的数据规模也在快速地增长.与其他领域的网络研究一样,社会网络分析也面临着数据规模急剧扩张的挑战.研究者通常将社会网络视为一个图,利用基于图的算法来分析社会网络的性质.而这些分析算法大都依赖于一个基本问题节点间的最短路径的计算.如 20 世纪 60 年代 Milgram1提出

10、的 “ 六度分离 ” 性质 ,就是对社会网络最短路径长度的假设;而近年在Internet 中流行的 “Bacon数” 和“Erd?s数”2游戏 ,以及对 Internet 等大规模网络的网络直径的研究3,都是典型的最短路径查找问题;社会学家提出的度量网络元素重要性的两个性质接近中心性、介数中心性4也是通过元素对最短路径的贡献程度来度量的;许多聚类算法也需要节点之间的距离或最短路径信息5,如 Girvan-Newman算法6等.但最短路径的计算具有很高的复杂性,使得这些分析方法在面向规模较大的现实网络时存在性能问题.在串行计算机上,目前主要有两种解决思路:利用优化算法结构等方法降低算法的计算复杂

11、性;利用启发式等方法限定搜索空间,近似计算最短路径.研究者们提出了各种不同形式的最短路径算法7- 9,由于问题本身的复杂性,目前最快的串行最短路径算法只能将计算复杂性降到O(n2.376)10.因此,如何快速而高效地近似最短路径成为研究者们关注的热点. 在社会网络的研究中,研究者们发现了不同于规则网络或随机网络的一些拓扑特征.如社会网络中往往具有较短的平均路径长度和较高的顶点集聚系数,Watts11提出了小世界模型来刻画这种现象,利用该模型可以较好地解释 “ 六度分离 ” 性质 ;Albert等人12则发现了在大规模现实网络中度分布的无标度现象.研究者们将具有这些特性的现实网络称为复杂网络,并

12、对复杂网络的拓扑特性、构造模型、传播动力学等方面都进行了深入的研究13,也将其成果广泛应用于软件工程等领域14.现实网络往往都具备复杂网络特征,本文利用复杂网络的拓扑特征推导现实网络中最短路径的可能分布.在此基础上,本文提出了基于区域中心点距离的最短路径(centers distance of zone, 简称 CDZ) 近似方法 ,利用复杂网络拓扑特征寻找一条实际存在的路径作为可能的最短路径 ,能够有效地应用于介数中心性等需要最短路径信息的社会网络分析算法的近似计算.实验结果表明,在具有复杂网络特征的网络上,我们的近似分析方法极大地提高了计算速度,而且保持了较高的有效性. 本文第1 节回顾相

13、关工作.第 2 节分析复杂网络拓扑特征对最短路径的影响,在此基础上提出针对复杂网络的最短路径近似算法CDZ. 第 3 节将 CDZ 算法应用到计算机生成网络和真实网络上,以检验 CDZ 算法的性能和正确性 .第 4 节阐述如何结合CDZ 算法近似计算中心性等社会网络性质的方法,并检验网络性质近似的有效性 .最后总结全文,提出一些有待探讨的问题,并展望未来的工作. 1 相关工作目前 ,面向互联网的社会网络挖掘和分析成为了一个新的研究热点.研究者们针对人们在互联网的活动进行挖掘和分析,如邮件交互15、科研合作16等;也研究了面向Web 2.0 的社会网络挖掘方法17,18;并将社会网络分析广泛应用

14、于恐怖袭击分析19、犯罪核心挖掘20等问题 .这些研究与其他现实网络分析一样,面临着网络规模急剧增大的挑战.中心性等网络性质度量方法由于复杂性太高而不能在大规模现实网络上有效应用,其中 ,最短路径的计算带来的复杂性最为显著.因此 ,如何快速而有效地近似最短路径,从而高效地分析网络性质,成为目前研究的一个热点.Chow 等人21提出了利用构建A* 算法的启发式来快速搜索最短路径的方法.Slivkins等人22提出了 Rings of Neighbors方法搜索最邻近节点,并在此基础上提出了基于环的距离近似算法.Rattigan 等人23则提出了图结构索引(network structure in

15、dices,简称 NSI) 算法 ,利用保存的预处理结果快速近似节点间的距离 ,文献 24 将该算法用于图聚类算法的近似,取得了较好的结果.Zwick25提出了t-最短路径近似算法的定义,一个算法被称作是t-近似的 ,是指该算法估算的最短路径都不超过实际最短路径长度的t 倍.Cohen 等人26设计了一种面向加权无向图的近似算法,该算法在2-近似的情况下仅需3 2()O ne 的预处理时间.Thorup等人27提出了 Approximate Distance Oracle数据结构 ,对于 (2k- 1)-近似需要O(kn1+1/k)的空间和O(n1/k)的预处理时间,并能在O(k)的时间内给出

16、任意节点对之间的近似最短路径.Baswana 等人28设计了两种随机近似算法,在非加权无向图最短路径的2-近似问题上具有O(e2/3nlog n+n2)的时间复杂度. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 唐晋韬等:适合复杂网络分析的最短路径近似算法2281 上述方法的设计目标往往面向所有类型的网络,并没有针对复杂网络的拓扑特征进行优化.研究结果29,30表明 ,最短路径算法在具有不同拓扑特征的网络上效率差异很大,通

17、用算法很难在各种网络形式下均有较好的效率 .本文在分析复杂网络拓扑性质的基础上,提出了一种适用于现实网络的近似算法.该算法利用符合复杂网络拓扑特征的一条可能的最短路径估算距离,适用于现实世界中基于最短路径的网络分析方法的近似. 2 CDZ 最短路径近似方法大规模网络中的所有节点对之间最短路径(all-pairs shortest paths,简称 APSP)问题一直是研究者面临的一个挑战 .本节分析了现实网络的复杂网络特性,由此推导了关于复杂网络节点间最短路径特征的一个假设.在此基础上 ,提出了基于区域中心点的最短路径近似算法,并研究了适合于复杂网络的区域中心点选择策略. 2.1 CDZ 算法

18、现实世界中 ,较大规模的网络在结构上往往表现出复杂网络特征,如社会网络、生物网络、Internet 物理网络等等16.复杂网络特征包括小世界特征和无标度特征;小世界特征11说明 ,在复杂网络中,任意节点之间的距离均较短 ,且具有较高的聚集系数.而无标度特征12是指度分布较为符合幂律(power-law) 定律 ,即复杂网络中存在着少量的占支配地位的中心节点,以及大量的不够活跃的普通节点.如在Internet 网页链接结构中,绝大部分网页的链接数不超过4 个,而不到 0.01%的网页占有了80%以上的链接12.本文统计了实验采用的两种现实网络是否同样具有复杂网络拓扑特征,包括科研文献引用网络Co

19、ra 和 Blogger 社会网络 (参见第 3.1 节).Cora 网络为 30 000 节点规模 ,Blogger 网络则包含1 000 多个节点 .本文利用 E-R 模型31分别生成与这两种网络规模基本相同的随机图进行比较,统计结果表明,这些现实网络的确具有复杂网络拓扑特征.如图 1 所示 ,不同于随机网络的正态分布 ,Blogger 网络和 Cora 网络的度分布都表现出了一定的幂律分布特征.而 Blogger 网络和 Cora 网络平均距离仅为3 和 5,明显小于相同规模随机网络的平均距离(6 和 13). Fig.1 Degree distribution curve of rea

20、l-world networks and random network 图 1 现实网络与相同规模的随机网路的度分布曲线复杂网络拓扑特征体现了现实网络中最短路径的一些内在规律.不同于随机网络,复杂网络的大部分节点都只在小范围内相互连接,呈现出一定的高聚集系数特性.不同于规则网络,复杂网络任意两个节点间的距离都较短 .复杂网络直径较小的原因在于少量连接不同簇的“ 长边 ”,社会学家 Granovetter 提出了弱链接的强度32,描述了在人际关系中少量跨越交际圈的较弱关系对交际网络的巨大贡献.这说明 ,最短路径通过“ 长边 ” 的可能性非常大 .而复杂网络的无标度特征说明节点的度数分布不均衡,存

21、在少量具有很高度数的中心节点以及大量度数很低的普通节点.这说明 “ 长边 ” 属于少数的中心节点的概率更大,任意节点之间的最短路径很有可能通过中心节点 .因此 ,本文提出了在现实网络中关于最短路径规律的一个假设: 假设 1. 在具有复杂网络特征的现实网络中,大部分节点都是经过中心节点连接在一起的,任意节点之间的最短路径有较大的可能会经过中心节点. 该假设在很多现实网络中可以找到佐证,如在 Internet网络中 ,绝大部分的节点是个人电脑终端,它们之间E-R random graphBlogger 3002001000Numberofvertices0 20 40 60 80 100Degre

22、e 5000200010000Numberofvertices0 20 40 60 80 100Degree E-R random graph Cora 30004000名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 2282 Journal of Software软件学报 V ol.22, No.10, October 2011 主要通过路由器连接.在性接触网络33和科研合作网络16中也发现了类似的特点.根据假设1,在 NS

23、I 方法23的基础上 ,本文提出了一种基于区域中心点的最短路径近似方法CDZ 方法 .在预处理时 ,该方法查找中心节点并记录各个节点到最邻近中心节点的最短路径;在估算最短路径时,该方法利用通过中心节点的一条路径近似最短路径 .在无向图情况下,CDZ 方法的预处理包括以下几个步骤: (1) 根据某种节点选择策略(本文策略见第2.2 节)选取 d 个可能的中心节点,表示为 C1,C2, , Cd; (2) 从中心节点集合开始,宽度优先遍历整个图,记录每个节点到最临近中心节点的最短路径、相邻区域 (两个区域有节点直接相连)中心节点之间的最短路径.该步骤将图划分为d 个区域 ,记为12,.,.dCCC

24、ZZZ (3) 新构造一个仅包含d 个中心点的图,如果原图中两个中心点所在区域相邻,在新图中添加一条连接这两个中心节点的边,边的权值为步骤2 得到的在原图中两个相邻区域的中心节点之间的距离.计算新图中所有节点之间的最短路径,通过映射可以得到原图任意两个中心节点之间的最短路径. CDZ方法利用通过中心节点的一条实际存在的路径近似跨区域节点之间的最短路径.任意两个属于不同区域的节点s,t 之间的距离 ,可以近似为这两个节点到各自区域中心节点的距离与中心节点之间的距离之和.d(s,t)=d(s,Cs)+d(Cs,Ct)+d(Ct,t) (1) 其中 ,Cs,Ct分别为距节点s,t 最近的中心节点,函

25、数 d(s,t)为节点 s和节点 t之间的距离 .属于不同区域的两个节点s,t 之间的距离d(s,t),CDZ 方法利用一条通过中心节点的路径长度来近似:从节点s 到其中心节点Cs的距离d(s,Cs)、从节点t 所在区域中心节点Ct到 t 的距离 d(Ct,t)以及中心节点之间的距离d(Cs,Ct)之和 . 如果两个节点属于同一区域,通过两个节点到中心节点的路径信息可以快速地发现它们的最近公共祖先(least common ancestors).本文利用两个节点通过其最近公共祖先的一条路径,近似它们之间的最短路径.对于属于同一区域的节点s,t,Cst为区域的中心节点,LCAst为 s,t 的最

26、近公共祖先,s,t 之间的距离可以近似为d(s,t)=d(s,LCAst)+d(LCAst,t) (2) 如果 s,t 的最近公共祖先是它们中间的一个,那么近似公式(2)给出的近似路径即为最短路径.与常见的随机方法不同,CDZ 方法利用复杂网络的高聚集特性来划分图的区域.在最短路径的近似上,该算法利用了复杂网络的小世界特性和无标度特性,认为复杂网络中最短路径有较大可能会经过中心节点.近似公式(1)、近似公式 (2)在给出节点距离的一个近似值的同时,也提供了一条图中存在的可能最短路径. 2.2 区域中心点的选择策略影响 CDZ 近似方法有效性的一个核心因素是区域划分,CDZ 方法的准确性很大程度

27、上取决于划分的区域是否符合网络的拓扑结构.CDZ方法利用基于中心节点集合的宽度优先算法划分区域,如何构造适合复杂网络的中心点选择策略成为CDZ 方法需要解决的一个核心问题.在社会网络的常用分析手段中,局部中心性 (local centrality)34通过统计与节点相连的边数来度量节点的重要性.该性质能够度量在局部环境中处于“ 核心 ” 位置的点 ,测量方法也只需要利用到节点的度数,计算复杂度较低.因此 ,我们选取局部中心性最高的一系列节点作为 CDZ算法的区域中心点.在此度量方法下,中心点选择策略还需要考虑区域的划分粒度,即中心点的数目.选择合适的中心点数目能够将网络划分为符合实际拓扑结构的

28、区域,进而能够有效地拟合节点间的最短路径,对CDZ 方法的性能也会产生较大的影响. 复杂网络一般都具有无标度特征,即度的分布较为符合幂律分布.在具有无标度特征的网络中,存在少量有着较高度数的活跃节点,而大部分节点往往只有一两个邻居节点;如在科研文献引用网络Cora 中,度数最高的20%的节点的度数之和就达到了网络总度数的75.6%.因此 ,在复杂网络中,只需选择局部中心性最高的少量节点就能使划分的区域很好地符合网络拓扑特征.节点的度数是由与之相连的边的数目来决定的,我们认为 ,在所选取的中心点的度数之和接近或达到全图度数之和的50%时,绝大部分边都会与中心点相连接.如在 Cora 网络中,当选

29、择的中心点集合度数达到全图的50%时,与中心点集合相连的边占到了全部边的83%以上 ;而在图 1 所示的随机网络中,这个比例仅仅达到51%.此时 ,CDZ算法在遍历中心点时就覆盖了复杂网络的绝大部分边,构建的结构索引更符合实际的网络结构.根据复杂网络的无标度特性,大部分复杂网络的度数均符合或接近幂律分布 ,即 y=cx-r,而社会网络的幂率r 往往在 23 之间12.如果中心点集合的度数大于总度数的50%,则需要选择名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页

30、 - - - - - - - - - 唐晋韬等:适合复杂网络分析的最短路径近似算法2283 的节点数目一般不超过总节点数的10%.因此 ,CDZ 方法的中心节点选择策略如下: (1) 将节点按照局部中心性大小进行排序,得到排序后的节点队列Q; (2) 取出队列Q 中的第 1 个元素 ,加入中心点集合C; (3) 如果中心点集合C 中所有节点的度数之和大于全图度数之和的50%,或中心点集合的大小超过了全图节点总数的10%,则终止循环 ;否则 ,继续执行第2 步; (4) 输出中心点集合C,此时 ,C 中所有元素就是本文策略选择的中心节点. 在近似节点间的距离时,CDZ 方法仅需要常数时间.但预处

31、理步骤中的图遍历需要O(e+nlogn)的开销 ,其中 , e 为网络边的数目,n 为节点数目 .预处理步骤3 将所有中心点抽取成一个加权网络,利用经典的最短路径算法计算中心点之间的距离需要O(d3)的时间 ,其中 ,d 为中心点数目;选择中心节点需要O(nlogn)的时间 .因此 ,CDZ 方法预处理的计算复杂性为O(e+nlogn+d3),其中 ,e 为网络边的数目,n 为节点数目 ,d 为选择的中心节点数目.在具有无标度特性的网络中,高度数节点的数目非常少,即 d 远远小于n.因此 ,在具有复杂网络特征的网络中,CDZ 方法的计算复杂性仅为O(e+nlogn).如果图的规模较大或无标度特

32、征不明显,则仍可能由于d 较大而使得精确计算所有中心点之间最短路径的时间开销过大.在中心点规模大于500 的情况下 ,我们同样采用CDZ 方法近似计算中心点之间的最短路径,以取得性能和正确性之间更好的平衡. 3 最短路径近似评测作为很多网络性质的度量基础,近似算法对最短路径估算的准确性和效率直接影响到网络近似分析的性能.在本节中 ,我们在各种网络上评估了CDZ 近似算法的有效性,并分析了影响算法正确性与性能的因素. 3.1 数据集本文使用了科研文献引用网络Cora35和搜狐博客(http:/ 社会网络 Blogger 来评测算法在现实网络中的有效性.作为一种常用的关系数据,Cora 包含了在信

33、息处理等领域的近37 000 篇科研文献以及文献之间的100 000多个引用关系.我们将每篇文章作为一个节点,如果文章之间有引用关系,则在对应节点之间添加一条边 .通过这些步骤,我们得到了一个包含30 751 个节点及134 996 条边的科研文献引用网络,本文称其为Cora 网络 .此外 , 我们也抓取了搜狐博客的部分数据,共收集到了1 327个博客的 20 166 篇文章 .将每个博客表示为图中的一个节点,如果博客之间存在着表示阅读、评论、引用、交友的链接,就在对应的节点之间添加一条边.去除了孤立节点后,生成了规模为1 113 个节点和3 685 条边的无向图,本文称其为Blogger 网

34、络 . 为了全面评测CDZ 方法的近似效果,本文利用经典的网络模型生成了3 种具有不同结构特征的网络:根据Erd?s 模型31生成的随机网络,根据 Eppstein 幂律模型36生成的幂律网络以及根据Barabsi模型12生成的无标度网络 .随机网络属于简单网络,而后两种生成网络都有着显著的无标度特征.为了便于统计性质的直观比较,3个生成网络的规模与Cora 网络基本相当.这些网络的统计性质见表1. Table 1 The statisitical features of the networks used in the expermiments表 1实验所用网络的统计性质Network Co

35、ra Blogger Random Power-Law Scale-Free Nodes 30 751 1 113 29 999 30 000 30 000 Average degree 8.78 6.62 9.01 6.0 8.36 Diameter 19 10 32 24 26 Average distance 5.42 3.36 12.6 5.98 7.51 3.2 评测方法本文采用了Dijkstra算法的Fibonacci 实现30作为距离的基准算法,该实现具有O(en+n2log n)的时间复杂度.本文采用该算法计算的距离作为标准答案评测近似算法的准确率,根据它的计算时间评测近似算法

36、的实际性能 .作为对比 ,本文还实现了两种知名的最短路径近似方法,包括Baswana 提出的随机化近似方法28(简称Baswana 方法 )和 NSI 近似方法中近似效果最好的DTZ 方法23,以验证我们提出的近似方法的有效性. 平均路径比 (PathRatio)23常用于度量距离近似方法的正确性.给定图G,从中随机选择r 对节点 ,对于任意名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 2284 Journal of Sof

37、tware软件学报 V ol.22, No.10, October 2011 节点对 i,分别计算出精确距离ioP 和近似距离ifP .在此基础上 ,可以定义平均路径比P: 11.iirrfoiiPPP=由定义可知 ,平均路径比P 的值越接近1,最短路径近似算法的准确性就越高.P 的值与1 的差距越大 ,说明近似结果和实际距离的偏差越大.为满足实际应用需求(如在路径导航问题中,用户能够接受比最短路径偏大的实际路径 ,而不能接受小于最短路径的不存在的一个近似解),常见最短路径近似方法(包括本文提到的几种方法)都要求近似结果不小于实际距离,所以平均路径比不会小于1.CDZ 方法使用通过中心节点的一

38、条实际存在的路径近似最短路径,这条路径的长度也不会小于最短路径的长度,其平均路径比同样不小于1. 3.3 结果与分析首先 ,我们测试了几种近似方法的准确性.CDZ方法利用复杂网络结构特性划分区域,不需要输入参数. DTZ 方法需要确定划分的区域数目和区域划分次数,本文中设定为10%和 5.Baswana 方法需要指定概率p 将节点加入样本集,本文中 ,p 设定为 0.2.几种近似方法在各种类型网络上的正确性评测结果见表2. Table 2 The PathRatio measure of the approximate algorithms in different networks表 2近似

39、算法在不同网络上的PathRatio 值Algorithm Random Power-Law Scale-Free Cora Blogger CDZ 1.454 1.103 1.172 1.018 1. 020 DTZ 6.412 6.246 6.600 5.549 5.648 Baswana 1.124 1.211 1.222 1.160 1.092 如表 2 所示 ,CDZ 近似方法和Baswana方法相对于DTZ 方法更为精确.如在估算随机网络中节点的距离时, CDZ 方法和 Baswana 方法的平均路径比分别为1.454 和 1.124,而 DTZ 高达 6.412.这是因为 DTZ

40、 方法利用泛洪算法随机划分区域;为了避免随机划分引入的距离偏置,DTZ 方法需要多次划分区域,并叠加每一种划分情况下的距离近似值.这在消除了随机偏置的同时,也使得估算距离远大于实际的最短路径长度.CDZ近似方法和Baswana 方法在各种网络上均达到较高的近似水平;但 CDZ 方法在 Cora 网络和 Blogger 网络中的近似准确性明显高于Baswana 算法 ;而在具有无标度生成网络中,CDZ 方法也要好于Baswana 算法 .如在 Barabsi无标度网络上 ,CDZ 方法的平均路径比达到了1.172,而 Baswana 算法为 1.222.这是因为Baswana 利用随机化的方法挑

41、选“Sample”节点 ,具有较好的通用性,却没有针对现实网络的特征进行优化;而 CDZ 方法是以复杂网络的结构特征为假设基础,认为在复杂网络连通性方面起重要作用的“ 长边 ” 往往与中心节点相连.在具有无标度特征的网络中,少量的中心节点占有了大部分的边,符合CDZ方法的假设.而现实网络大都具有无标度等复杂网络特征 ,所以 CDZ 方法更适合于现实复杂网络的最短路径的近似. 本文也在2 000 个节点规模的Cora 子网络上测试了CDZ 方法中心节点选择策略对近似正确性的影响 .本文采用随机方法作为对比策略,以 2为间隔 ,从 20400 设置中心点数目,计算不同的中心点情况下CDZ 方法的准

42、确性.如图 2 所示 ,基于局部中心性的选择策略在CDZ方法上整体表现出较好的近似准确性,而随机选择策略则有着较大的偏置 .这说明 ,基于局部中心性划分的区域更符合现实网络的拓扑结构特征.而选择不同的中心点数目,对距离估算的准确性也有较大的影响.在随机选择策略中 ,CDZ算法的近似准确率随着中心点数目的变化出现了较大的随机波动.基于局部中心性的选择策略在中心点数目很少时,对距离的估计偏大;而随着中心点数目的增加,估算距离快速地逼近实际距离.在中心节点数Local centrality Random selection0 100 200 300 4002.52.01.51.00.50.0Path

43、RatioNumber of centers Our strategyFig.2 Influence of center selection strategy on CDZ 图 2 中心节点选择策略和对CDZ 方法的影响名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 唐晋韬等:适合复杂网络分析的最短路径近似算法2285 目为 4050 时,估算距离基本与实际距离一致,本文第 2.2 节设计的中心点数目选择策略选择的节点数目为5

44、6,对应的平均路径比为1.026.随着节点数目的增长,偏置程度仍会缓慢地缩小.这是因为 ,随着中心节点数目的增加,每个区域的规模变小,节点之间的近似路径越来越接近于区域中心点之间的最短路径;而区域中心点之间最短路径是通过Dijkstra算法得到的 .因此 ,随着中心节点数目的增加,近似准确性会缓慢地得以提升,但计算代价也会急剧增大.而本文中心点选择策略使得中心点数目较小且估算结果较为正确,同时满足了计算距离的性能和准确性的要求.在性能方面 ,几种最短路径算法的计算复杂性见表3.CDZ 近似方法和DTZ 方法在时空开销上都要远远小于经典的距离计算方法,但 Baswana 方法的预处理复杂性非常高

45、,仅比Dijkstra方法的Fibonacci实现略好 ; Baswana 方法的时间复杂性依赖于节点数目n 以及边的数目e.CDZ 方法的时间复杂性线性地依赖于节点数目n、边的数目e 以及选择的中心点数目d.DTZ 方法的时间复杂性则依赖于图中边的数目e 与选择的区域数目d以及区域划分次数k 的乘积 .正如第 2.2 节所分析的 ,如果网络具有无标度特征,则本文策略选择的中心点数目d远远小于节点数目n.在这种情况下,CDZ 方法仅仅需要O(e+nlog(n)的计算时间 . Table 3 The computational complexity of the (approximate) sh

46、ortest-paths algorithms表 3距离计算与近似算法的时空复杂性Algorithm Time Space Dij. O(n2logn+en)O(n2) CDZ O(nlogn+e+d3)O(n+d2) DTZ O(ekd)O(n+d2) Baswana O(e3/2nlogn+n2)O(n2) 在普通台式机上(2GHZ CPU,2G 内存 ),几种算法的Java实现在 Cora 网络和 E-R 随机网络不同规模子网络上的实际所用时间如图3 所示 . Fig.3 Run time of different approximate algorithms on Cora and B

47、logger network 图 3 几种距离计算方法在Cora 和 Blogger 两种网络上的实际执行时间通过图 3 可以发现 ,与其他几种算法相比,CDZ 方法具有非常明显的性能优势. Dijkstra 方法的 Fibonacci 实现的性能曲线表明,即使面对中等规模的网络,传统的精确算法也不能在工程应用可以接受的时间内计算出结果.Baswana 方法在网络规模较小时,近似计算性能最好;但随着网络规模的增大,该方法所需计算时间急剧增加;在网络规模大于10 000 个节点后 ,该方法的计算时间开销在几种近似方法中最大.这是因为 ,Baswana 方法需要做多次的宽度优先遍历保存图的结构信息

48、,以确保近似路径长度不超过实际路径长度的2 倍.DTZ 方法的预处理时间开销也要高于CDZ 方法 ;为了避免随机划分的影响,DTZ 方法需要多次划分区域并根据每次的近似值综合估算距离;多次区域划分大大地增加了DTZ 方法的时间开销.而 CDZ 方法利用局部中心性划分区域,能够较好地符合实际复杂网络的拓扑结构,因此不需要多次划分区域来避免结果的偏置.在 Cora 等具有无标度特征的网络中 ,根据本文的中心点选择策略,我们仅需选择非常少的中心点,这也使得CDZ方法预处理时间大为降低.而在随机网络上,由于节点度分布较为均衡,CDZ 方法会选择较多的节点作为中心节点,使得 CDZ 方法的性Dji. D

49、TZ CDZ Baswana0 5000 10000 15000 20000 25000 300006543210log10(time)Network scale Cora network 0 5000 10000 15000 20000 25000 30000 6543210log10(time)Network scale Blogger network Dji. DTZ CDZ Baswana 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - -

50、- - - - - 2286 Journal of Software软件学报 V ol.22, No.10, October 2011 能有所降低 .如在 20 000 个节点的随机网络上,CDZ 方法需要近60s;而在同样规模的Cora 子网络上 ,CDZ 方法仅需 20 余秒 .综合性能和准确率考虑,我们认为 ,CDZ 方法更加适合具有无标度特征的复杂网络的最短路径近似;如果对近似精度要求较高而网络规模又不大,则可以使用Baswana 方法 ,但该方法不适合较大规模现实网络的最短路径近似计算. 4 社会网络性质近似个人或组织在其社会网络的中心度是社会网络分析的初始研究目标之一,也一直是研究