复杂网络的鲁棒性与中心性指标的研究

陆靖桥 傅秀芬 蒙在桥

复杂网络的鲁棒性与中心性指标的研究

陆靖桥1傅秀芬1蒙在桥2

1(广东工业大学计算机学院 广东 广州 510006)

2(中山大学信息科学与技术学院 广东 广州 510006)

网络鲁棒性是指网络遭到随机故障或蓄意攻击时仍能维持其功能的能力，理解复杂网络部分结构的失效对网络结构和功能的影响有着非常重要的意义。针对不同的开放数据集和爬取的新浪微博数据集，通过计算移除部分节点后的巨片和连通子图数目等指标，着重分析蓄意攻击对网络的影响，发现度攻击策略对不同网络结构影响均较大，紧密度和介数攻击策略对网络结构的影响有明显区别。实验表明，非微博网络的蓄意攻击中，采用度和介数攻击策略效果较好，而微博网络应采用度和紧密度攻击策略。

复杂网络 中心性指标 鲁棒性 蓄意攻击

0 引 言

复杂系统出现在很多自然和社会科学领域，以及许多技术领域。复杂网络是复杂系统的抽象，几乎所有的复杂系统均可以抽象为复杂网络，这些抽象后的网络一般拥有大量的节点，同时对应的节点间存在复杂的连边关系[1]。复杂网络的一项基础领域是研究在网络部分结构失效后对网络整体结构和功能的影响[2]，其称为网络的鲁棒性。

复杂系统强调从结构角度分析系统的功能，事实上复杂系统的拓扑结构是系统所具有的内在、本质的特性，系统的功能与其拓扑密切相关。复杂系统可能会受到各种事件的攻击，影响系统正常的结构和功能。如2003年8月，美国俄亥俄州克利夫兰市的超高压输电线路相继过载烧断使得上千万人陷入黑暗长达15小时，经济损失高达数百亿美元。再如，2008年1月的大雪造成中国南方的高速道路、各个城市的街道陷入瘫痪，造成行人和物资无法流通，给社会和经济带来了极大的损失。因此，研究复杂网络的鲁棒性具有重要的理论和现实意义。

Albert等[3]开创性地分别将随机网络(ER模型)和无标度网络(BA模型)置于随机故障和蓄意攻击两种攻击策略之下，结果显示无标度网络对随机故障比随机网络具有更强的鲁棒性，但对蓄意攻击却较脆弱，并指出其根源在于无标度网络中度分布的不均匀性。柳虹等[4]分析供应链网络遭到攻击时的脆弱性和鲁棒性，得出传递攻击能够较好地模拟供应链网络中的供求失败。周漩等[5]利用节点效率评估复杂网络的功能鲁棒性，实现对大型复杂网络可以获得较理想的计算能力。王凯[6]对电力网络的复杂性和鲁棒性进行研究，提出了用于电网关键节点和关键路线识别的结构重要度指标和计算方法。Schneider等[7]以欧洲电力网络和全球因特网的服务提供者网络为研究对象，提出了一种新的有效减缓攻击的方法，在网络拓扑修改最小和不增加连边的情况下显著提高网络的鲁棒性。Iyer等[8]除采用度和介数中心性，还引入紧密度和特征向量等全局指标，结合聚类系数和同配系数，分析合成网络和真实网络遭到随机攻击和蓄意攻击时的鲁棒性，发现度和介数攻击策略均具有不错的效果。吴敏等[9]对BBS回复网络进行分析，发现BBS用户回复网络抗毁能力远不及随机网络和无标度网络，蓄意攻击能在短时间内使网络崩溃。

目前不少学者采用平均最短路径、聚集系数和网络效率等作为衡量指标[10]，广泛探讨了网络的鲁棒性和灾难(故障)对网络的影响。Barrat等在文献[11]中指出“确定最中心节点是刻画网络各种特征研究的最主要问题”，依据这一思想，另一种重要的网络鲁棒性研究方法考察网络在移除部分节点后的巨片大小[7]，即先移除一定比例高中心性值的节点，再计算最大连通子图包含节点数目。

本文采用巨片指标，同时引入连通子图数目这一新指标，用以刻画网络“破碎”程度，力求更全面地对比分析不同网络的鲁棒性。目前复杂网络的鲁棒性研究大多针对电力、航空等数据集，较少关注微博网络。复杂网络的随机攻击在文献[3]等已有详细描述，本文不予累赘分析，重点在于分析不同网络的蓄意攻击。实验对象采用开放数据集和爬取的新浪微博数据集。

1 相关定义

1.1 中心性指标

度刻画网络的局部特征，属于无标度网络拓扑结构的最基本参数，用于描述静态网络节点的直接影响力。节点v的度kv定义为与其直接相连的节点数目，节点的kv越大说明该节点越重要。在拥有n个节点的有向网络中，节点最大的可能度为n-1，则节点v的度中心性归一化值为:

(1)

介数刻画网络节点对于信息流动的影响力，属于网络的全局特征。在n个节点的网络中，经过给定节点v的最短路径的最大数目情形是任意两个其他节点之间的最短路径均经过该节点，即(n-1)(n-2)/2。节点v的介数中心性归一化定义为：

(2)

其中，δst表示节点s到节点t的最短路径数目，δst(v)表示从节点s到节点t之间经过节点v的最短路径数目。

紧密中心性刻画节点v到达其他节点的难易程度，定义为v到达其他节点的最短路径之和的倒数：

(3)

特征向量中心性认为一个节点的重要性既取决于其邻居节点的数量(度)，同时也取决于每个邻居节点的重要性，定义节点vi的特征向量值xi为:

(4)

其中，仅当vi和vj相邻时，aij=1，否则aij=0。c为一个比例常量。从定义发现，特征向量更加强调节点所处的周围环境。

1.2 连通子图

连通子图[3]表示网络G在攻击后，v1,v2,…,vm-1,vm(1≤m≤n)与网络其他节点失去连接，导致网络G破碎成多个互不连通的独立子图G1,G2,…,Gs-1,Gs(1≤s≤n)，其中的最大连通子图称为“巨片”。

对于复杂网络而言，巨片在描述网络受到攻击后的“残留”连通能力方面有一定局限性。如图1是同一网络受到相同攻击后的两种不同破碎状态：左图破碎为6个不连通子图，巨片包含5个节点，右图破碎为4个不连通子图，巨片包含3个节点。明显发现，右图的子图(节点数大于1)内部节点间仍可以局部沟通，而左图的子图多数为孤立几点，完全无法与其他节点沟通。所以，左图的巨片虽包含较多节点，但整体破碎程度远高于右图，攻击策略对其的攻击效果更好。本文结合巨片和连通子图数目，希望较全面的分析网络面对蓄意攻击时的鲁棒性。

图1 相同攻击策略对同一网络造成的两种破碎状态

1.3 网络鲁棒性R-指标

本文采用R-指标[8]刻画网络的鲁棒性，其思想是移除网络一定比例的节点后，计算网络中属于巨片的节点数目：

(5)

其中，N表示网络的节点总数，δ(Q)表示移除Q=qN(q为移除的节点比例)节点后巨片包含的节点数占网络总数N的比例，即巨片的相对大小。1/N实现不同尺度的网络可以进行鲁棒性的归一化比较。不论何种算法，在星型网络中，R取最小值1/N，在完全图中R取最大值0.5。由此，我们可以进一步定义：

V=0.5-R

(6)

式(6)表示网络对于移除节点后的脆弱性：V越大说明网络对于攻击越脆弱，即采用的攻击策略的效果越好。

2 数据介绍

实验所用数据集分为两大类：开放数据集(非微博数据)和作者爬取的新浪微博数据集。依据实验需要，原始网络统一处理为无向无权网络。

2.1 开放数据集

实验一共采用5个不同规模的开放数据集[12]。海豚网络和线虫神经网络(有向含权网络)属于小型网络，科学家合作网络、美国西部电力网络和路由器自治层次网络属于中大型网络，具体统计性质见表1所示。其中，N和M分别表示网络的节点数和边数，为网络的平均度，l为平均路径长度，GN为巨片包含节点数，CN为连通子图数目。

表1 开放数据集网络的拓扑性质

2.2 新浪微博数据集

本文采集新浪微博的实际用户数据，构建用户关系网络。为了增强实验结果的可靠性、避免新浪微博API的限制，采用基于HTTP协议的网络爬虫获取数据集，分别从作者的所有转发用户出发，逐层爬取粉丝和关注用户，构成原始的数据集。然后经过数据的预处理，得到实验所需的网络数据集。构建的微博数据集的网络拓扑特征如表2所示(d为网络直径、r为平均聚类系数，其他符号同上表)。从表2发现网络平均路径长度位于4到6之间，网络直径均为12，说明微博数据集均具有小世界的特征[13]。文中实验不区分边的有向性。

表2 微博有向传播网络的拓扑结构

图2是数据集的度、入度和出度的累计概率分布。从图中可知，度、入度和出度均出现首尾分段幂律分布的现象，其中，度和出度在尾部的分布类似，出度的分布更加平滑。微博数据集均符合复杂网络的幂律分布特性[14]，说明新浪微博满足复杂网络的无标度特性，验证了爬取的微博数据的有效性。

图2 微博数据集的度、入度和出度的累计分布图

3 实验结果与分析

本文对构建的网络从某一中心性值最高的节点开始，迭代递增比例的顺序移除节点。通过巨片的相对大小和连通子图数目直观分析网络的鲁棒性，再依据V-指标量化分析网络的鲁棒性。

3.1 开放数据集网络

图3-图5为数据集在遭到蓄意攻击时的不同情况。经分析，面对相同的攻击不同的网络呈现某些共性，比如巨片相对大小的下降趋势呈现先快后慢，连通子图数目先递增至最值，然后递减。然而，不同网络又表现出各自的差异性。

图3 海豚网络

图4 科学家合作网络、电力网络和路由器自治网络

图5 线虫神经网络

从图3可以看出海豚网络对不同的攻击策略有明显差异。巨片和连通子图数目均表明度和介数攻击策略优于紧密度和特征向量攻击策略，其中度攻击策略产生较多的碎片，介数攻击策略生成较小的巨片，两种策略各有优缺点。

从图4结果分析，可以看到科学家合作网络、电力网络和路由器自治网络遭到蓄意攻击时，巨片大小呈现较快速的下降趋势。其中，科学家合作网络若仅分析巨片，发现度、介数和紧密度攻击策略的效果类似。进一步分析连通子图数目，在移除节点的百分比较低时，介数攻击策略产生显著较多碎片，其攻击效果优于度策略，此外清晰得知紧密度和特征向量攻击策略较差。电力网络和航空网络属于社会生产生活过程中演化出的网络。电力网络从巨片角度出发，度和介数攻击策略效果类似，均好于紧密度和特征向量，结合连通子图数目分析，可以看出度攻击策略优于介数策略。而且明显发现电力网络移除少量高中心性值节点(少于10%节点)可对网络产生严重后果。路由器自治网络的攻击效果明显分为两大类，其中度和介数攻击策略属于较好一类，其攻击效果基本相同，即对网络造成迅速和严重的破坏，极少量节点(甚至不到5%节点)可导致网络的整体破碎，这一现象与路由器网络的构造紧密相关，少量的路由器占据着网络的大量重要位置。

从图5发现线虫神经网络遭到蓄意攻击时呈现有趣的不同现象。巨片大小下降缓慢、碎片数目上升也较慢，这表明该网络具有较强的鲁棒性：移除小部分节点对网络的完整性产生的影响较小。但移除的节点数到达一定程度，对网络的破坏程度便会突升。这一现象或许与生物神经网络的特性相关，生物神经网络是长期进化的结果。

从不同网络遭到蓄意攻击时的不同现象发现，采用度和介数攻击策略普遍较好。我们也注意到，结合巨片和连通子图数目可以更加清晰、有效地分析攻击效果。巨片描述网络的最大连通子图内部的沟通能力，属于局部指标；连通子图数目从网络的整体破碎程度出发，描述破碎网络“残留”的“整体”沟通能力，属于粗粒度的全局指标。

3.2 微博数据集

除采用开放数据集，本文继续对微博数据集进行鲁棒性研究，实验结果如图6所示。

图6 新浪微博网络

从图6发现，微博网络对蓄意攻击表现出与前文不同的现象。对于微博网络，图6表明度和紧密度攻击策略更好，均优于介数(较浅虚线)和特征向量攻击策略，且紧密度(较深虚线)攻击策略的攻击效果不同于度策略的攻击效果。其中，移除节点比例较低时，度策略均优于紧密度策略，但在移除节点比例20%左右时，度攻击策略略逊于紧密度攻击策略。此外，采用紧密度攻击策略，微博网络在移除25%～35%的节点区间内，巨片大小下降速度迅速减缓，同时碎片数目不再增加，反而呈现持续递减趋势，一段过程后才回升。

我们定性解释微博网络的现象，图7是各中心性的分布图。可以看出，一类有较多的高中心性值节点，另一类有较少的高中心性值节点。对于度分布，高中心性值的节点数目最少，该现象与文献[3]中描述一致，即大部分节点的度相对较小仅少量节点的度相对较大。介数和特征向量中心性均拥有较多的高中心性节点，而紧密度的高中心性值节点较少。同时也发现，不同紧密度值均对应一定小数目的节点，特别是统计发现在0.26～0.28值之间集中了较多节点，这与图6中紧密度出现的局部(巨片平滑稳定)碎片数目不升反降密切有关。

图7 微博网络鲁棒性现象探究解释

3.3 综合分析

为了定量分析开放数据集和爬取的微博数据集的鲁棒性，本文计算网络脆弱性V-指标，结果如表3所示。

表3 网络受到同步蓄意攻击的V-指标

从表3得知，非微博网络(开放数据集)采用度和介数攻击策略对应的V值大于紧密度和特征向量攻击策略。微博网络采用度和紧密度攻击策略对应的V值大于介数和特征向量攻击策略。此外，电力和路由器自治网络的V值大于0.4，面对蓄意攻击的影响更大，这一结果和日常生活的直觉一致；线虫神经网络的V值最小，面对蓄意攻击时的鲁棒性最强；量化的分析结果与前文分析的结论一致。

4 结 语

复杂网络的部分节点失效后，网络能否维持其功能通常与网络结构的完整性有关。本文在常用的巨片指标的基础上，引入连通子图数目来分析网络遭到攻击后的破碎情况。研究发现，非网络微博在面对度和介数攻击策略时，破坏程度较严重；微博网络采用度和紧密度攻击策略得到的攻击效果优于采用介数和特征向量攻击策略。

[1] 邓宏钟,吴俊,李勇,等.复杂网络拓扑结构对系统抗毁性影响研究[J].系统工程与电子技术,2009,30(12):2425-2428.

[2] Morohosi H.Measuring the network robustness by Monte Carlo estimation of shortest path length distribution[J].Mathematics and Computers in Simulation,2010,81(3):551-559.

[3] Albert R,Jeong H,Barabási A L.Error and attack tolerance of complex networks[J].Nature,2000,406(6794):378-382.

[4] 柳虹,周根贵,傅培华,等.基于供应链网络的传递攻击策略研究[J].计算机科学,2013,40(7):98-101.

[5] 周漩,张凤鸣,周卫平,等.利用节点效率评估复杂网络功能鲁棒性[J].物理学报,2012,61(19):190201.

[6] 王凯.基于复杂网络理论的电网结构复杂性和脆弱性研究[D].华中科技大学,2011.

[7] Schneider C M,Moreira A A,Andrade J S,et al.Mitigation of malicious attacks on networks[J].Proceedings of the National Academy of Sciences,2011,108(10):3838-3841.

[8] Iyer S,Killingback T,Sundaram B,et al.Attack robustness and centrality of complex networks[J].PloS one,2013,8(4):e59613.

[9] 吴敏,李慧,张柯,等.BBS用户回复网络的抗毁性分析[J].计算机科学,2012,39(S6):28-30.

[10] Crucitti P,Latora V,Marchiori M,et al.Error and Attack Tolerance of Complex Networks[J].Physica,2004,340:388-394.

[11] Barrat A,Barthelemy M,Pastor-Satorras R,et al.The architecture of complex weighted networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(11):3747-3752.

[12] Newman M E J.datsets.http://www-personal.umich.edu/～mejn/netdata/.

[13] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’networks[J].Nature,1998,393(6684):440-442.

[14] Newman M E J,Park J.Why social networks are different from other types of networks[J].Physical Review E,2003,68(3):036122.

RESEARCH ON ROBUSTNESS AND CENTRALITY METRICS OF COMPLEX NETWORKS

Lu Jingqiao1Fu Xiufen1Meng Zaiqiao2

1(SchoolofComputer,GuangdongUniversityofTechnology,Guangzhou510006,Guangdong,China)2(SchoolofinformationScienceandTechnology,SunYat-senUniversity,Guangzhou510006,Guangdong,China)

Network’s robustness refers to the capability of network to remain its functionality unchanged when suffering random failures or malicious attacks, it is of important significance to understand the impact of partial structural failure in complex network on the structure and function of networks. Aiming at different open datasets and the Sina microblogging datasets which is derived by crawling, we concentrated on analysing the impact of malicious attacks on the network structure by calculating the indices of giant component and the number of connected subgraph after removing a portion of nodes, and found that the degree attack strategy had a great impact on different network structures, while closeness and betweenness attack strategies had distinct impact on network structure. Experiment showed that in malicious attacking against non-microblogging network, to adopt the degree and betweenness attacking strategies simultaneously has better effect, while for microblogging network the degree and closeness attacking strategies should be used.

Complex networks Centrality metrics Robustness Malicious attack

2014-08-25。广东省科技计划项目(2012B091000173)。陆靖桥，硕士生，主研领域：复杂网络，数据挖掘。傅秀芬，教授。蒙在桥，博士生。

TP301

A

10.3969/j.issn.1000-386x.2016.04.070