复杂网络中的一种介度熵抗毁性度量方法

张 昕，郭 阳

辽宁大学 信息学院，沈阳110036

1 引言

随着信息技术的发展复杂网络已经深入到人类社会的各个方面，如社交网络、通信网络与互联网、物网络、交通网络、经济与金融网络等。而网络时刻遭受着来自不同方面的、不同程度的、蓄意或无意的攻击，这就需要对网络进行抗毁性分析[1]，合理地衡量整个网络抵御攻击的能力，从而得到更有针对性地部署防范策略，有效地减少攻击损失。所以，复杂网络中的抗毁性[2]研究具有重要的理论价值和应用价值。现有的相关研究主要从三个方面进行[3]：一是基于图论的抗毁性研究，如粘连度、完整度、膨胀系数、核度等，考量了整个网络的抗毁性；二是基于解析的抗毁性研究，是采用渝渗理论将随机图中研究的问题渗流变换后进行分析研究；三是基于仿真的抗毁性研究，主要是对随机网络模型[4]和无标度网络模型[5-6]采用不同类型的攻击策略进行攻击后，对其拓扑结构的变化进行研究。考虑到在复杂网络中，核心节点一旦遭到攻击，有可能产生严重后果，甚至摧毁整个网络，因此本文从基于节点重要性[7]方面进行考量，研究复杂网络的抗毁性。本文结合多种网络拓扑结构，重新定义了节点重要性评估指标，提出了基于局部的介-度中心性指标，进而构建出介-度熵测度模型，提出衡量网络抗毁性的介-度熵算法。仿真实验结果表明，与传统的攻击策略相比较，本文提出的介-度中心性攻击策略破坏网络的能力更强，由此可知本文提出的基于局部的介-度中心性指标及介-度熵度量方法可以更好地衡量和评估网络的抗毁性。

2 相关工作

在复杂网络中，网络的生产性为随机性故障发生后其仍可以正常工作的能力；网络的可靠性为网络被攻击后其自身纠错并正常工作的能力。网络的随机性攻击会影响网络的生产性，而选择性攻击则会影响网络的可靠性。目前，网络的抗毁性能研究主要集中在对已知的确定性的网络进行选择性攻击，从而评估网络的可靠性。但在实际中对于网络的损害也有可能是其自身因素所造成的。

目前，许多研究人员从不同角度提出了抗毁性测度模型，确定了网络抗毁性度量，并量化分析了网络抗毁性。文献[8]中利用节点度值的大小对随机网络的鲁棒性和脆弱性进行了评估和分析；文献[9]在有权网络中利用边的数量及权值的大小评估网络中节点的重要程度，进而构建网络抗毁模型；文献[10]中分析了节点的介数中心性对大规模复杂网络中节点重要程度的影响；文献[11]提出了删除网络中节点后最短路径变化的评估方法；文献[12]中提出了针对无标度网络模型的抗毁性测度分析；文献[13]分别从节点重要性和网络拓扑结构的变化方面对网络的抗毁性的影响进行了研究；文献[14]研究了拓扑结构确定的加权复杂网路的抗毁性；文献[15]采用基于平均连通度及粘聚度的抗毁性测度方法评估了赋权网络的抗毁性。

在基于节点重要性的抗毁性测度研究中，文献[8]虽然是最简单直接的方式，但该方式并不全面；文献[9]局限于有权网络；文献[10]需要考虑网络自身的拓扑结构；文献[11]在网络遭受选择性攻击后分析了网络的连通性，但未考虑网络中最短路径的改变对节点重要性的影响。在基于链路的抗毁性测度研究中，文献[12]中当随机对网络中的链路进行删除时，有可能会破坏无标度网络的原有特性。文献[13]中衡量节点重要性主要采用节点的度分布，未结合节点其他重要性指标来进行抗毁性研究；文献[14]的研究无法适用于拓扑结构不确定的网络。

目前研究者们对节点的重要性评估主要采用全局中心性度量方法，如度中心性、介数中心性等。基于局部的节点重要性度量方法较少，已有的局部介数中心性[16]度量方法，是将节点的介数中心性的求解范围从全局转变为约束在k步内进行求解。在现实网络中节点的重要性需要从多方面进行考量，节点的度中心性和介数中心性虽然都可以在某种程度上反映出一个节点在网络中的重要程度，而且介数较高的节点的度值一般也比较高，但节点的度值和介数的关联程度并不高，所以可以对节点的度值和介数进行综合考量，得到节点重要性的衡量指标，可以更好地对节点的重要性进行评估。因此，本文对节点的局部介数中心性和度中心性进行了综合考量，提出介-度中心性指标（Betweenness-Degree Centrality，K-BDC），用以评估网络中节点的重要程度。同时兼顾聚集系数对节点重要程度的影响，进一步给出节点的抗毁性指标，并构建介-度熵度量，进而提出介-度熵（Betweenness-Degree Entropy，BDE）算法，衡量整个网络的抗攻击能力。

3 介-度中心性指标

在对计算机抗干扰性进行分析时，需要计算所有节点对之间的最短路径，计算复杂度较高，故而本文在Brandes[17]针对全局介数中心性算法基础上，引入最长距离约束k，将全局节点对之间的最短路径求解转化为k步内最短路径求解，缩小了求解最短路径的规模，提升了计算效率。并综合考虑节点的介数中心性与节点的度中心性，定义了基于局部的介-度中心性指标，用来衡量节点在网络中的重要性。

3.1 术语定义

复杂网络可抽象为拓扑图表示，记为图G=(V,E)，其中V表示为节点的集合，E表示为连边的集合。

定义1局部度相关系数：图G中节点v的局部度相关系数是指在图G所有长度不超过k(k＞1)的路径中，节点v的度在每条路径中占比值的总和，记为Tk(v)，其值由式（1）确定。

式中，dv表示节点v的度值，L(s,t|v)表示以节点s与节点t为两端点并经过节点v的路径集合，l表示其中一条路径。

定义2局部介-度中心性指标：令p(v)表示图G中通过节点v的所有长度不超过k的路径条数，σ(s,t)表示从节点s到节点t的最短路径数量，σ(s,t|v)表示从节点s通过节点v后到达节点t的最短路径数量，则图G中节点v的局部介-度中心性指标Ck(v)值由式（2）确定。

3.2 合理性分析

对比节点的介数中心性度量方法，K-BDC指标对节点的度值和介数进行了综合考量，从不同的角度综合评估了节点的重要性。由于节点度值仅能体现邻接节点数目，对节点重要程度的刻画不足，因此本文提出局部度相关系数概念，考察节点度在多条路径中的比重。在此基础上结合节点介数，进一步提出局部介-度中心性指标，并考虑到度相关系数相比节点介数计算结果相差一个量级，因此引入局部路径数目，使二者对局部介-度中心性指标的影响更为均衡。

分别采用介数中心性及本文提出的介-度中心性指标对图1所示网络中的节点中心性进行求解，所得结果见表1。

图1 示意网络图

表1 不同中心性度量方法求得的节点中心性对比

由表1可以看出，图1中节点1、2、3的介数中心性的值相同，表明这3个节点在网络中的重要程度相同，若对该网络进行蓄意攻击[18]，当节点1、2、3失效后，剩余节点之间不再存在连边，网络完全瘫痪。而图1中节点2、3的介-度中心性的值相同，当这2个节点失效后，即可使整个网络瘫痪。由该对比操作结果可知，本文定义的介-度中心性指标在网络抗毁性上对节点重要性的刻画准确程度高于介数中心性度量方法。同时，也说明本文提出的局部介-度中心性虽然是通过最长距离约束k对介数中心性进行了近似计算，但求得的节点重要性排序结果依然合理有效。由于在求解时有效地约束了路径长度，使得其在大规模网络上的运行效率得到了较大的提升。

4 介-度熵度量及算法

在复杂网络中，处于关键位置的核心节点通常具有信息传输量大、信息交换频繁等特点。所以核心节点的损坏可能会影响到整个网络的稳定性。故而本文基于节点重要性相关研究构建网络抗毁性测度模型。结合已提出的节点介-度中心性指标，提出节点抗毁性指标。进而提出介-度熵（BDE）度量方法，并进一步给出BDE算法及其时间复杂度分析。

4.1 术语定义

在图论中，聚集系数通常用于刻画图中节点聚集成团的程度，即衡量图中一个节点的邻居节点之间相互连接的紧密程度，节点在网络中越靠近核心位置，其邻居节点之间存在连边的可能性就越大，节点就越可能具有较高的度值和聚集系数，聚集系数在一定程度上刻画出节点在网络中所处的位置，而核心节点一般距离网络的中心位置较近，其聚集系数也较高，所以采用聚集系数可以更全面地描述节点的重要性。因而可以通过介-度中心性指标和聚集系数对节点的重要性进行综合考量，以期得到的更符合现实网络的节点抗毁性指标。

定义3节点抗毁性：是指网络中节点v的毁坏与整个网络毁坏的关联程度，记为S(v)，其值越大，则该节点的毁坏越易导致整个网络的毁坏。计算方法如式（3）所示，其中CLv表示节点v的聚集系数，Ck(v)为节点v的局部介-度中心性指标。

节点的抗毁性指标的准确性与最长距离约束k的取值直接相关，为了准确地刻画出节点v在局部范围内的介数中心性，最大距离约束k随着网络的规模增加而增大。而现实网络具有小世界性质，通过实验分析和理论依据，在网络规模较大时，取k=6是一个可以取得较准确计算结果的值。随着k值的取值增大，由最大距离约束k所确定的局部范围也会随之增加，直到k增大到某一阈值时，节点v的局部介数中心性计算会退化为对全局介数中心性的计算。以v为局部中心点的局部最短路径求解范围也会转化为对网络全局最短路径的计算。节点抗毁性指标体现出网络中的单个节点抵御攻击能力的强弱，在此基础上可以定义网络抗毁性度量，衡量整个网络的抗打击能力。

定义4介-度熵度量：通过对节点抗毁性分布的差异性进行评估，衡量整个网络的抗打击能力，记作BDE。介-度熵度量结果与网络的抗毁性能成正比，与节点间抗毁性分布成反比。即节点间抗毁性分布差异越小，网络抵御选择性攻击的能力越强，介-度熵度量值越大。反之亦然。计算方法如式（4）所示：

该度量表明节点抗毁性分布情况对网络抵御选择性攻击能力强弱的影响。综合考察了节点的度、局部介数中心性、聚集系数对网络抗毁性能的影响，得到较全面的网络的抗毁性度量结果。

4.2 BDE算法

本节给出计算节点抗毁性指标与介-度熵度量的BDE算法，该算法有2个输入参数，分别为网络G和最长距离约束k。通常来说，最长距离约束k与网络G的规模具有一定相关性，可根据具体输入网络酌情定值。在算法形式化描述中，Node[s-t]为从节点s出发到节点t，所经过的节点集合；Degree[s-t]为从节点s出发到节点t，所经过节点的度值总和。

算法形式化描述如下：

步骤1 START

1.FileOpen(G.edges)

2. FileRead(&u,&v)；

3. Matrix[u][v]=Matrix[v][u]=1；

4. Degree[u]++；

5. Degree[v]++；

6.For(i＜G.nodes)

7.If(Degree[i]＞1)

8. 计算各节点的聚集系数CL[s]

步骤1 FINISH

步骤1读入图G的数据文件，将其存入邻接矩阵中，并计算每个节点的度值，同时得到度值大于1的节点的聚集系数。其中Matrix[N][N]为邻接矩阵，用来保存图G的节点信息，Degree[N]用来保存节点的度信息，CL[s]用来保存节点的聚集系数。

步骤2 STRAT

9. BFS(s) s∈V

10. Node[s]←s；

11.If dist[t]＜=k

12. Node[s]←t,Q←t

13. If(!Pred Map.containsKey(Node[s-t]))

14. Pred Map.key=Node[s-t]

15. Pred Map.value=Degree[s-t]；

16. σ[s]++；

17. t[s]+=Degree[s]/Degree[s-t]；

步骤2 FINISH

步骤2求解度相关系数。采用Map结构存储节点的路径及路径上节点的度值总和。其中key为节点的路径Node[s-t],value为路径上的节点度值总和Degree[s-t]。dist[t]表示从节点s到节点t之间的最短路径；Q为满足最长距离约束k的队列；σ[s]表示记录从节点s开始遍历的满足最长距离约束k的路径条数；t[s]表示节点s在整条路径中节点度所占比值。

步骤3 START

18. While(!Q.Empty())

19. 出队列w←Q；入栈S←w；

20. GOTO步骤2

21. If Node[w-v]∈Node[s]&&s∈Node[w-v]

22. σ[s]++；

23. t[s]+=Degree[s]/Degree[w-v]；

24. If dist[w]=∞∩Exist(dist[w-v])

25. dist[w]←dist[v]+1；

26. If dist[w]＜k&&(!Q.contains(w))

27. 入队列Q←w；

28. If dist[w]=dist[v]+1

29. σ[w]←σ[w]+ω(s,w)⋅σ[v]；

30. Pred[w]←v；

31.For v∈V

32. δ[v]←0；

33.While(!S.Empty())

34. 出栈w←S；

35. For v∈Pred[w]

36. δ[v]←σ[v]/σ[w]⋅((1+δ[w])；

37. If w≠s Then

38. C(w)+=δ[w]；

39. Ck(s)=t[s]/σ[s]⋅C(s)；

40. Ck+=Ck(s)；

步骤3 FINISH

步骤3利用网络中前置节点的点对依赖求解节点的介-度中心性。其中ω(s,w)表示从节点s到节点w之间的路径的条数。其中序号18～20为初始化Q中节点信息；序号21～23为计算节点s在整条路径中节点度所占比值；序号24～30为求得s和w的中继节点v及从s经过v再到w的最短路径条数；序号31～40依据最短路径个数计算点对依赖，进而获得局部介-度中心性的值。

步骤4 START

41. BFS(s) s∈V

42. S(s)=CL[s]*Ck(s)/Ck；

43. E+=(-S(s)ln S(s))；

44. return S,E；

步骤4 FINISH

步骤4计算整个网络的介-度熵值。由求解得到的节点的聚集系数及介-度中心性，推导出节点的抗毁度，进而求得整个网络的介-度熵值。

在BDE算法中，计算节点的度相关系数由于引入最长距离约束k，使得其计算的时间复杂度近似接近于O(n2)，局部介-度中心性指标的时间复杂度由于将全局介数中心性计算转化为局部介数中心性计算，节点数量远远小于整个网络的节点数量，可以快速计算出局部的介数中心性。所以，局部介-度中心性指标的时间复杂度近似接近于O(n2)。从而可以得出BDE算法的时间复杂度根据最长距离约束k的选择会有一定的差异，当k选择为常量时，BDE算法的时间复杂度不超过O(n2)。

5 仿真实验

采用具有无标度网络和小世界网络特性的生成网络进行仿真实验，网络节点数量分别为200和5 000，通过对节点攻击（在网络中去除节点）后网络连通程度的变化情况进行研究，得到网络在不同攻击策略下的抗毁性能。实验中采用随机攻击和蓄意攻击方式去除仿真网络中的节点，其中蓄意攻击方式采取基于度中心性优先攻击、基于介数中心性优先攻击以及基于介-度中心性优先攻击三种攻击策略。分别对比不同的网络规模及攻击策略下仿真网络所表现出的抗毁性差异。一般来说，对于规模较小的网络选择以去除的节点个数为研究对象，可采用最大连通子图；对于规模较大的网络选择以去除节点的比例为研究对象，可采用平均反测地线距离。因此，本文采用上述两种指标作为评估不同规模网络连通程度的度量。

然后生成节点数量分别为30和5 000，且连接概率不同的模拟网络进行抗毁性评估，通过对比不同网络的介-度熵度量与网络的实际抗毁性，论证该度量的合理性。

5.1 节点数为200的网络仿真实验

在网络中，连通子图表示其内部任意两个节点之间都存在相连路径的图；非连通子图则表示其内部存在两个或以上节点之间无相连路径的图。在图中具有最多节点的连通子图称为最大连通子图。在一个连通的网络中，网络的结构随着节点的变化而不断改变，连通子图有可能分裂为多个子图或者合并成一个子图。采用最大连通子图对网络连通程度的进行度量，可以有效说明网络受损的程度。

分别生成节点数量为200的2个具有不同网络特性仿真网络。具有小世界网络特性的生成网络的节点度值分布相对比较均匀，而具有无标度特性的生成网络的节点度值随机性较大，且网络中小部分节点具有较高的度值。在无标度网络中度值为1的节点比重较大，而在小世界网络中度值为4的节点比重较大。实验中计算局部介-度中心性指标时，考虑实验网络规模，令局部性约束k=5。图2展现了基于随机性攻击、度中心性优先攻击、介数中心性优先攻击以及介-度中心性优先攻击4种攻击策略时网络受损情况对比，并以网络最大连通子图的规模为衡量标准。

从图2（a）中可以看出，在随机攻击模式下，无标度网络中的最大连通子图中节点的数量随着节点的不断移除以线性的方式逐渐递减，直到移除节点的个数接近节点总数时才降为0；在蓄意攻击模式下，基于度中心性的攻击策略在移除大约50个节点时，最大连通子图中节点的数量接近于0，此时网络中只存在孤立节点；基于介数中心性的攻击策略与基于本文介-度中心性的攻击策略在移除大约40个节点时，最大连通子图中节点的数量即趋向于0。但从两个攻击策略的对比曲线可以看出，基于本文介-度中心性的攻击策略下降得略快。图2（b）所示对比情况与图2（a）类似，随机攻击的效果较差，而在蓄意攻击模式下基于介-度中心性的策略效果最佳。由此可以得到结论，基于本文介-度中心性的攻击策略要优于基于度中心性和基于介数中心性的攻击策略，对网络的破坏性更强。

5.2 节点数为5 000的网络仿真实验

节点之间的最短路径为从起始节点到目标节点经过连边最少的一条路径，也称为测地线。网络中所有节点之间最短距离的均值表明了节点的分散情况，称为平均测地线距离，记作L，其计算方法如式（5）所示，其中dij表示节点之间的最短距离。

当网络不断遭受选择性攻击时，整个网络被逐步拆分为多个子网络，导致平均路径长度不断扩大。这时可以使用反测地线距离L-1描述网络的平均最短路径，当L-1变为0时，则表明节点对之间不再存在相连路径，此时网络中的节点全部成为孤立节点，其计算方法如式（6）所示，其中若节点i和节点j之间不存在通路时1/dij=0。

图2 最大连通度指标下4种攻击策略对比图

分别生成节点数量均为5 000的无标度网络和小世界网络，图3展现了基于度中心性优先攻击、基于介数中心性优先攻击以及基于介-度中心性优先攻击三种攻击策略时网络受损情况对比，并以网络平均反测地线距离为衡量标准。由于实验网络规模较大，随机攻击效果极差，不必与其进行对比，并令局部性约束k=6。

由图3（a）中可知，平均反测地线距离的变化速率随着节点的失效逐渐放缓，在基于度中心性的攻击策略中，网络的平均反测地线距离在移除大约整个网络中25%的节点时变为0；在基于介数中心性的攻击策略和基于本文介-度中心性的攻击策略中，网络的平均反测地线距离在移除整个网络中20%的节点时开始趋向于0，但采用本文介-度中心性策略进行攻击的曲线比采用介数中心性策略进行攻击的曲线下降得略快，即网络中节点全部成为孤立节点的速度略快于采用基于介数中心性的攻击策略。由此可知，在无标度网络中，基于介-度中心性的攻击策略对网络的破坏能力高于基于度中心性及基于介数中心性的攻击策略。

由图3（b）可知，小世界网络中的平均反测地线距离变化速率虽然也随着节点的失效逐渐放缓，但其放缓速率要比在无标度网络中慢得多。采用基于度中心性的攻击策略时，平均反测地线距离在移除整个网络中大约60%的节点时变为0；采用基于介-度中心性的策略攻击时，平均反测地线距离在移除整个网络中大约50%的节点时就开始趋近0；而采用基于介数中心性攻击策略进行攻击的曲线图形介于基于度中心性攻击策略和基于介-度中心性攻击策略之间，靠近于基于本文提出的介-度中心性策略进行攻击的曲线。总体看来，对网络进行蓄意攻击时，与采用基于度中心性和采用基于介数中心性的攻击策略相比，采用本文提出的基于介-度中心性的攻击策略在去除更少的节点时就使得网络的平均反测地线距离趋向于0或成为0，表明其更容易对网络造成损害，攻击效果更明显。

5.3 介-度熵度量实验

构造不同规模以及不同连接概率的模拟网络对节点抗毁性测度及网络介-度熵度量进行分析，根据构造时选取的随机重连概率p不同，构造出的网络模型也将发生相应的变化。当p为0时，构造出的网络为规则网络；随着p值的不断增大，网络向小世界网络演化，当p增大至1时，构造出的网络即为随机网络。

将网络中节点总数分别设为30与5 000，节点平均度为6，对p分别取值为0.1、0.5和0.9，构造出的3种仿真网络中的节点的度分布情况如图4所示。

分别针对节点个数为30（局部性约束k=4）和节点个数为5 000（局部性约束k=6）2种情况，计算对3类网络进行选择性攻击时网络中的节点抗毁性和介-度熵，计算结果如表2所示。

图3 平均反测地线距离指标下3种攻击策略对比图

图4 仿真网络节点度分布图

表2 仿真网络节点抗毁性及介-度熵计算结果

由图4（a）和图4（b）可以看出，生成网络的节点度值的随机性与生成网络的随机重连概率p正相关，p值越大，节点度分布的差异性就越大。由于规则网络中节点度分布最均匀，因此对其进行选择性攻击时单个节点的毁坏对网络的影响最小，抵抗破坏能力最强。而随机网络中节点度分布最不均匀，重要性较为突出个别核心节点一旦被毁坏将对网络造成较大的影响，因此随机网络对选择性攻击的抵抗能力最弱。

由表2的对比结果可以看出，对3种网络进行选择性攻击时，其节点平均抗毁性关系：规则网络＞小世界网络＞随机网络，体现了网络面对选择性打击时抗毁性能的强弱排序，而介-度熵度量得到了相同的对比结果。该对比排序结果符合图4（a）和图4（b）的对比分析，因此说明介-度熵度量是完全合理的。

首先对仿真生成网络进行仿真攻击实验。通过分别对比3种不同攻击策略下的实验结果，可以看出在对网络进行选择性攻击时，基于本文介-度中心性的攻击策略大幅优于基于度中心性的攻击策略，且相对于基于介数中心性的攻击策略也具有一定优势。对大规模复杂网络求取介数中心性时通常效率较低，而介-度中心性可以通过限制最长距离约束来进行近似计算，提高了计算效率，更适合大规模网络中的抗毁性分析。然后对规则网络、小世界网络以及随机网络进行抗毁性评估计算，结果表明本文提出的介-度熵度量能够准确评估大规模复杂网络的网络抗毁性。

6 结束语

本文结合节点度值与节点介数，并通过限制最长距离约束考察其局部作用，提出了用于度量网络中节点重要程度的局部介-度中心性指标。在此基础上提出了度量网络中单个节点对整体抗毁性影响能力大小的节点抗毁性指标。进而提出介-度熵度量，评估网络抗毁性能的强弱，并给出了该度量的计算方法。仿真实验结果表明，与传统的攻击策略相比较，本文提出的介-度中心性的攻击策略具有明显优势，对网络造成的破坏性更强，说明介-度中心性指标在衡量节点重要性方面具有明显优势。对规则网络、小世界网络以及随机网络进行抗毁性评估计算的结果表明，介-度熵度量是评估大规模复杂网络抗毁性的合理度量。

本文主要基于无权网络进行抗毁性研究，而在现实网络中，连边通常存在多种权重，需要综合考虑权重因素，以便获得更准确的网络抗毁性度量结果。在未来的工作中需要依据实际应用环境，综合考虑各方面因素改进介-度中心性指标与介-度熵度量，使其具有更好的评估效果。