利用节点效率评估地理网格网络的鲁棒性*

王蕾蕾，林中材，潘佳庆，杨孔庆，邹卫东

(集美大学 理学院，福建 厦门 361021)

1 引 言

自1999年美国圣母大学物理系Barabási教授及其博士生Albert提出网络的无标度性质以后，复杂网络理论发展迅速且应用广泛，从Internet到WWW网络，从大型电力网络到全球交通网络，从科研合作网络到各种经济、政治、社会关系网络等。随着复杂网络研究的深入，复杂网络的抗毁性研究的重大意义和应用价值日益凸显出来，由于网络的抗毁性与系统的可靠性密切相关［1］，而大部分复杂网络是由少数集散节点主控的系统。因此，确定合理的评估指标，发掘网络中的重要节点具有重要的实用价值，尤其是对各种具体的实际网络，更能针对性的分析网络性质，制定正确的策略和措施。

评价复杂网络中节点重要性的方法很多，但其本质均是源于图论以及基于图的数据挖掘，对应于图论中的关键节点和关键边问题［2］。本文研究的是与地理距离有关的网格网络，采用节点效率指标来衡量网络节点的重要性。用节点效率对节点重要性进行评估既考虑了网络的局部影响性，又考虑了网络的全局影响性。在一定攻击策略下，文献［1］通过度量网络不连通时失效节点的比例来衡量网络功能的鲁棒性。文献［3］和文献［4］采用网络中连通节点所占的比例和节点对之间最短路径的分布来衡量网络的鲁棒性，认为连通节点的比例值越大，节点之间最短路径越短，该网络的可靠性越强。文献［5］用最大连通图的相对大小和平均路径长度L与去除节点数占原始网络节点数的比例f的关系来度量网络的鲁棒性。文献［6］以节点删除造成全网络效率下降程度来度量网络的鲁棒性．本文采用文献［1］提出的度量网络不连通时失效节点的比例来衡量与地理距离有关的网格网络的鲁棒性。通过实验分析验证其有效性和可行性。

2 复杂网络功能鲁棒性的评定

2．1问题的提出

随着科学技术的发展，交通工具的不断推陈出新，速度变得越来越快，世界变得越来越小，人类越来越希望自然界以简单清晰的姿态呈现出来，例如沿着一条公路少过几个路口，少等几个红绿灯、少换几次交通工具就能到达目的地;如何确定一个城市中交警的执勤点，保证能在有效的时间内到达报警点或成功拦截逃犯;如何为商场、大型超市选址，在满足更多市民需求的同时获取最大商业价值等。节点效率表达了一个节点与其他节点的平均接近程度。节点效率越高，表明在最短路径上经过其他节点的个数就越少，向其他节点传播信息越容易。从节点效率的意义可以看出节点效率指标能较好的评估这方面的问题。本文研究的是与地理距离有关的网络，而带权重连接的嵌入式无标度网络模型(Weighted Lattice Embedded Scale－free(WLESF))正好能体现这一类网络。因此，我们可把实体红绿灯、路口、公交车站牌、车站、机场等看做网络中的节点，其路径看做节点与节点之间的边。

2．2网络中关键节点的评价标准

2．3 理论基础

设图G=(V，L)是一个无自环的无向网络，其中V={v1，v2，…，vn}是网络中所有节点的集合;L={l1，l2，…，ln}且L∈V×V是节点边的集合。

定义1节点度是指与该节点直接相连的节点的数目，目前普遍认为节点的重要性与其度值有很大的关系，所以节点的度值能直接反应节点在整个网络中的影响力。

定义3节点效率是指节点与网络中其他节点之间距离倒数之和的平均值，即

从Ik的定义中可以看出，节点效率表达了节点到网络中其他所有节点的平均难易程度，网络中节点效率越高，表明该节点向其他节点传输信息越容易，所消耗的资源越少，该节点越重要。

3 模型的建立［7］

本文主要研究的是与地理距离有关的网络。考虑到很多现实的网络都具有马太效应，所以在构建模型时不但要考虑空间地理因素的影响也要考虑马太效应的影响，即节点间的连接主要考虑节点本身度的大小以及节点间的地理距离。为探讨这两个因素的影响，在模型中引进参数α来调节控制节点的度权重与地理距离权重的比重。该模型的构建具体分以下几个步骤：

(1)初始网络：给定大小为L×L正方形二维网格，给定m0个节点随机嵌入在网格的格点上，这m0个节点全连接(m0选取远远小于网格格点数);

(2)网络进入演化阶段：在每一单位时间网络都增加一个新的节点，并嵌入到二维正方形网格中，且每个网格最多只能有一个节点，直到嵌入的节点布满整个二维网格。每个新增节点在网格上的位置是随机选取的，且这个新增的节点与原有网络中的m(m≤m0)个节点相连(禁止重复连接和自身连接)，连接的概率取决于这两个节点间的地理距离和待连接节点的度，具体按下面的第(3)步骤进行;

(3)其一：在许多自然过程和科学领域中，高斯形式普遍存在，因此在考虑空间地理距离的影响时，我们取高斯函数作为地理距离的权重函数(PiD)：

设某时刻网络有N(t)个节点，其中第j个节点被待增加的第i个节点连接的距离权重连接概率为：

其二：考虑节点度权重连接概率(PBA)：

设某时刻网络有N(t)个节点，其中第j个节点被待增加的第i个节点连接的度权重连接概率为：

综合考虑地理距离权重和节点度权重，引进调节参数α(0≤α≤1)使得节点间的连接概率为：

由(3)式知，当参数α从0增大到1可由嵌入式无标度网络渐进过度到嵌入式指数网络。若连接概率完全由地理距离权重决定，当最近临连接时(A=1)，网络的度分布满足指数分布，所以当A=1，α从0逐渐增大到1时，网络的度分布是从幂律分布逐渐过渡到指数分布，如图1;α当 =1时，A从1逐渐增大到100时，其分布逐渐偏离指数分布，如图2。

4计算机模拟的结果及分析

Fig1：度分布图，A=1，α =0，0．5，1．网络总节点数N=10000，L=100，m0=4，m=3．每个数据点是在给定参数下重复生成80次网络并对度分布求平均后的结果(除非特别声明，以下数据也是如此生成)

Fig2：度分布图，α =1，A=1，20，30，100．

Fig3：节点效率分布图：A=1，α =0，0．5，1．

Fig4：节点效率分布图：α =1，A=1，20，30，100．

对比图1和图3、图2和图4，我们可以看出，度分布和节点效率分布基本一致，即A=1时，随着参数α从0到1，节点效率分布从幂律分布逐渐过渡到指数分布。当α=1，即节点的连接完全由地理距离概率决定时，参数A从1增大到100，节点效率分布逐渐偏离指数分布。这是因为节点度的大小与节点效率的大小有直接关系。节点的度越大，其邻居节点就越多，该节点到达其他节点的距离越短，节点效率就越高。当参数A=100时，节点的连接范围基本不受地理距离的限制，由地理连接概率可以看出，节点与其临近的节点连接的概率更大，节点距离减小，节点效率变大，从而导致不存在节点效率较小的节点，如图4。

Fig5：最大节点效率Imαx随A的变化情况。

Fig6：最大节点效率Imαx随α的变化情况。

节点效率的最大值Imαx对网络的拓扑性质有很大影响，例如实际中的发电站，离附近居民的平均距离越短，为居民提供最大方便的同时所消耗的资源就越少。从图5可以看出，对于给定的α，随着A的增大，节点效率的最大值Imαx相应减小，当A＞60时，节点效率的最大值Imαx趋于稳定。这是因为当A＞60时，节点的连接几乎不受地理距离的影响，度分布更加均匀，节点到达其他节点的难以程度更加接近，节点效率分布也更加均匀。从图6可以看出，对于给定的A，随着参数α的增大，节点效率的最大值Imαx逐渐减小。这是因为随着参数α的增大，地理距离所占的比重增加，马太效应减弱。本来度大的节点增加的概率减少，导致度大的节点的度减小，其邻居个数也相应减少，导致该节点到达其他节点的距离增大，节点效率减小．

Fig7：节点效率攻击，直到网络不连通时网络节点的打击规模f随参数A的变化。

Fig8：节点效率攻击，当α=1，A=100时和随机攻击作比较

从图7中可以看出，α固定，随着参数A的增大，网络能够承受的打击次数在不断增加。当A＞50，网络能够承受的打击次数基本趋于稳定，这是因为随着参数A的增大，节点的连接范围基本不受地域的限制，节点效率分布更加均匀。当网络连接概率PD=1时，即网络节点的连接全部由地理连接概率决定，参数A＞30时，采用节点效率进行攻击，网络能够承受的打击次数和随机攻击相当，如图8。这说明加入地理距离连接概率的网络更接近真实网络，这与自然科学中高斯形式普遍存在相吻合。

5 结 论

本文采用节点效率指标对网络节点的重要性进行评估，既考虑了节点失效的局部影响性，又考虑了节点失效的全局影响性。基于本文所研究的模型，实验结果分析表明，节点效率分布和度分布基本一致，采用删除节点效率高的节点，直到网络不连通时的打击规模与度指标也基本一致，但和随机攻击相比却具有较大的优越性。所以在类似本文构建的与地理距离有关的网格网络时，我们可以用度这个简单又重要的指标对网络节点的重要性进行衡量。但并不代表度可以代替节点效率来衡量网络节点的重要性。例如度大的根节点，到达其他节点的平均距离并不一定小，节点效率不一定大。总的来说，本文研究的与地理距离有关的网络对蓄意攻击鲁棒性较低，对随机攻击具有较强的容错性，这与网络鲁棒性评定的经典结论［8，9］是一致的，这也证明了利用节点效率衡量节点重要性的有效性。

［1］周璇，张凤鸣，周卫平，邹伟．物理学报，Acta PhysSin-Vol61，No19(2012)190201

［2］郭世泽，陆哲明．复杂网络基础理论［M］．科学出版社，2012：247

［3］Morohosi H 2012 Mathematics and Computers in Simulation 81 551

［4］Nair A，Vidal JM 2011 International Journal of Production Research 49 1391

［5］Albert R，Jeong H，Barabási A L，Attack and error tolerance in complex networksNature，2000，406：387 ～482

［6］王林，戴冠．复杂网络的Scale－free性、Scale－free现象及其控制［M］．北京：科学出版社，2009：137

［7］陈进良．与地域相关的类BA模型的构造及其应用［D］．2011：23

［8］Paul H，Seth B 2008 Proc．of the 41st Annual Hawaii International Conference on System Sciences Hawaii，January 7－10，2008 p1

［9］Albert D J，Strogatz SH 1998 Nature A 393 440