不同信息条件下加权复杂网络抗毁性仿真研究
2013-09-12王甲生吴晓平陈永强
王甲生，吴晓平，陈永强
(海军工程大学信息安全系，湖北 武汉，430033)
复杂网络作为复杂性科学的一个重要研究领域，近年来受到数学、物理学、生物学、社会学、信息科学以及军事和经济学等各学科领域研究人员的广泛关注[1]。随着复杂网络研究的兴起，复杂网络的抗毁性研究备受关注。复杂网络抗毁性是指网络中的节点(或边)在发生随机失效或遭受故意攻击的条件下，网络维持其功能的能力。对复杂网络的抗毁性进行研究有助于正确认识网络的抗毁性状况，对于保证网络的安全稳定运行具有重要的理论价值，对于网络的优化设计也具有重要的指导意义[2]。对复杂网络的抗毁性研究主要采用仿真与解析的方法，分析网络拓扑结构及特征参数与其抗毁性之间的关系，进而通过优化网络拓扑结构和匹配特征参数，达到提高抗毁性的目的[3-8]。在加权网络中，权重为刻画网络性质提供了一个新的方法，也为优化网络性质及功能提供了新的手段。目前，针对加权网络拓扑结构、权重分布以及网络上的物理过程等对网络功能的影响研究有了一些有影响力的成果[9-14]。Barrat等[9-10]研究了国际航空网与科学家合作网2个典型的加权网络，分析了刻画网络权重特性以及权重与拓扑结构相互作用关系的特征参量，为研究实际加权网络的特性提供了一个新的视角。Li等[11]研究了科学协作网络中权重的度量以及权重重分配对于网络性能的影响。田柳等[8]通过改变权重分布形式考察了权重分布对加权网络效率的影响。Li等[12]研究了规则网络上的权重随机化出现的小世界现象。Li等[13]研究了在规则网络上通过权重随机化加强网络同步的方法。Wang等[14]研究了加权网络对抗级联失效的普适特性，等等。从加权网络抗毁性的角度来看，目前的研究尚存在以下问题：加权网络权重的重分布不能找到很好的应用背景，考虑到成本与效率，实际网络并不适用于进行权重分布以获得较好的抗毁性或其他特性；另外，目前对于加权网络中边权的赋予方式缺乏现实依据，且针对加权网络静态抗毁性的文献尚不多见。现实生活中的许多网络如因特网、科学协作网和国际航空网等都具有明显的无标度特性，而无标度网络面对不同的攻击策略时会表现出不同的抗毁性。鉴于此，本文重点研究了加权无标度网络的抗毁性，以期得到网络拓扑参数、权重系数与抗毁性之间的关系，从而为现实网络的抗毁性优化设计提供一定的参考和借鉴。本文首先分析加权网络中边权的赋予方式以及网络性能的度量指标，然后采用数值仿真的方法研究加权网络权重系数和网络密度等参数对不同信息条件下加权网络抗毁性的影响，最后对加权网络的抗毁性进行定量分析，给出不同信息条件下网络抗毁性的优化策略。与通过权重随机化以及改变权重与边匹配关系等提高加权网络抗毁性的方法相比，本研究的方法更具可行性且能针对不同的信息条件，从整体上把握网络的抗毁性状况。
1 加权复杂网络分析
人们对复杂网络的早期研究主要集中在无权网络方面，然而，在实际网络中，节点之间的关系呈现出丰富的多样性，如果忽略了节点之间相互作用的差异性，就会失去很多重要信息。给网络中的每条边都赋予相应的权值，无权网络就成为加权网络。加权网络为描述节点之间的关系和相互作用提供了更加细致的刻画手段，且权重及其分布也会对网络的性质和功能产生重要影响。因此，加权网络已经成为复杂网络的一个重要的研究领域。
加权网络可以用图G=(V,E)来表示，其中，G是1个无向连通图，有n个节点和m条带权重的边；节点集V=(v1,v2, …,vn)，边集E=(e1,e2, …,em)。一般用权重邻接矩阵W=(wij)n×n表示加权网络的权重，其中，元素wij表示以节点vi与vj为端点的边eij的权重，当网络中各条边的权值都相同时，加权网络即退化为无权网络。
加权网络研究需要考虑的第1个问题就是边权的赋予方式。权重代表的是节点间相互作用的关系与强度，以往的权重模型主要有 YJBT模型、AK模型以及 BBV模型等，这些权重模型尚待实际网络数据验证。本研究考虑了一种将无权网络的性质转化为边权的赋权模型，在文献[9]的基础上，边权的赋予方式如下：假设网络中边eij连接的2个节点vi与vj的度值分别为ki和kj，那么，该边的权重为wij=(ki kj)θ，其中θ是一个可调的权重系数，用于控制边权强度。这种边权赋予方式是有实际网络的观测数据作支撑的；另外，加权网络中边的介数与其端节点度的乘积是正相关的[4]。因此，本研究的边权模型与基于负载的权重模型也是一致的。
2 网络性能度量指标
为了研究加权网络的抗毁性，首先需要选择合适的网络性能度量指标。Albert等[3]在对无标度网络鲁棒性的仿真研究中，采用最大连通子图的相对大小和平均路径长度来度量网络的抗毁性。对加权网络而言，网络攻击带来的影响主要包括2个方面：一是网络的连通性遭到破坏，二是网络的信息传输效率下降。目前，网络直径、平均路径长度和网络效率等常用来衡量网络的传输性能，连通性和最大连通子图的相对大小等指标则用来衡量网络的连通性。本研究从网络传输信息的有效性和网络抵抗攻击的连通性能2个方面出发，采用网络效率和网络鲁棒性作为加权网络抗毁性的度量指标[15]。
2.1 网络鲁棒性
连通性是网络的重要性能指标之一。网络鲁棒性用来衡量网络遭受攻击时剩余节点之间仍能保持连通的能力。由此，网络鲁棒性可定义为移除任意节点后，网络中仍连通的节点对与网络总节点对的比值。假设移除节点后的网络为G′，则网络鲁棒性δ可表示为
式中：lij为连通系数，当节点vi与vj之间连通时，lij=1，否则lij=0。网络鲁棒性δ描述了网络在遭受外界干扰或破坏时的连通性，反映了网络结构本身对于攻击的抵御能力，克服了最大连通子图的相对大小不能反映网络受到攻击后子网络的连通情况的缺点。
2.2 网络效率
在无权网络的研究中，平均路径长度L常用来描述网络的连通性能和效率，本文采用网络效率作为加权网络抗毁性的度量指标。网络效率衡量的是信息在网络上传播的有效程度，Crucitti等[6]最早给出了一个基于平均最短路径的网络效率E的定义：
式中：dij为节点vi与vj之间的距离。在加权网络中，网络效率可表示为边权的函数。若网络中2个节点之间的距离越近，则直观上信息在这2点之间就越容易传播，网络的传播效率就越高。因此，当网络的权重为相异权时，网络效率E可以定义为边权的倒数平均值。特别地，当2个节点之间不连通，即当wij→∞时，仍可定义节点之间的效率eij→0，克服了平均最短路径和网络直径等指标不适用于非连通网络的缺点。加权网络中所有节点对的效率均值即为网络的全局效率Eg：
以上给出了针对相异权的网络效率定义。由于相似权与相异权在一定程度上可以相互转化，因此，此处仅考虑相异权的情况。
3 抗毁性仿真研究
加权网络的性能变化是与权重系数θ密切相关的，其抗毁性分析较为复杂，要给出准确的解析分析十分困难。因此，采用数值仿真的方法来研究加权复杂网络的抗毁性与网络参数的关系。
首先，构建加权复杂网络。本节的分析是基于加权 BA无标度网络的，根据文献[17]给出的方法构建BA网络，其初始节点数n0=5，m=4，节点总数N=1 000，网络的构建依赖于择优吸附机制。然后，对BA网络进行赋权，其中权重系数θ在{0.2, 0.5, 0.8, 1.0, 1.5, 2.0}中取值。
其次，选择攻击方式。攻击方式的选择是加权网络抗毁性分析的关键，攻击者通常会根据所掌握的网络结构信息，采取破坏力最强的蓄意攻击以达到最大的费效比。根据攻击者对网络信息的掌握情况，可将攻击方式分为基于网络局部信息和全局信息攻击2种方式。节点度和介数是网络节点重要性的2个常用测度，度大的节点对于保持网络的连通性至关重要，而介数较大的节点对于保持网络的传输效率则具有重要作用。因此，攻击者通常会选用度和介数作为节点重要性度量指标，对加权网络中的节点进行重要性排序并依次进行攻击。
本文依据Holme等[4]提出的4种攻击策略分别对加权网络抗毁性进行仿真。显然，当网络受到攻击时，网络效率及连通性都会减小，在一定的节点移除比例下，其减小的幅度越小，则说明网络的抗毁性越强。
3.1 基于网络局部信息的抗毁性仿真
节点的度刻画的是节点的局部特性，基于局部信息的攻击方式就是依据度值对节点进行攻击，其中又分为初始节点度(ID)和重新计算节点度(RD) 2种方式。在 ID攻击方式下，加权网络效率及连通性的变化情况如图1和图2所示，仿真结果为10次仿真的平均值。
由图1可知：在确定权重系数θ的情况下，网络的连通性和效率随着节点移除比例的增大而不断下降。在移除大约45%的节点后，网络的连通性和网络效率均下降为0。
另外，ID攻击初始阶段网络效率与连通性的变化曲线如图2所示，若取定网络效率的下降阈值为10%，可以看出在网络的连通性被完全破坏前，权重系数θ越大，节点移除对于网络效率的影响越小，网络的抗毁性越强。比如在移除 10%的节点后，θ=0.2的网络效率下降了38%，而θ=1.5的网络效率仅下降16%。若取定网络的连通性阈值为90%，则在移除比例小于5%之前，权重系数的变化对于网络连通性的影响不大，仅在节点移除比例大于5%时有细微的差别。
图1 ID攻击方式下网络效率与连通性变化曲线Fig.1 Efficiency and connectivity of weighted networks under ID removal
图2 ID攻击初始阶段网络效率与连通性变化曲线Fig.2 Efficiency and connectivity of weighted networks in early stage of ID removal
RD攻击方式下节点的移除对于网络性能的影响与 ID攻击方式下类似，只是由于每一步攻击都选择度最大的节点进行攻击，加剧了网络崩溃的速率。
3.2 基于网络全局信息的抗毁性仿真
节点的介数刻画的是节点的全局影响力，基于全局信息的攻击方式就是依据介数对节点进行攻击，其中又分为初始节点介数(IB)和重新计算的节点介数(RB) 2种。在IB攻击方式下，加权网络效率及连通性的变化情况如图3所示，仿真结果为10次仿真的平均值。
图3 IB攻击方式下网络效率与连通性变化曲线Fig.3 Efficiency and connectivity of weighted networks under IB removal
由图3可知：随着节点移除比例的增大，权重系数θ对于网络连通性的影响呈现出两极分化的趋势；当θ=0.2时，节点移除比例达到48%网络连通性下降为 0，节点移除对网络连通性的影响最大，而其他θ取值之间的差别很小；权重系数θ对于网络效率的影响也呈现出非常复杂的关系，当θ=0.5时，节点移除对网络效率和连通性的影响要小于其他值。经过进一步研究发现：当θ=0.5时网络对节点移除最不敏感，网络效率与连通性随节点移除比例增大的变化率较小，表明θ=0.5对应的加权网络抗毁性最优。
在RB攻击方式下，加权网络效率及连通性的变化情况如图4所示。由图4可知：节点移除对于网络效率和连通性的影响更为复杂；当节点移除比例小于40%时，权重系数θ=2.0的加权网络效率下降最快，对于其他取值的网络，节点移除对其网络效率的影响没有明显的规律；对于网络的连通性而言，θ=0.2的网络下降最快，随着θ的不断增大，节点移除对网络连通性的影响不断减小，网络抗毁性不断增强。
图4 RB攻击方式下网络效率与连通性变化曲线Fig.4 Efficiency and connectivity of weighted networks under RB removal
图5 RB攻击初始阶段网络效率变化曲线Fig.5 Efficiency of weighted networks in early stage of RB removal
RB攻击初始阶段网络效率的变化如图5所示。在早期阶段，权重系数θ=0.5的网络效率对于节点移除的敏感性最低，抗毁性最强。
需要说明的是：基于节点度的攻击策略侧重于尽快减少网络中边的数目，基于介数的攻击策略侧重于破坏网络的信息传输效率。然而，从图1～5中网络效率与连通性在不同攻击模式下的变化曲线可以看出：加权网络对基于节点介数攻击的抗毁性要优于基于节点度攻击的抗毁性。具体表现是：在基于节点介数攻击时，网络效率和连通性随节点移除比例的变化曲线较基于节点度的攻击曲线平缓。已有研究表明：在无标度网络中介数较大的节点往往就是度较大的节点[18]。然而，加权无标度网络对基于节点介数和节点度攻击的抗毁性表现出一定的差异。这可能是由加权网络权重与节点度乘积之间的非线性关系造成的。
3.3 考虑成本与性能的抗毁性优化分析
在数值仿真的基础上给出了网络特征参数与抗毁性之间的定性关系，下面从定量角度给出网络抗毁性的优化分析模型。
加权网络的抗毁性能与其建设成本、网络效率及网络鲁棒性是密切相关的。本文采用定量加权的方法建立的抗毁性分析模型如下：
式中：F网络抗毁性目标函数；α为加权系数；E为网络效率；δ为网络鲁棒性；c为加权网络建设成本，此处取c=
图6 ID攻击方式下网络的抗毁性Fig.6 Invulnerability of weighted networks under ID removal
由图6可知：在ID攻击方式下，若兼顾效率与鲁棒性，网络的抗毁性表现出分段效应；在初始阶段、中间阶段和后续阶段，平均度
由图7可知：IB攻击方式下网络的抗毁性与平均度即成本成反比，平均度越大，抗毁性越差。
由以上仿真结果可以得出：
图7 IB攻击方式下网络的抗毁性Fig.7 Invulnerability of weighted networks under IB removal
(1) 在网络成本一定的情况下，若攻击者仅仅获取了网络的局部拓扑结构信息，则权重系数越大，网络的抗毁性越强；若攻击者可能获取了网络的全局拓扑结构信息，则当权重系数θ=0.5时，网络的抗毁性较强。
(2) 若网络的成本不确定时，则在攻击者仅获取了网络的局部拓扑结构信息的条件下，平均度
另外，从图1～5也可以看出：在对网络进行攻击的过程中，加权网络效率和连通性的变化曲线渐趋平缓，即对网络的攻击效果越来越差。从攻击成本和抗毁性的角度分析，若能在网络攻击的早期加大节点的保护力度，则会大大降低对网络性能的影响。
由此可以看出：本文对于加权网络抗毁性的定性分析以及定量计算与通过权重随机化以及改变权重与边匹配关系等提高加权网络抗毁性的方法相比更实用，且能针对不同的信息条件，从整体上把握网络的抗毁性状况。
4 结论
(1) 在不同信息条件下，加权网络的抗毁性表现是不同的。在基于局部拓扑信息的攻击策略下，权重系数越大，节点移除对于网络效率和连通性的影响越小，网络的抗毁性越强。
(2) 在基于全局拓扑信息的攻击策略下，网络效率和连通性对节点移除的鲁棒性要优于基于局部信息的攻击策略，且权重系数为 0.5的网络在攻击初始阶段表现出最强的鲁棒性。
(3) 若能在攻击早期加大对节点的防护力度，则会大大降低对网络性能的影响。
(4) 给出了成本和性能约束下的网络抗毁性的优化策略。
(5) 本文仅研究了加权网络的静态抗毁性，实际上，网络的失效往往是动态关联的，因此，加权网络的动态抗毁性将是下一步需要深入研究的问题。
[1] 陈关荣, 陈增强, 吕金虎. 复杂网络科学与工程的研究进展[J]. 系统工程学报, 2010, 25(6): 723-724.
CHEN Guanrong, CHEN Zengqiang, LÜ Jinhu. Advances on complex networks science and engineering[J]. Journal of Systems Engineering, 2010, 25(6): 723-724.
[2] 谭跃进, 吕欣, 吴俊, 等. 复杂网络抗毁性研究若干问题的思考[J]. 系统工程理论与实践, 2008(S0): 116-120.
TAN Yuejin, LÜ Xin, WU Jun, et al. On the invulnerability research of complex networks[J]. Systems Engineering: Theory& Practice, 2008(S0): 116-120.
[3] Albert R, Jeong H, Barabasi A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406: 378-382.
[4] Holme P, Kim B J, Yoon C N, et al. Attack vulnerability of complex networks[J]. Phys Rev E, 2002, 65(5): 056109.
[5] Paul G, Sreenivasan S, Stanley H E. Resilience of complex networks to random breakdown[J]. Phys Rev E, 2005, 72(5):056130.
[6] 邓宏钟, 吴俊, 李勇, 等. 复杂网络拓扑结构对系统抗毁性影响研究[J]. 系统工程与电子技术, 2008, 30(12): 2425-2428.
DENG Hongzhong, WU Jun, LI Yong, et al. Influence of complex network topologic structure on system invulnerability[J]. Systems Engineering and Electronics, 2008,30(12): 2425-2428.
[7] WU Jun, DENG Hongzhong, TAN Yuejin, et al. Vulnerability of complex networks under intentional attack with imcomplete information[J]. J Phys A, 2007, 40(11): 2665-2671.
[8] 田柳, 狄增如, 姚虹. 权重分布对加权网络效率的影响[J]. 物理学报, 2011, 60(2): 028901.
TIAN Liu, DI Zengru, YAO Hong. Effect of distribution of weight on the efficiency of weighted networks[J]. Acta Phys Sin,2011, 60(2): 028901.
[9] Barrat A, Barthelemy M, Pastor-Satorras R, et al. The architecture of complex networks[J]. Proc Natl Acad Sci USA,2004, 101(11): 3747-3752.
[10] Dall' Asta L, Barrat A, Barthelemy M, et al. Vulnerability of weighted networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2006, P04006.
[11] LI Menghui, FAN Ying, CHEN Jiawei, et al. Weighted networks of scientific communication: The measurement and topological role of weight[J]. Physica A, 2005, 350(2/3/4): 643-656.
[12] LI Menghui, FAN Ying, WANG Dahui, et al. Small-world effect induced by weight randomization on regular networks[J].Physics Letters A, 2007, 364(6): 488-493.
[13] LI Daqing, LI Menghui, WU Jinshan, et al. Enhancing synchronizability by weight randomization on regular networks[J]. The European Physical Journal B, 2007, 57(4):423-428.
[14] WANG Wenxu, CHEN Guanrong. Universal robustness characteristic of weighted networks against cascading failure[J].Physics Review Letters E, 2008, 77(2): 026101.
[15] 李黎, 管晓宏, 赵千川, 等. 网络生存适应性的多目标评估[J].西安交通大学学报, 2010, 44(10): 1-7.
LI Li, GUAN Xiaohong, ZHAO Qianchuan, et al. Multi objective evaluation of network survival fitness[J]. Journal of Xi'an Jiaotong University, 2010, 44(10): 1-7.
[16] Crucitti P, Latora V, Marchiori M, et al. Efficiency of scale-free networks error and attack tolerance[J]. Physica A, 2003, 320(15):622-642.
[17] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[18] Goh K I, Oh E, Jeong H, et al. Classification of scale-free networks[J]. Proc Natl Acad Sci USA, 2002, 99(20):12583-12588.
