马顺利，王小红

原图边与线图点扰动的相继故障仿真研究

马顺利1，王小红2

（1. 青海民族大学 计算机学院，青海 西宁 810007；2. 齐鲁工业大学（山东省科学院），山东省计算中心（国家超级计算济南中心），山东 济南 250101）

提出基于BA无标度网络和ER随机网络拓扑的线图结构，继而进行线图点边扰动仿真实验。通过模拟故障的发生，对仿真结果中线图与原图间的阈值关系进行比较可知：不论攻击点还是攻击边，不论蓄意攻击还是随机攻击，在相同的扰动值下，原图引起的故障规模总是比线图大。

BA无标度网络；ER随机网络；相继故障；仿真实验

1 研究背景

线图的概念是由Whitney[1]于1932年首先提出的，是从一个已知图构造另一个更大的图的重要方法。线图中的许多图论参数，比如顶点度、直径、连通度、Euler和Hamilton性等都可以很方便地从原始图导出。线图是从图中与边有关的性质导出与顶点有关的性质的重要工具[2-3]，被广泛用于互联网拓扑结构设计。

设=（,）是无孤立点的简单无向图。的线图（line graph）记为()，顶点集为()，对中任何两条不同的边1和2，它们在()中相邻，当且仅当它们在中相邻[2]。

可以利用这种方法，把BA无标度网络[4-9]与ER[10]随机网络的原拓扑结构图转换为线图结构。例如，图1所示的是节点数18、边数为70的ER随机网络图和它的线图()。可以清晰地看到：图中节点度分布是非常均匀的。

图1 ER随机网络拓扑结构及其线图

图2所示的是节点数为18、边数为46的BA无标度网络¢和它的线图(¢)。在图¢中可以清晰地看到，BA无标度网络表现出了优先连接机制，新的节点总是倾向于与3个度最大的节点相连接。

图2 BA无标度网络拓扑结构与其线图

2 相继故障仿真模型

点扰动时，应用Kaneko K在20世纪90年代提出的耦合印象格子（CML）的相继故障模型表达[11]。该模型被描述为

边扰动时，应用崔迪提出的边抗损坏模型表 达[12]，该模型被描述为

3 BA无标度网络原图边与线图点扰动的相继故障仿真

3.1 仿真实验与结果

图3中的数据见表1。表1显示了BA无标度网络以随机攻击和蓄意攻击两种策略对原图边与线图点施加扰动时，扰动阈值与故障规模的关系。BA无标度网络的相继故障过程中，当扰动幅值超过第一个临界值1时，故障规模开始增大；在第二个临界值2和第三个临界值3中，故障规模保持同一水平；当扰动幅值超过第三个临界值3时，故障规模快速增大；当扰动幅值超过第四个临界值4时，网络将出现全局故障。

图3 BA网络原图边、线图点的攻击阈值与故障规模的关系曲线

表1 BA无标度网络原图与线图结构下的相继故障与阈值关系

3.2 数据分析

分析图3中的曲线以及表1中数据，可知：

（1）关于BA无标度网络线图点与原图边的相继故障扩散过程。当随机攻击时，原图边的扰动临界值4=5.4，线图点的扰动临界值4=7.6；当蓄意攻击时，原图边的扰动临界值4=3，线图点的扰动临界值4=7.6。

随机攻击与蓄意攻击线图点，其相继故障过程如图4所示。在相同的扰动幅值下，随机攻击下的故障规模要远小于蓄意攻击下的故障规模。

图4 BA网络线图点的随机、蓄意攻击阈值与故障规模的关系曲线

3.3 仿真结果

由以上分析，可以得到如下仿真结果：

（1）在BA无标度网络的相继故障过程中，对边施加很小的扰动，就能引起很大的网络故障，以致全局崩溃。特别是在蓄意攻击时，边攻击达到全局崩溃的扰动值较小，而同样大小的扰动施加给点，只能造成初始故障。

（2）在BA无标度网络的相继故障过程中，线图点和原图边在蓄意攻击下，更容易引起网络的全局故障。对于原图边攻击，引起全局故障的蓄意扰动值4比随机扰动值4小。BA无标度网络中相继故障进程剧烈程度由大到小依次为：原图边蓄意攻击>原图边随机攻击>线图点蓄意攻击>线图点随机攻击。

4 ER随机网络原图边与线图点扰动的相继故障研究

4.1 仿真实验与结果

图5 ER网络原图边、线图点的攻击阈值与故障规模的关系曲线

图5中的数据见表2，表2显示了ER随机网络以随机攻击和蓄意攻击两种策略对原图边与线图点施加扰动时扰动阈值与故障规模的关系。

表2 ER随机网络原图与线图结构下的相继故障与阈值关系

4.2 数据分析

分析图5(a)和图5(b)的曲线以及表2中数据，可知：

（1）关于ER随机网络线图点与原图边的相继故障扩散过程。当随机攻击时，原图边的扰动临界值4=4.4，线图点的扰动临界值4=7.6；蓄意攻击时，原图边的扰动临界值4=4.6，线图点的扰动临界值4=7.6。

（2）关于蓄意攻击与随机攻击对ER随机网络相继故障的影响。随机攻击时，原图边的相继故障扰动临界值4=4.4；蓄意攻击时，原图边的相继故障扰动临界值4=4.6；随机攻击时，线图点的相继故障扰动临界值4=7.6；蓄意攻击时，线图点的相继故障扰动临界值4=7.6。

4.3 仿真结果

（1）在ER随机网络的相继故障过程中，不论是随机攻击还是蓄意攻击，原图边崩溃的速度明显比线图点的速度快，同时原图边崩溃的剧烈程度要大于线图点。这是因为，边在网络中作为攻击对象时，比点更脆弱，边遭受攻击对整个网络的影响大于点。

（2）在攻击线图点与原图边时，与随机攻击相比，蓄意攻击时的相继故障速度区别不大。

（3）ER随机网络中的线图点随机攻击，持续时间最长，相继故障进程最缓和。这是因为ER随机网络的度分布较均匀，并且线图结构有极高的连通度，所以在随机攻击ER线图点时，网络体现出了很高的鲁棒性。

5 结论

根据图3、图5仿真结果以及表1、表2中数据分析，得到结论如下：

（1）在BA无标度网络与ER随机网络中，相继故障进程剧烈程度由大到小为：原图边蓄意攻击>原图边随机攻击>线图点蓄意攻击>线图点随机攻击；

（2）在BA无标度网络与ER随机网络中，同样的扰动值，施加给原图边带来的故障远远大于线图点，表明网络中的边比点更脆弱；

（3）线图与原图对节点施加扰动时，所得扰动值呈近似的线性关系。

根据表1和表2的数据，做拟合曲线如图6和图7所示，图中显示BA无标度网络和ER随机网络在随机攻击、蓄意攻击下的线图与原图的扰动阈值关系。

图6 BA网络线图与原图的扰动关系

图7 ER网络线图与原图的扰动关系

根据图6和图7可知，原图边与线图点的阈值可以近似落在一条直线上。说明对于BA无标度网络模型与ER随机网络模型，对原图中的节点和线图中的连边施加扰动时，线图结构与原图结构取得的阈值可以近似用以下线性关系表示，其中表示原图边的扰动值，表示线图点的扰动值：

（1）BA无标度网络随机扰动时，原图边与线图点的阈值关系近似为=0.72+3.34；

（2）BA无标度网络蓄意扰动时，原图边与线图点的扰动关系近似为=1.21+3.96；

（3）ER随机网络随机攻击节点时，扰动值符合=1.4+1.44；

（4）ER随机网络蓄意攻击节点时，扰动值符合=2.67－4.678。

[1] WHITNEY H. Congruent Graphs and the Connectivity of Graphs[J]. American Journal of Mathematics, 1932, 54(1): 150–168.

[2] 徐俊明.组合网络理论[M].北京：科学出版社，2007.

[3] HEMMINGER R L, BEINEKE L W. Line graphs and line digraphs[G]//Selected Topics in Graph Theory. London: Academic Press, 1978: 271–305.

[4] 郑梅容.无标度网络的相继故障及其中心化研究[D].武汉：华中师范大学，2012.

[5] 文宏，樊晓平，张会福，等. BA无标度网络性能优化方法研究[J].小型微型计算机系统，2016, 37(8): 1812–1815.

[6] 张彩艳.基于BA无标度网络的传输容量优化策略研究[D].西安：西安电子科技大学，2018.

[7] 文宏，樊晓平，张会福，等.无标度网络局部路由算法优化与设计[J].湖南大学学报(自然科学版)，2014, 41(10): 122– 128.

[8] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286: 509–512.

[9] 周秋花，邹艳丽.无标度网络的交通动力学行为研究[J].广西师范大学学报(自然科学版)，2010, 28(1): 6–9.

[10] 宗威豪. ER随机网络中新型雪堆博弈模型的研究[J].通讯世界，2018(5): 11–12.

[11] KANEKO K. Coupled Map Lattices[M]. Singapore: World Scientific, 1992.

[12] CUI Di, GAO Ziyou, ZHENG Jianfeng.Tolerance of edge cascades with coupled map lattices methods[J]. Chinese Physics B, 2009, 18(3): 992–996.

Research on simulation of successive faults of original graph edge and line graph point under disturbance

MA Shunli1, WANG Xiaohong2

(1. School of Computer, Qinghai Nationalities University, Xining 810007, China; 2. Qilu University of Technology (Shandong Academy of Sciences), Shandong Computer Science Center, (National Supercomputer Center in Ji’nan), Ji’nan 250101, China)

A line graph structure based on BA scale-free network and ER random network is proposed, and then the simulation experiment on point-edge disturbance of the line graph is carried out. By simulating the occurrence of faults, and with comparison of the threshold relationship between the line graph and the original graph in the simulation results, it can be seen that the scale of faults caused by the original graph is always larger than that caused by the line graph under the same disturbance value, regardless of attack point or attack edge, whether it is the intentional attack or random attack.

BA scale-free network; ER random network; successive faults; simulation experiment

O18

A

1002-4956(2019)10-0131-04

10.16791/j.cnki.sjg.2019.10.031

2019-03-24

2019-08-19

青海省自然科学基金项目（2017-ZJ-912）资助

马顺利（1970—），男，安徽萧县，硕士，讲师，主要研究领域为计算机网络与信息安全。E-mail: mashunli@sina.com

王小红（1982—），女，陕西宝鸡，博士，助理研究员，主要研究领域为图论与复杂网络，知识工程。E-mail: wangxiaoh@sdas.org