原圖邊與線圖點擾動的相繼故障仿真研究

馬順利，王小紅

原圖邊與線圖點擾動的相繼故障仿真研究

馬順利1，王小紅2

（1. 青海民族大學 計算機學院，青海 西寧 810007；2. 齊魯工業(yè)大學（山東省科學院），山東省計算中心（國家超級計算濟南中心），山東 濟南 250101）

提出基于BA無標度網絡和ER隨機網絡拓撲的線圖結構，繼而進行線圖點邊擾動仿真實驗。通過模擬故障的發(fā)生，對仿真結果中線圖與原圖間的閾值關系進行比較可知：不論攻擊點還是攻擊邊，不論蓄意攻擊還是隨機攻擊，在相同的擾動值下，原圖引起的故障規(guī)?？偸潜染€圖大。

BA無標度網絡；ER隨機網絡；相繼故障；仿真實驗

1 研究背景

線圖的概念是由Whitney[1]于1932年首先提出的，是從一個已知圖構造另一個更大的圖的重要方法。線圖中的許多圖論參數，比如頂點度、直徑、連通度、Euler和Hamilton性等都可以很方便地從原始圖導出。線圖是從圖中與邊有關的性質導出與頂點有關的性質的重要工具[2-3]，被廣泛用于互聯(lián)網拓撲結構設計。

設=（,）是無孤立點的簡單無向圖。的線圖（line graph）記為()，頂點集為()，對中任何兩條不同的邊1和2，它們在()中相鄰，當且僅當它們在中相鄰[2]。

可以利用這種方法，把BA無標度網絡[4-9]與ER[10]隨機網絡的原拓撲結構圖轉換為線圖結構。例如，圖1所示的是節(jié)點數18、邊數為70的ER隨機網絡圖和它的線圖()?？梢郧逦乜吹剑簣D中節(jié)點度分布是非常均勻的。

圖1 ER隨機網絡拓撲結構及其線圖

圖2所示的是節(jié)點數為18、邊數為46的BA無標度網絡￠和它的線圖(￠)。在圖￠中可以清晰地看到，BA無標度網絡表現(xiàn)出了優(yōu)先連接機制，新的節(jié)點總是傾向于與3個度最大的節(jié)點相連接。

圖2 BA無標度網絡拓撲結構與其線圖

2 相繼故障仿真模型

點擾動時，應用Kaneko K在20世紀90年代提出的耦合印象格子（CML）的相繼故障模型表達[11]。該模型被描述為

邊擾動時，應用崔迪提出的邊抗損壞模型表 達[12]，該模型被描述為

3 BA無標度網絡原圖邊與線圖點擾動的相繼故障仿真

3.1 仿真實驗與結果

圖3中的數據見表1。表1顯示了BA無標度網絡以隨機攻擊和蓄意攻擊兩種策略對原圖邊與線圖點施加擾動時，擾動閾值與故障規(guī)模的關系。BA無標度網絡的相繼故障過程中，當擾動幅值超過第一個臨界值1時，故障規(guī)模開始增大；在第二個臨界值2和第三個臨界值3中，故障規(guī)模保持同一水平；當擾動幅值超過第三個臨界值3時，故障規(guī)?？焖僭龃?；當擾動幅值超過第四個臨界值4時，網絡將出現(xiàn)全局故障。

圖3 BA網絡原圖邊、線圖點的攻擊閾值與故障規(guī)模的關系曲線

表1 BA無標度網絡原圖與線圖結構下的相繼故障與閾值關系

3.2 數據分析

分析圖3中的曲線以及表1中數據，可知：

（1）關于BA無標度網絡線圖點與原圖邊的相繼故障擴散過程。當隨機攻擊時，原圖邊的擾動臨界值4=5.4，線圖點的擾動臨界值4=7.6；當蓄意攻擊時，原圖邊的擾動臨界值4=3，線圖點的擾動臨界值4=7.6。

隨機攻擊與蓄意攻擊線圖點，其相繼故障過程如圖4所示。在相同的擾動幅值下，隨機攻擊下的故障規(guī)模要遠小于蓄意攻擊下的故障規(guī)模。

圖4 BA網絡線圖點的隨機、蓄意攻擊閾值與故障規(guī)模的關系曲線

3.3 仿真結果

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

（1）在BA無標度網絡的相繼故障過程中，對邊施加很小的擾動，就能引起很大的網絡故障，以致全局崩潰。特別是在蓄意攻擊時，邊攻擊達到全局崩潰的擾動值較小，而同樣大小的擾動施加給點，只能造成初始故障。

（2）在BA無標度網絡的相繼故障過程中，線圖點和原圖邊在蓄意攻擊下，更容易引起網絡的全局故障。對于原圖邊攻擊，引起全局故障的蓄意擾動值4比隨機擾動值4小。BA無標度網絡中相繼故障進程劇烈程度由大到小依次為：原圖邊蓄意攻擊>原圖邊隨機攻擊>線圖點蓄意攻擊>線圖點隨機攻擊。

4 ER隨機網絡原圖邊與線圖點擾動的相繼故障研究

4.1 仿真實驗與結果

圖5 ER網絡原圖邊、線圖點的攻擊閾值與故障規(guī)模的關系曲線

圖5中的數據見表2，表2顯示了ER隨機網絡以隨機攻擊和蓄意攻擊兩種策略對原圖邊與線圖點施加擾動時擾動閾值與故障規(guī)模的關系。

表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）在攻擊線圖點與原圖邊時，與隨機攻擊相比，蓄意攻擊時的相繼故障速度區(qū)別不大。

（3）ER隨機網絡中的線圖點隨機攻擊，持續(xù)時間最長，相繼故障進程最緩和。這是因為ER隨機網絡的度分布較均勻，并且線圖結構有極高的連通度，所以在隨機攻擊ER線圖點時，網絡體現(xiàn)出了很高的魯棒性。

5 結論

根據圖3、圖5仿真結果以及表1、表2中數據分析，得到結論如下：

（1）在BA無標度網絡與ER隨機網絡中，相繼故障進程劇烈程度由大到小為：原圖邊蓄意攻擊>原圖邊隨機攻擊>線圖點蓄意攻擊>線圖點隨機攻擊；

（2）在BA無標度網絡與ER隨機網絡中，同樣的擾動值，施加給原圖邊帶來的故障遠遠大于線圖點，表明網絡中的邊比點更脆弱；

（3）線圖與原圖對節(jié)點施加擾動時，所得擾動值呈近似的線性關系。

根據表1和表2的數據，做擬合曲線如圖6和圖7所示，圖中顯示BA無標度網絡和ER隨機網絡在隨機攻擊、蓄意攻擊下的線圖與原圖的擾動閾值關系。

圖6 BA網絡線圖與原圖的擾動關系

圖7 ER網絡線圖與原圖的擾動關系

根據圖6和圖7可知，原圖邊與線圖點的閾值可以近似落在一條直線上。說明對于BA無標度網絡模型與ER隨機網絡模型，對原圖中的節(jié)點和線圖中的連邊施加擾動時，線圖結構與原圖結構取得的閾值可以近似用以下線性關系表示，其中表示原圖邊的擾動值，表示線圖點的擾動值：

（1）BA無標度網絡隨機擾動時，原圖邊與線圖點的閾值關系近似為=0.72+3.34；

（2）BA無標度網絡蓄意擾動時，原圖邊與線圖點的擾動關系近似為=1.21+3.96；

（3）ER隨機網絡隨機攻擊節(jié)點時，擾動值符合=1.4+1.44；

（4）ER隨機網絡蓄意攻擊節(jié)點時，擾動值符合=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無標度網絡性能優(yōu)化方法研究[J].小型微型計算機系統(tǒng)，2016, 37(8): 1812–1815.

[6] 張彩艷.基于BA無標度網絡的傳輸容量優(yōu)化策略研究[D].西安：西安電子科技大學，2018.

[7] 文宏，樊曉平，張會福，等.無標度網絡局部路由算法優(yōu)化與設計[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