趙國濤 王立夫 關(guān)博飛

(東北大學(xué)秦皇島分校控制工程學(xué)院, 秦皇島 066004)

應(yīng)用復(fù)雜網(wǎng)絡(luò)描述大規(guī)模復(fù)雜系統(tǒng)間的相互作用已被廣泛接受, 網(wǎng)絡(luò)中某些邊遭受攻擊或破壞會使網(wǎng)絡(luò)不能控. 然而哪些邊失效后會對網(wǎng)絡(luò)能控性造成影響? 針對這一問題, 本文首先提出了類關(guān)鍵邊集的概念,并給出了類關(guān)鍵邊集的判定定理. 然后通過建立類關(guān)鍵邊集失效模型, 來研究類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響. 最后將類關(guān)鍵邊集失效、隨機失效、按度失效和按介數(shù)失效進行對比, 驗證了無論是在模型網(wǎng)絡(luò)(ER隨機網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)、隨機三角形網(wǎng)絡(luò)和隨機矩形網(wǎng)絡(luò)), 還是26種不同領(lǐng)域的實際網(wǎng)絡(luò)中, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的破壞力最大, 同時該結(jié)果為網(wǎng)絡(luò)邊攻擊提供了一種新方法.

1 引 言

隨著社會和科學(xué)技術(shù)的不斷發(fā)展, 電力網(wǎng)絡(luò)、社會關(guān)系網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等大型網(wǎng)絡(luò)漸漸進入我們的視線. 起初人們對于復(fù)雜網(wǎng)絡(luò)的關(guān)注點主要集中在拓?fù)浣Y(jié)構(gòu)特征上, 如網(wǎng)絡(luò)的小世界特性[1]、無標(biāo)度特性[2]等. 而研究復(fù)雜網(wǎng)絡(luò)的主要目的是控制網(wǎng)絡(luò)的行為, 減少不必要的損害, 更好地為社會服務(wù), 因此復(fù)雜網(wǎng)絡(luò)能控性受到越來越多學(xué)者的關(guān)注[3,4]. Lin[5]首次提出了結(jié)構(gòu)能控性理論,Liu等[6]利用圖的最大匹配計算網(wǎng)絡(luò)的驅(qū)動節(jié)點,解決了有向網(wǎng)絡(luò)的最小輸入問題. 然而有些網(wǎng)絡(luò),僅僅通過給驅(qū)動節(jié)點添加輸入仍無法使網(wǎng)絡(luò)結(jié)構(gòu)能控, 為了求解使網(wǎng)絡(luò)結(jié)構(gòu)能控的最小受控節(jié)點,Pequito等[7]提出了一種結(jié)構(gòu)能控性框架, Yin和Zhang[8]給出一個帶有約束的數(shù)學(xué)模型. 以上針對的是有向網(wǎng)絡(luò)能控性, 對于無向網(wǎng)絡(luò)的控制,Yuan等[9]利用PBH判據(jù)提出復(fù)雜網(wǎng)絡(luò)的嚴(yán)格能控性判據(jù), 該理論適用于任意結(jié)構(gòu)和邊權(quán)值的網(wǎng)絡(luò), 解決了無向網(wǎng)絡(luò)的能控性問題. 根據(jù)網(wǎng)絡(luò)能控性衍生出來的問題, 例如最小化[10,11]、邊控制[12]和對稱網(wǎng)絡(luò)能控性[13]的研究, 都為復(fù)雜網(wǎng)絡(luò)能控性的發(fā)展提供了新的思路. 與此同時, 對實際網(wǎng)絡(luò)能控性的研究也從未止步, 例如交通網(wǎng)絡(luò)能控性[14,15]、腦網(wǎng)絡(luò)能控性[16]、電力網(wǎng)絡(luò)能控性[17]等, 都具有重要的現(xiàn)實意義.

通過對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究可以更好地認(rèn)識和利用網(wǎng)絡(luò). 人們對網(wǎng)絡(luò)中節(jié)點屬性的研究取得一些成果, 文獻[18]通過節(jié)點分類發(fā)現(xiàn)了網(wǎng)絡(luò)的雙峰現(xiàn)象, 文獻[19, 20]通過節(jié)點分類解決了增長網(wǎng)絡(luò)能控性問題. 但是在邊屬性方面的研究相對較少,Liu等[6]根據(jù)邊失效后對網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)的影響, 將邊分為三類: 關(guān)鍵邊、冗余邊和普通邊.

當(dāng)一個網(wǎng)絡(luò), 由于自身原因或外部攻擊, 導(dǎo)致某些邊失效時, 可能使整個網(wǎng)絡(luò)不能控, 因此網(wǎng)絡(luò)能控魯棒性受到越來越多的關(guān)注. 對于網(wǎng)絡(luò)邊攻擊, 最常見的攻擊方法有隨機、按度和按介數(shù)攻擊.例如, Ruths等[21]研究了在給定一組驅(qū)動節(jié)點的前提下, 邊移除對網(wǎng)絡(luò)受控節(jié)點數(shù)量的影響.Lu和Li[22]研究了將邊按隨機攻擊、初始度攻擊、初始介數(shù)攻擊和重新計算度攻擊、重新計算介數(shù)攻擊對網(wǎng)絡(luò)能控性的影響, 結(jié)果表明重新計算比按初始值攻擊邊對網(wǎng)絡(luò)能控性損害更大. Thomas等[23]分析了在基于度和隨機的邊攻擊下, 用能控性和可達性來度量每次攻擊后受控節(jié)點位置的改變情況.Chen等[24]在6種有向模型網(wǎng)絡(luò)中研究了邊在按隨機攻擊、重新計算度攻擊、重新計算介數(shù)攻擊時,對能控性的影響, 并展示了多環(huán)結(jié)構(gòu)在網(wǎng)絡(luò)中的良好性能. 以上的研究都沒有考慮網(wǎng)絡(luò)中某條邊失效后對周圍邊的影響, 因為網(wǎng)絡(luò)復(fù)雜的拓?fù)浣Y(jié)構(gòu), 有時候某些邊的失效可能引發(fā)局部的故障, 進而導(dǎo)致整個網(wǎng)絡(luò)崩潰[25,26], 因此Nie等[27]研究了單邊攻擊和邊級聯(lián)失效對網(wǎng)絡(luò)能控性的影響, 并且發(fā)現(xiàn)在無標(biāo)度網(wǎng)絡(luò)中, 級聯(lián)失效并不意味著驅(qū)動節(jié)點的增加. 不同于以往基于常見的模型網(wǎng)絡(luò)(隨機網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)等)的研究, Lou等[28]提出了q-snapback網(wǎng)絡(luò)模型, 并與multiplex congruence網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)進行對比, 研究了基于目標(biāo)和隨機邊攻擊下的網(wǎng)絡(luò)魯棒性. 除了研究網(wǎng)絡(luò)的單邊失效, Shang[29]通過引入子圖魯棒性, 建立了一個分析框架來研究兩類子圖在隨機攻擊、局部攻擊和目標(biāo)攻擊下的魯棒性.

通過以上分析可知, 當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)與能控性關(guān)系的研究, 主要集中在具有某種網(wǎng)絡(luò)拓?fù)鋵傩?度、介數(shù)等)的單個節(jié)點或邊失效對網(wǎng)絡(luò)能控性的影響上, 缺少一種直接影響網(wǎng)絡(luò)能控性的方法. 本文主要研究了一類影響網(wǎng)絡(luò)能控性的邊集—“類關(guān)鍵邊集”, 通過邊分類和節(jié)點分類得到了類關(guān)鍵邊集的判定定理, 給出類關(guān)鍵邊集失效模型, 并推導(dǎo)出失效的理論函數(shù). 通過將類關(guān)鍵邊集失效和常見的3種邊失效方式(隨機失效、按度失效、按介數(shù)失效)對比, 在4種模型網(wǎng)絡(luò)(ER 隨機網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)、隨機三角形網(wǎng)絡(luò)和隨機矩形網(wǎng)絡(luò))和實際網(wǎng)絡(luò)中進行邊攻擊, 分析類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響.

本文在論述時安排如下: 第2節(jié)主要介紹復(fù)雜網(wǎng)絡(luò)能控性的基本概念和網(wǎng)絡(luò)能控魯棒性指標(biāo);第3節(jié)根據(jù)節(jié)點分類和邊分類, 提出類關(guān)鍵邊集的概念, 給出類關(guān)鍵邊集失效模型, 并推導(dǎo)其失效后的理論曲線; 第4節(jié)研究在模型網(wǎng)絡(luò)和實際網(wǎng)絡(luò)中不同邊失效方式下對網(wǎng)絡(luò)能控性的影響; 第5節(jié)對論文的成果進行總結(jié), 并且給出今后的研究方向.

2 復(fù)雜網(wǎng)絡(luò)能控性

2.1 定 義

對于有向網(wǎng)絡(luò)G(A)=(X,E) , 其中節(jié)點集X={x1,x2,...,xN}, 邊集E={e1,e2,···,eM}.A=(aij)N×N表示有向網(wǎng)絡(luò)G(A) 的鄰接矩陣,aij表示節(jié)點j對節(jié)點i的影響強度. 當(dāng)aij=0 時,表示節(jié)點j和節(jié)點i之間不存在有向邊 (xj→xi) ;當(dāng)時,aij的值越大, 表示節(jié)點j對節(jié)點i的影響強度越大.

對于有向網(wǎng)絡(luò)G(A) , 將網(wǎng)絡(luò)中所有邊的方向翻轉(zhuǎn)后形成的新網(wǎng)絡(luò)記為G(AT) , 稱G(AT) 為原網(wǎng)絡(luò)G(A) 的轉(zhuǎn)置網(wǎng)絡(luò), 原網(wǎng)絡(luò)G(A) 中的邊(xi→xj) 和轉(zhuǎn)置網(wǎng)絡(luò)中的邊 (xj→xi) 互為轉(zhuǎn)置邊.如圖1(a) 所示的網(wǎng)絡(luò), 當(dāng)其所有邊的方向翻轉(zhuǎn)之后, 形成的轉(zhuǎn)置網(wǎng)絡(luò)如圖1(b)所示. 網(wǎng)絡(luò)中一共存在7 對轉(zhuǎn)置邊, 分別是邊 (x4→x1) 和邊 (x1→x4) ,(x4→x3) 和邊 (x3→x4) , (x4→x5) 和邊 (x5→x4) ,(x4→x6) 和邊 (x6→x4) , (x1→x2) 和邊 (x2→x1) ,(x3→x2) 和邊 (x2→x3) , (x6→x5) 和邊 (x5→x6).

圖1 原網(wǎng)絡(luò)與轉(zhuǎn)置網(wǎng)絡(luò) (a) 原網(wǎng)絡(luò); (b) 轉(zhuǎn)置網(wǎng)絡(luò)Fig. 1. Original network and transpose network: (a) Originalnetwork; (b) transpose network.

有向網(wǎng)絡(luò)G(A) 邊集的一個子集合中任意兩條邊沒有公共的始點也沒有公共的終點, 稱這個子集為網(wǎng)絡(luò)G(A) 的一個匹配集. 如果一個節(jié)點是匹配集中某條邊的終點, 稱該節(jié)點為匹配節(jié)點, 否則該節(jié)點為未匹配節(jié)點. 網(wǎng)絡(luò)G(A) 的匹配集中所含邊數(shù)最多的匹配集被稱為最大匹配. 如果一個網(wǎng)絡(luò)的某個匹配中, 所有的頂點都是匹配節(jié)點, 稱該匹配為一個完美匹配.

對一個有向網(wǎng)絡(luò)G(A) 而言, 它可能存在多組不同的最大匹配. 有向網(wǎng)絡(luò)的最大匹配可以通過對應(yīng)的二部圖得到, 具體做法通過以下方式構(gòu)造:

2.2 有向網(wǎng)絡(luò)系統(tǒng)動力學(xué)方程

線性時不變系統(tǒng)動力學(xué)方程可以表示為

其中,x(t)=(x1(t),x2(t),···,xN(t))T為狀態(tài)向量,A∈RN×N為狀態(tài)矩陣,B∈RN×M稱為輸入矩陣,u(t)=(u1(t),u2(t),···,uM(t))T為輸入向量.

將線性時不變系統(tǒng)(LTI)引入到有向網(wǎng)絡(luò)中,得到有向網(wǎng)絡(luò)系統(tǒng)G(A,B)=(XA∪XB,EA∪EB) ,其中XA={x1,x2,···,xN},XB={u1,u2,···,uM},aij表示節(jié)點j對節(jié)點i的影響強度,aij的值越大, 影響強度越大.EB=bij表示在t時刻將輸入信號uj(t) 作用于節(jié)點i.

2.3 結(jié)構(gòu)能控性

對于一個線性時不變系統(tǒng), 若存在一個分段連續(xù)的輸入u(t) , 能夠在有限時間 [t0,tf] 內(nèi)使得系統(tǒng)從任意初始狀態(tài)x(t0) 轉(zhuǎn)移到任意終止?fàn)顟B(tài)x(tf) , 則稱此系統(tǒng)是狀態(tài)能控的. 在控制理論中, Kalman[32]提出的能控性判據(jù)為判斷系統(tǒng)能控性提供了代數(shù)方法, 即系統(tǒng)完全能控的充分必要條件是矩陣

為滿秩, 即 r ank(C)=N, 其中C被稱為能控性矩陣.

在實際中, 有些網(wǎng)絡(luò)邊權(quán)重不可測, 或者隨著時間的變化而改變, 因此, Lin[5]提出了結(jié)構(gòu)能控性的概念. 在網(wǎng)絡(luò)系統(tǒng)G(A,B) 中 , 矩陣A和矩陣B被認(rèn)為是結(jié)構(gòu)化的, 即它們的元素要么是固定的零, 要么是獨立的自由參數(shù). 只需要考慮網(wǎng)絡(luò)本身的拓?fù)浣Y(jié)構(gòu), 而不需要考慮網(wǎng)絡(luò)節(jié)點間的真實權(quán)重. 如果將G(A) 中的自由參數(shù)固定到某一確定值, 使所得到的網(wǎng)絡(luò)系統(tǒng)G(A,B) 在通常意義上( r ank(C)=N)是能控的, 則該網(wǎng)絡(luò)系統(tǒng)G(A,B)是結(jié)構(gòu)能控的.

在輸入矩陣B中, 和輸入節(jié)點連接的狀態(tài)節(jié)點稱為受控節(jié)點, 那些不共享輸入節(jié)點的受控節(jié)點稱為驅(qū)動節(jié)點. 滿足網(wǎng)絡(luò)結(jié)構(gòu)能控所需的最少的驅(qū)動節(jié)點的集合就是最小驅(qū)動節(jié)點集(minimum driver node set, MDS), MDS可以通過最小輸入定理[6]求出.

引理1 最小輸入定理完全控制有向網(wǎng)絡(luò)G(A) 所需要的最少輸入節(jié)點數(shù)NI或者最少驅(qū)動節(jié)點數(shù)ND取決于網(wǎng)絡(luò)G(A) 的最大匹配, 如果G(A) 存在完美匹配, 則ND等于1并可選擇網(wǎng)絡(luò)中的任一節(jié)點作為驅(qū)動節(jié)點; 如果G(A) 不存在完美匹配, 則ND等于網(wǎng)絡(luò)中的未匹配節(jié)點數(shù), 并且未匹配的節(jié)點就是所尋找的驅(qū)動節(jié)點. 即:

其中M表示網(wǎng)絡(luò)G(A) 的一個最大匹配,|M|表示網(wǎng)絡(luò)G(A) 最大匹配的邊數(shù).

對于有向網(wǎng)絡(luò), 某些邊會因為外界或自身因素而失效, 為了評判邊失效后對網(wǎng)絡(luò)能控性的影響,可以由控制節(jié)點密度nD來量化, 其定義為控制網(wǎng)絡(luò)所需要的最小驅(qū)動節(jié)點數(shù)ND占網(wǎng)絡(luò)節(jié)點總數(shù)N的比例, 記為

其中,nD的大小反映復(fù)雜網(wǎng)絡(luò)控制的難易程度, 其值越小, 說明網(wǎng)絡(luò)達到完全能控所需的驅(qū)動節(jié)點數(shù)占總節(jié)點數(shù)的比例越小, 網(wǎng)絡(luò)越容易控制, 同時網(wǎng)絡(luò)的能控魯棒性越好.

3 類關(guān)鍵邊集對網(wǎng)絡(luò)能控性的影響

3.1 節(jié)點分類與邊分類

對于給定的網(wǎng)絡(luò), 當(dāng)網(wǎng)絡(luò)滿足結(jié)構(gòu)能控時, 所需的最少的驅(qū)動節(jié)點的個數(shù)是固定的. 然而, 一個網(wǎng)絡(luò)可能存在多組最大匹配, 導(dǎo)致網(wǎng)絡(luò)存在多種MDSs. 根據(jù)每個節(jié)點參與MDS的程度[18], 將網(wǎng)絡(luò)節(jié)點分成三類, 定義如下.

定義1如果一個節(jié)點參與所有的MDSs, 則這個節(jié)點稱為關(guān)鍵節(jié)點; 如果一個節(jié)點不全參與所有的MDSs, 則這個節(jié)點稱為間歇節(jié)點; 如果一個節(jié)點不參與任何一個MDSs, 則這個節(jié)點稱為冗余節(jié)點.

對于圖1(a)所示的網(wǎng)絡(luò), 所有可能的最大匹配和MDS如圖2(a). 節(jié)點4參與所有MDSs, 因此為關(guān)鍵節(jié)點. 節(jié)點1, 3, 6不全參與所有MDSs,因此為間歇節(jié)點. 節(jié)點2, 5不參與任何一個MDSs, 因此為冗余節(jié)點, 結(jié)果如圖2(b)所示.

類似地, 根據(jù)每條邊參與最大匹配的程度, 將所有邊分成三類, 定義如下.

定義2如果一條邊參與所有的最大匹配, 則這條邊稱為關(guān)鍵邊; 如果一條邊不全參與所有的最大匹配, 則這條邊稱為間歇邊; 如果一條邊不參與所有的最大匹配, 則這條邊稱為冗余邊.

對于圖1(a)所示的網(wǎng)絡(luò), 所有可能的最大匹配如圖2(a). 根據(jù)定義2, 對網(wǎng)絡(luò)中邊進行分類, 結(jié)果見圖2(b). 其中, 邊 (x6→x5) 參與所有的最大匹配, 為關(guān)鍵邊. 邊 (x4→x1) , (x4→x3) , (x4→x6) ,

圖2 有向網(wǎng)絡(luò)節(jié)點分類和邊分類 (a) 有向網(wǎng)絡(luò)所有可能的最大匹配以及對應(yīng)的MDS; (b) 節(jié)點分類和邊分類Fig. 2. Directed network node classification and edge classification: (a) All possible maximum matching and corresponding MDS of directed network; (b) node classification and edge classification.

(x3→x2) , (x1→x2) 不全參與所有的最大匹配,因此為間歇邊. 邊 (x4→x5) 不參與所有的最大匹配, 因此為冗余邊.

在定義2中, 通過分析邊在最大匹配中的參與程度, 將網(wǎng)絡(luò)中所有邊分成了三類, 而最大匹配中邊的個數(shù)會直接影響網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)ND, 下述定理1討論了三類邊失效后對網(wǎng)絡(luò)能控性的影響.

定理1 網(wǎng)絡(luò)中不同類型的邊失效對能控性的影響

1) 當(dāng)關(guān)鍵邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)減少1, 驅(qū)動節(jié)點個數(shù)ND增加1;

2) 當(dāng)間歇邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)不變, 驅(qū)動節(jié)點個數(shù)ND保持不變, 但是網(wǎng)絡(luò)所有可能的最大匹配個數(shù)將減少;

3) 當(dāng)冗余邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)不變, 網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)ND保持不變, 網(wǎng)絡(luò)所有可能的最大匹配個數(shù)不變.

證明

1) 反證法: 對于給定的有向網(wǎng)絡(luò)G(A) , 存在最大匹配M,|M|表示最大匹配中的邊數(shù). i)假設(shè)關(guān)鍵邊失效后, 網(wǎng)絡(luò)最大匹配的邊數(shù)增加t,t＞0.那么在關(guān)鍵邊不失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)就是|M|+t, 與最大匹配的邊數(shù)唯一矛盾. 因此關(guān)鍵邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)不會增加. ii)假設(shè)關(guān)鍵邊失效后, 網(wǎng)絡(luò)最大匹配的邊數(shù)保持不變. 那么在關(guān)鍵邊不失效時, 關(guān)鍵邊就不會一直參與最大匹配, 與關(guān)鍵邊定義矛盾. 因此關(guān)鍵邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)不會保持不變. iii)假設(shè)關(guān)鍵邊失效后, 網(wǎng)絡(luò)最大匹配的邊數(shù)減少r,r＞1. 當(dāng)關(guān)鍵邊失效后, 假如現(xiàn)在的最大匹配M’ 為原最大匹配M除去關(guān)鍵邊, 則M’ 對應(yīng)的最大匹配邊數(shù)為|M|-1 ,與假設(shè)的最大匹配的邊數(shù)為|M|-r,r＞1 矛盾.因此關(guān)鍵邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)不會減少r,r＞1. 綜上i) ii) iii)所述, 當(dāng)關(guān)鍵邊失效時, 網(wǎng)絡(luò)最大匹配的邊數(shù)減少1, 根據(jù)引理1, 驅(qū)動節(jié)點個數(shù)ND增加1.

2) 由于間歇邊不全參與最大匹配, 至少存在一個最大匹配不包含要失效的間歇邊, 因此間歇邊的失效不影響最大匹配的邊數(shù), 驅(qū)動節(jié)點個數(shù)ND也保持不變. 由于去掉了間歇邊, 也就去掉了所有包含該失效間歇邊的最大匹配, 因此網(wǎng)絡(luò)所有可能的最大匹配個數(shù)將減少.

3) 由于冗余邊不參與最大匹配, 因此冗余邊去掉之后對網(wǎng)絡(luò)最大匹配無影響, 網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)ND保持不變, 網(wǎng)絡(luò)所有可能的最大匹配個數(shù)也不變.

通過定理1, 將每個不同類型的邊與網(wǎng)絡(luò)能控性(驅(qū)動節(jié)點個數(shù)ND)建立了聯(lián)系.

在對網(wǎng)絡(luò)中的邊進行分類時, 根據(jù)定義2, 需要求出網(wǎng)絡(luò)所有的最大匹配, 但這是一個NP問題[33]. 由于給定網(wǎng)絡(luò)的最大匹配邊數(shù)是固定的, 因此, 從最大匹配邊數(shù)變化的角度來對邊分類將是一個可行的方法. 根據(jù)定理1可知, 關(guān)鍵邊失效后,會使網(wǎng)絡(luò)最大匹配邊數(shù)減少1; 冗余邊總是不參與最大匹配, 如果被強制參與匹配(去掉和該邊同出節(jié)點以及同入節(jié)點的所有邊), 會使原來參與最大匹配的兩條邊不參與最大匹配, 網(wǎng)絡(luò)中最大匹配邊數(shù)與之前相比將減少1; 如果一條邊既不屬于關(guān)鍵邊又不屬于冗余邊, 則為間歇邊. 綜上三種情況,可以給出網(wǎng)絡(luò)邊分類的算法:

算法1 網(wǎng)絡(luò)中邊分類算法

Step 1: 求出網(wǎng)絡(luò)一組最大匹配, 記匹配邊數(shù)為m;

Step 2: 遍歷網(wǎng)絡(luò)中所有的邊, 如果存在一條邊 (xi→xj) , 在去掉該邊后, 新網(wǎng)絡(luò)的最大匹配邊數(shù)m1滿足m1=m-1 , 則該邊為關(guān)鍵邊;

Step 3: 遍歷網(wǎng)絡(luò)中所有的邊, 如果存在一條邊 (xi→xj) , 在去掉和該邊同出節(jié)點以及同入節(jié)點的所有邊后, 新網(wǎng)絡(luò)的最大匹配邊數(shù)m2滿足m2=m-1, 則該邊為冗余邊;

Step 4: 遍歷網(wǎng)絡(luò)中所有的邊, 如果存在一條邊 (xi→xj) , 既不屬于關(guān)鍵邊又不屬于冗余邊, 則該邊為間歇邊.

3.2 類關(guān)鍵邊集概念

網(wǎng)絡(luò)中某個或某些邊的失效會影響網(wǎng)絡(luò)能控性, 使網(wǎng)絡(luò)滿足結(jié)構(gòu)能控所需的最小的驅(qū)動節(jié)點個數(shù)增加, 本文研究了一類影響網(wǎng)絡(luò)能控性的邊集稱為“類關(guān)鍵邊集”, 其定義如下:

定義3對于網(wǎng)絡(luò)中的一組邊集EC, 當(dāng)EC同時失效時網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)(ND)增加1, 并且當(dāng)EC中任意|EC|-1 條邊失效時網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)(ND)保持不變, 則稱邊集EC為類關(guān)鍵邊集.

注1|EC|-1 表示邊集EC中的邊數(shù)減1. 根據(jù)定義3可以知道, 對于存在類關(guān)鍵邊集的有向網(wǎng)絡(luò), 移除任意一個類關(guān)鍵邊集, 都會使ND增加1.

由于類關(guān)鍵邊集是一組邊的集合, 不同的類關(guān)鍵邊集, 其元素個數(shù)不一定相同. 因此類關(guān)鍵邊集根據(jù)元素的多少, 又可以細(xì)分.

定義4邊數(shù)為1的類關(guān)鍵邊集稱為1-元類關(guān)鍵邊集. 邊數(shù)為2的類關(guān)鍵邊集稱為2-元類關(guān)鍵邊集. 同理, 邊數(shù)為x的類關(guān)鍵邊集稱為x-元類關(guān)鍵邊集.

3.3 類關(guān)鍵邊集的辨識

對于一個有向網(wǎng)絡(luò), 通過定義3, 很難求出網(wǎng)絡(luò)中所有的類關(guān)鍵邊集, 因此下面給出類關(guān)鍵邊集判定定理.

定理2 類關(guān)鍵邊集判定定理

1) 有向網(wǎng)絡(luò)G(A) 中指向同一個冗余節(jié)點的所有間歇邊的集合, 一定為類關(guān)鍵邊集;

2) 有向網(wǎng)絡(luò)G(A) 的轉(zhuǎn)置網(wǎng)絡(luò)G(AT) 中指向同一冗余節(jié)點的所有間歇邊的轉(zhuǎn)置邊的集合, 一定為類關(guān)鍵邊集.

證明

1) 根據(jù)冗余節(jié)點的定義, 冗余節(jié)點一定不參與MDSs, 因此冗余節(jié)點一定是匹配節(jié)點, 并且指向冗余節(jié)點的邊中一定存在一條匹配邊. 根據(jù)間歇邊的定義, 間歇邊會參與最大匹配, 因此, 對于指向同一個冗余節(jié)點的所有的x條間歇邊, 只有一條參與最大匹配, 而只有把這x條間歇邊全部去掉才可以使網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)增加1.

2) 與1)同理, 只有轉(zhuǎn)置網(wǎng)絡(luò)中指向同一個冗余節(jié)點的所有間歇邊全部去掉之后, 才可以使轉(zhuǎn)置網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)增加1, 其對應(yīng)的原網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)也增加1.

注2根據(jù)定義3, 有向網(wǎng)絡(luò)中的關(guān)鍵邊, 一定為類關(guān)鍵邊集.

通過以上分析可以知道, 關(guān)鍵邊是一種特殊的類關(guān)鍵邊集, 而類關(guān)鍵邊集是關(guān)鍵邊在能控性方面的推廣. 通過定理2, 可以得到對應(yīng)的類關(guān)鍵邊集搜尋算法.

算法2 類關(guān)鍵邊集搜尋算法

Step 1: 對原網(wǎng)絡(luò)進行節(jié)點分類和邊分類, 找出關(guān)鍵節(jié)點、間歇節(jié)點和冗余節(jié)點, 關(guān)鍵邊、間歇邊和冗余邊;

Step 2: 記每個關(guān)鍵邊為1-元類關(guān)鍵邊集;

Step 3: 遍歷所有的冗余節(jié)點, 將指向同一個冗余節(jié)點的所有的x條間歇邊記為x-元類關(guān)鍵邊集(x=2,3,···);

Step 4: 求原網(wǎng)絡(luò)的轉(zhuǎn)置網(wǎng)絡(luò), 并對轉(zhuǎn)置網(wǎng)絡(luò)進行邊分類和節(jié)點分類, 找出轉(zhuǎn)置網(wǎng)絡(luò)中的關(guān)鍵節(jié)點、間歇節(jié)點和冗余節(jié)點, 關(guān)鍵邊、間歇邊和冗余邊;

Step 5: 遍歷轉(zhuǎn)置網(wǎng)絡(luò)中所有的冗余節(jié)點, 將指向同一個冗余節(jié)點的所有的x條間歇邊的轉(zhuǎn)置邊記為x-元類關(guān)鍵邊集(x=2,3,···).

對于圖1(a)所示的網(wǎng)絡(luò), 其原網(wǎng)絡(luò)和轉(zhuǎn)置網(wǎng)絡(luò)的節(jié)點分類和邊分類如圖3(a)和圖3(b)所示.通過類關(guān)鍵邊集搜尋算法, 網(wǎng)絡(luò)中所有的x-元類關(guān)鍵邊集如圖3(c)所示, 在原網(wǎng)絡(luò)中, 邊(x6→x5)為關(guān)鍵邊, 因此為1-元類關(guān)鍵邊集. 邊 (x1→x2) ,(x3→x2)為指向冗余節(jié)點2的所有間歇邊, 因此為2-元類關(guān)鍵邊集. 在轉(zhuǎn)置網(wǎng)絡(luò)中, 邊 (x1→x4) ,(x3→x4) , (x6→x4) 是指向冗余節(jié)點4的所有間歇邊, 因此其轉(zhuǎn)置邊 (x4→x1) , (x4→x3) ,(x4→x6)為3-元類關(guān)鍵邊集.

圖3 尋找有向網(wǎng)絡(luò)中的類關(guān)鍵邊集 (a), (b) 原網(wǎng)絡(luò)和轉(zhuǎn)置網(wǎng)絡(luò)中的節(jié)點分類和邊分類; (c) 網(wǎng)絡(luò)中的類關(guān)鍵邊集Fig. 3. Find the quasi-critical edge set in directed network:(a), (b) Node classification and edge classification in original network and transpose network; (c) quasi-critical edge set in the network.

3.4 類關(guān)鍵邊集失效對能控性影響分析

為了研究類關(guān)鍵邊集失效后對網(wǎng)絡(luò)能控性的影響, 提出了類關(guān)鍵邊集失效模型.

類關(guān)鍵邊集失效模型

Step 1: 搜尋網(wǎng)絡(luò)中所有的x-元類關(guān)鍵邊集(x=1,2,3,···);

Step 2: 任意選擇一個元素最少的x-元類關(guān)鍵邊集(x=1,2,3,···), 將其包含的所有邊在網(wǎng)絡(luò)中移除;

Step 3: 計算邊移除比例p和新網(wǎng)絡(luò)的能控性nD;

Step 4: 檢查網(wǎng)絡(luò)中是否存在邊. 如果存在邊,轉(zhuǎn)向Step1, 否則結(jié)束運行.

由于每次失效都會選擇一個類關(guān)鍵邊集, 根據(jù)類關(guān)鍵邊集的定義, 每移除一個x-元類關(guān)鍵邊集(x=1,2,3,···), 都使網(wǎng)絡(luò)驅(qū)動節(jié)點個數(shù)增加1, 因此網(wǎng)絡(luò)能控性nD與邊移除比例p之間存在正比關(guān)系, 即能控性nD與邊移除比例p的理論關(guān)系曲線為一次分段函數(shù).

假設(shè)在n個節(jié)點,e條邊的有向網(wǎng)絡(luò)中, 最大匹配的邊數(shù)為m(m≤n) 個. 網(wǎng)絡(luò)中所有邊都失效后, 假設(shè)一共移除了c1個1-元類關(guān)鍵邊集,c2個2-元類關(guān)鍵邊集,c3個3-元類關(guān)鍵邊集,···,cj個j-元類關(guān)鍵邊集,···,ci個i-元類關(guān)鍵邊集(m=則能控性nD與邊移除比例p的理論函數(shù)為

根據(jù)以上分析, 可以畫出失效函數(shù)的理論曲線, 如圖4所示, 可以更加直觀地看出類關(guān)鍵邊集失效后曲線的分段性和一次性. 通過對曲線的分析, 可以得到其斜率為

圖4 基于類關(guān)鍵邊集的邊失效理論曲線Fig. 4. Theoretical curve of edge failure based on quasi-critical edge set.

其中,x為每次失效的類關(guān)鍵邊集中邊的數(shù)量. 對于給定的網(wǎng)絡(luò), 斜率的最小值和最大值取決于x的大小. 當(dāng)x=1 時, 即網(wǎng)絡(luò)存在1-元類關(guān)鍵邊集, 代入(7)式, 有斜率最大值〈kin〉=〈kout〉, 由于優(yōu)先攻擊邊數(shù)少的類關(guān)鍵邊集,因此其初始斜率就是最大斜率, 并且初始斜率的大小與網(wǎng)絡(luò)平均度 〈k〉 有關(guān). 當(dāng)x→∞時, 代入(7)式, 有最小值由于網(wǎng)絡(luò)的邊數(shù)是有限的, 因此其最小斜率只能無限趨向于0.

下面通過一個實例介紹類關(guān)鍵邊集失效過程,對于圖1(a)所示網(wǎng)絡(luò), 其驅(qū)動節(jié)點個數(shù)為3. 按照類關(guān)鍵邊集失效模型, 尋找網(wǎng)絡(luò)x-元類關(guān)鍵邊集,如圖5(a). 優(yōu)先移除元素個數(shù)為1的1-元類關(guān)鍵邊集 (x6→x5) , 此時新網(wǎng)絡(luò)驅(qū)動節(jié)點數(shù)由3變成4. 重新尋找新網(wǎng)絡(luò)x-元類關(guān)鍵邊集, 如圖5(b)所示, 移除2-元類關(guān)鍵邊集 (x1→x2) , (x3→x2) , 此時新網(wǎng)絡(luò)驅(qū)動節(jié)點數(shù)由4變成5. 重新尋找新網(wǎng)絡(luò)x-元類關(guān)鍵邊集, 如圖5(c)所示, 移除4-元類關(guān)鍵邊集 (x4→x1) , (x4→x3) , (x4→x5) , (x4→x6) ,此時新網(wǎng)絡(luò)節(jié)點全部變成孤立節(jié)點, 驅(qū)動節(jié)點數(shù)由5變成6, 如圖5(d)所示.

圖5 圖1(a) 所示網(wǎng)絡(luò)的邊失效過程Fig. 5. The edge failure process of the network shown in Fig. 1(a).

根據(jù)以上失效過程, 可以計算出邊失效比例p對網(wǎng)絡(luò)能控性nD影響的曲線, 與上述攻擊過程相符, 一共由3段不同斜率、不同截距的一次函數(shù)組成, 如圖6所示, 斜率分別為分析斜率的大小可以知道, 當(dāng)斜率越大時, 說明一定數(shù)量的邊失效后, 對網(wǎng)絡(luò)能控性破壞越大, 網(wǎng)絡(luò)保持能控所需的ND就越多. 當(dāng)斜率越小時, 說明一定數(shù)量的邊失效后, 對網(wǎng)絡(luò)能控性破壞越小, 網(wǎng)絡(luò)保持能控所需的ND就越少.

圖6 圖1(a)所示網(wǎng)絡(luò)的邊失效曲線Fig. 6. The edge failure curve of the network shown in Fig. 1(a).

對于任何有向網(wǎng)絡(luò), 其任意一條邊失效后, 驅(qū)動節(jié)點個數(shù)最多增加1. 當(dāng)關(guān)鍵邊失效時, 會使網(wǎng)絡(luò)驅(qū)動節(jié)點數(shù)增加1, 因此關(guān)鍵邊是對網(wǎng)絡(luò)能控性影響最大的一類邊; 當(dāng)網(wǎng)絡(luò)中無關(guān)鍵邊時, 失效任意一條邊驅(qū)動節(jié)點數(shù)不會增加, 此時失效多條邊可導(dǎo)致驅(qū)動節(jié)點數(shù)增加,x-元類關(guān)鍵邊集 (x≥2) 成為失效后使驅(qū)動節(jié)點個數(shù)增加1的邊數(shù)最少的邊集, 此時x-元類關(guān)鍵邊集是對網(wǎng)絡(luò)能控性影響最大的邊集. 由于關(guān)鍵邊可作為邊數(shù)為1的類關(guān)鍵邊集, 因此在失效相同邊數(shù)的情況下, 類關(guān)鍵邊集對網(wǎng)絡(luò)能控性的影響是最大的. 在某些應(yīng)用背景下,需要保持較高網(wǎng)絡(luò)能控性時, 可對類關(guān)鍵邊集按次序進行重點保護.

4 仿 真

4.1 網(wǎng)絡(luò)中不同屬性邊占比研究

為了研究3種不同類型的邊(關(guān)鍵邊、間歇邊和冗余邊)占網(wǎng)絡(luò)總邊數(shù)的比例p, 分別選取了4種節(jié)點總數(shù)為500的模型網(wǎng)絡(luò)(ER隨機網(wǎng)絡(luò)[34]、BA無標(biāo)度網(wǎng)絡(luò)[2]、隨機三角形網(wǎng)絡(luò)[35,36]和隨機矩形網(wǎng)絡(luò)[24])進行仿真.

對于ER隨機網(wǎng)絡(luò), 平均度〈k〉=〈kin〉=〈kout〉從1增加到30, 每次增加1. 對于BA無標(biāo)度網(wǎng)絡(luò),新節(jié)點作為弧頭連接的節(jié)點數(shù)min等于新節(jié)點作為弧尾連接的節(jié)點數(shù)mout都從1增加到30, 每次初始網(wǎng)絡(luò)存在min+1 個 節(jié)點和min+1 條邊, 首尾連接, 保證網(wǎng)絡(luò)的連通性. 對于隨機三角形網(wǎng)絡(luò), 平均度從3開始, 增加到30, 每次增加1. 對于隨機矩形網(wǎng)絡(luò), 平均度從4開始, 增加到30, 每次增加1. 對于每個確定度下的網(wǎng)絡(luò), 運行50次后取平均值, 仿真結(jié)果如圖7所示.

圖7 不同網(wǎng)絡(luò)中關(guān)鍵邊、間歇邊和冗余邊占網(wǎng)絡(luò)總邊數(shù)的比例隨網(wǎng)絡(luò)度的變化曲線 (a) ER隨機網(wǎng)絡(luò); (b) BA無標(biāo)度網(wǎng)絡(luò);(c) 隨機三角形網(wǎng)絡(luò); (d) 隨機矩形網(wǎng)絡(luò)Fig. 7. Curve of the ratio of critical edge, intermittent edge and redundant edge to the total number of network edges with network degree in different networks: (a) ER random network; (b) BA scale-free network; (c) random triangle network; (d) random rectangle network.

通過仿真發(fā)現(xiàn)以下結(jié)果. i)隨著網(wǎng)絡(luò)平均度的增加, 網(wǎng)絡(luò)中的關(guān)鍵邊占整個網(wǎng)絡(luò)總邊數(shù)的比重逐漸降低, 間歇邊占整個網(wǎng)絡(luò)總邊數(shù)的比重升高. 當(dāng)網(wǎng)絡(luò)中關(guān)鍵邊的數(shù)量幾乎為0, 間歇邊占整個網(wǎng)絡(luò)邊數(shù)的比重達到1時, 對應(yīng)ER隨機網(wǎng)絡(luò)的平均度〈k〉＞6; BA無標(biāo)度網(wǎng)絡(luò)新節(jié)點作為弧頭和弧尾連接的節(jié)點數(shù)min=mout＞4 ; 隨機三角形網(wǎng)絡(luò)的平均度 〈 k〉＞7 ; 隨機矩形網(wǎng)絡(luò)的 平均度 〈 k〉＞6.ii)隨著網(wǎng)絡(luò)平均度的增加, ER隨機網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)中的冗余邊占整個網(wǎng)絡(luò)邊數(shù)的比重先增加后降低, 對于ER隨機網(wǎng)絡(luò), 其峰值對應(yīng)平均度〈k〉=2; 對于BA無標(biāo)度網(wǎng)絡(luò), 其峰值對應(yīng)新節(jié)點作為弧頭和弧尾連接的節(jié)點數(shù)min=mout=2.iii)對于隨機三角形網(wǎng)絡(luò)和隨機矩形網(wǎng)絡(luò), 由于其初始度從3和4開始, 其冗余邊占整個網(wǎng)絡(luò)總邊數(shù)的比重隨著網(wǎng)絡(luò)平均度的增加一直減小.

根據(jù)定理1, 網(wǎng)絡(luò)中關(guān)鍵邊的失效會導(dǎo)致ND增加1, 但是在致密網(wǎng)絡(luò)中, 關(guān)鍵邊的數(shù)量幾乎為0, 只存在間歇邊, 然而單個間歇邊的失效不會對網(wǎng)絡(luò)能控性(ND)造成影響, 因此, 對于致密網(wǎng)絡(luò)來說, 不容易找到影響網(wǎng)絡(luò)能控性的邊. 而本文研究的類關(guān)鍵邊集對能控性的影響結(jié)果適合所有類型的網(wǎng)絡(luò). 具體來說, 對于稀疏網(wǎng)絡(luò), 影響網(wǎng)絡(luò)能控性的邊集中既存在1-元類關(guān)鍵邊集(關(guān)鍵邊),又存在x-元類關(guān)鍵邊集(多條間歇邊組成的集合,x≥2); 對于致密網(wǎng)絡(luò), 在影響網(wǎng)絡(luò)能控性的邊集中只存在x-元類關(guān)鍵邊集(多條間歇邊組成的集合,x≥2 ).

4.2 邊失效對網(wǎng)絡(luò)能控性影響的對比

本節(jié)在4種模型網(wǎng)絡(luò)(ER隨機網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)、隨機三角形網(wǎng)絡(luò)和隨機矩形網(wǎng)絡(luò))和26種實際網(wǎng)絡(luò)中, 將類關(guān)鍵邊集失效(failure of quasi-critical edge set, FQ)和常見的3種邊失效方式進行對比, 觀察不同失效方式下的網(wǎng)絡(luò)能控性nD, 分析類關(guān)鍵邊集失效后對網(wǎng)絡(luò)能控性的影響.常見的邊失效方式有以下幾種.

1)邊隨機失效: 隨機刪除網(wǎng)絡(luò)中的一條邊.

2)基于度的邊失效: 刪除網(wǎng)絡(luò)中度最大的一條邊. 邊度的定義為邊兩端節(jié)點度的幾何均數(shù)[37].對于邊aij, 其邊度可以表示為其中ki為節(jié)點i的入度,kj為節(jié)點j的出度.

3)基于介數(shù)的邊失效: 刪除網(wǎng)絡(luò)中介數(shù)最大的一條邊. 邊的介數(shù)定義為網(wǎng)絡(luò)中所有的最短路徑中經(jīng)過邊的數(shù)量比例. 對于邊aij, 其介數(shù)可以表示為其 中Nlm表 示 節(jié) 點l和節(jié)點m之間的最短路徑的條數(shù),Nlm(aij) 表示節(jié)點l和節(jié)點m之間的最短路徑經(jīng)過邊aij的條數(shù).

根據(jù)Lu和Li[22]的結(jié)論, 基于重新計算的失效方式通常比基于初始計算的失效方式更能損害網(wǎng)絡(luò)的能控性. 因此, 對于以上3種失效方式, 和本文提出的類關(guān)鍵邊集失效模型一樣, 在每次邊失效后都需要對網(wǎng)絡(luò)中的度或介數(shù)重新計算. 需要注意的是, 基于隨機、度、介數(shù)的失效方式每次只攻擊一條邊, 而我們提出的類關(guān)鍵邊集失效模型雖然每次移除的邊數(shù)不同, 但由于最終分析的是網(wǎng)絡(luò)邊移除比例p對網(wǎng)絡(luò)能控性nD的影響, 因此每次移除邊數(shù)的多少對最終的結(jié)論無影響.

4.2.1 ER 隨機網(wǎng)絡(luò)

本節(jié)將生成節(jié)點數(shù)分別為300, 500, 700,〈kin〉=〈kout〉=2的ER隨機網(wǎng)絡(luò). 考慮到網(wǎng)絡(luò)的能控性與網(wǎng)絡(luò)平均度(邊的密度)具有相關(guān)性[38], 又生成節(jié)點總數(shù)分別為300, 500, 700,〈kin〉=〈kout〉=6的ER隨機網(wǎng)絡(luò), 按照以上4種邊失效方式(類關(guān)鍵邊集失效、隨機失效、按度失效和按介數(shù)失效)將網(wǎng)絡(luò)中邊移除, 記錄邊失效比例p與網(wǎng)絡(luò)能控性nD的曲線, 如圖8(a)—圖8(f)所示.

圖8 不同節(jié)點總數(shù)和平均度的隨機網(wǎng)絡(luò)在4種邊失效方式下網(wǎng)絡(luò)能控性 n D 的變化 (a)節(jié)點總數(shù) N =300 , 平均度〈kin〉=〈kout〉=2 的隨機網(wǎng)絡(luò); (b)節(jié)點總數(shù) N =500 , 平均度 〈 kin〉=〈kout〉=2 的隨機網(wǎng)絡(luò); (c)節(jié)點總數(shù) N =700 , 平均度〈kin〉=〈kout〉=2 的隨機網(wǎng)絡(luò); (d)節(jié)點總數(shù) N =300 , 平均度 〈 kin〉=〈kout〉=6 的隨機網(wǎng)絡(luò); (e)節(jié)點總數(shù) N =500 , 平均度〈kin〉=〈kout〉=6 的隨機網(wǎng)絡(luò); (f)節(jié)點總數(shù) N =700 , 平均度 〈 kin〉=〈kout〉=6 的隨機網(wǎng)絡(luò)Fig. 8. The change of controllability n D of random networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=2 ; (b) a random network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ; (c) a random network with number of nodes N=700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random network with number of nodes N =300 and average degree〈kin〉=〈kout〉=6 ; (e) a random network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通過仿真發(fā)現(xiàn): i)在不同的4種失效方式下,隨著網(wǎng)絡(luò)邊移除比例p的增加, 網(wǎng)絡(luò)能控性nD也在一直增加, 說明網(wǎng)絡(luò)的能控性在不斷降低. ii)不管網(wǎng)絡(luò)節(jié)點總數(shù)N和平均度 〈k〉 如何變化, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響最大. 在網(wǎng)絡(luò)邊移除前期, 當(dāng)移除比例為0.1時, 網(wǎng)絡(luò)能控性nD上升大約20%. 另外, 按介數(shù)失效和隨機失效、按度失效相比, 對網(wǎng)絡(luò)能控性的影響最大, 并且隨著網(wǎng)絡(luò)平均度的增加, 介數(shù)失效和隨機失效、按度失效之間的差距越來越明顯. iii)隨著網(wǎng)絡(luò)平均度的增加, 失效曲線的一次性和分段性變得不明顯, 曲線變得更加平滑, 說明此時網(wǎng)絡(luò)中存在單個類關(guān)鍵邊集的元素個數(shù)非常大.

4.2.2 BA 無標(biāo)度網(wǎng)絡(luò)

本節(jié)將生成節(jié)點數(shù)分別為300, 500, 700 的BA無標(biāo)度網(wǎng)絡(luò). 設(shè)置初始網(wǎng)絡(luò)為 4 個節(jié)點和 4 條邊, 且首尾連接. 為了研究度的影響, 分別使新節(jié)點作為弧頭連接的節(jié)點數(shù)min等于新節(jié)點作為弧尾連接的節(jié)點數(shù)mout等于1或2[39]. 按照以上4種邊失效方式(類關(guān)鍵邊集失效、隨機失效、按度失效和按介數(shù)失效)將網(wǎng)絡(luò)中邊移除, 記錄邊失效比例p與網(wǎng)絡(luò)能控性nD的曲線, 如圖9(a)—圖9(f)所示.

圖9 不同節(jié)點總數(shù)和平均度的無標(biāo)度網(wǎng)絡(luò)在4種邊失效方式下網(wǎng)絡(luò)能控性 n D 的變化 (a) 節(jié)點總數(shù) N =300 ,min=mout=1 的無標(biāo)度網(wǎng)絡(luò); (b) 節(jié)點總數(shù) N =500 , m in=mout=1 的無標(biāo)度網(wǎng)絡(luò); (c) 節(jié)點總數(shù) N =700 ,min=mout=1的無標(biāo)度網(wǎng)絡(luò); (d) 節(jié)點總數(shù) N =300 , m in=mout=3 的無標(biāo)度網(wǎng)絡(luò); (e) 節(jié)點總數(shù) N =500 , m in=mout=3 的無標(biāo)度網(wǎng)絡(luò);(f) 節(jié)點總數(shù) N =700 , m in=mout=3 的無標(biāo)度網(wǎng)絡(luò)Fig. 9. The change of controllability n D of scale-free networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A scale-free network with number of nodes N =300 and m in=mout=1 ; (b) a scale-free network with number of nodes N =500 and m in=mout=1 ; (c) a scale-free network with number of nodes N =700 and m in=mout=1 ; (d)a scale-free network with number of nodes N =300 and m in=mout=3 ; (e) a scale-free network with number of nodesN=500 and m in=mout=3 ; (f) a scale-free network with number of nodes N =700 and m in=mout=3.

通過仿真發(fā)現(xiàn): i)在不同的4種失效方式下,隨著網(wǎng)絡(luò)邊移除比例p的增加, 網(wǎng)絡(luò)能控性nD也在一直增加, 說明網(wǎng)絡(luò)的能控性在不斷降低; ii)不管網(wǎng)絡(luò)節(jié)點總數(shù)N和平均度 〈k〉 如何變化, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響最大. 在網(wǎng)絡(luò)邊移除前期, 當(dāng)min=mout=1 時, 邊移除比例為0.1,nD大約上升20%. 當(dāng)min=mout=3 時, 邊移除比例為0.1,nD大約上升30%. 另外, 按介數(shù)失效和隨機失效、按度失效相比, 對網(wǎng)絡(luò)能控性的影響最大, 隨著網(wǎng)絡(luò)平均度的增加, 介數(shù)失效和隨機失效、按度失效之間的差距越來越明顯.

4.2.3 隨機三角形網(wǎng)絡(luò)

本節(jié)生成節(jié)點總數(shù)分別為300, 500, 700, 平均度為2的隨機三角形網(wǎng)絡(luò), 又生成節(jié)點總數(shù)分別為300, 500, 700, 平均度為6的隨機三角形網(wǎng)絡(luò), 選取4種失效方式分別對網(wǎng)絡(luò)中的邊進行移除, 記錄能控性變化nD與邊失效比例p的曲線, 如圖10(a)—圖10(f)所示.

圖10 不同節(jié)點總數(shù)和平均度的隨機三角形網(wǎng)絡(luò)在4種邊失效方式下網(wǎng)絡(luò)能控性 n D 的變化 (a) 節(jié)點總數(shù) N =300 , 平均度〈kin〉=〈kout〉=2 的隨機三角形網(wǎng)絡(luò); (b) 節(jié)點總數(shù) N =500 , 平均度 〈 kin〉=〈kout〉=2 的隨機三角形網(wǎng)絡(luò); (c) 節(jié)點總數(shù)N=700 , 平均度 〈 kin〉=〈kout〉=2 的隨機三角形網(wǎng)絡(luò); (d) 節(jié)點總數(shù) N =300 , 平均度 〈 kin〉=〈kout〉=6 的 隨 機 三 角形網(wǎng)絡(luò);(e) 節(jié)點總數(shù) N =500 , 平均度 〈 kin〉=〈kout〉=6 的隨機三角形網(wǎng)絡(luò); (f) 節(jié)點總數(shù) N =700 , 平均度 〈 kin〉=〈kout〉=6 的隨機三角形網(wǎng)絡(luò)Fig. 10. The change of controllability n D of random triangle networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random triangle network with number of nodes N =300 and average degree〈kin〉=〈kout〉=2 ; (b) a random triangle network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ;(c) a random triangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random triangle network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=6 ; (e) a random triangle network with number of nodes N=500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random triangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通過仿真發(fā)現(xiàn): i)在不同的4種失效方式下,隨著網(wǎng)絡(luò)邊移除比例p的增加, 網(wǎng)絡(luò)能控性nD也在一直增加, 說明網(wǎng)絡(luò)的能控性在不斷降低; ii)不管網(wǎng)絡(luò)節(jié)點總數(shù)N和平均度 〈k〉 如何變化, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響最大, 在網(wǎng)絡(luò)邊移除前期, 當(dāng)平均度 〈kin〉=〈kout〉=3 時, 邊移除比例為0.1, 網(wǎng)絡(luò)能控性nD上升大約25%. 當(dāng)〈kin〉=〈kout〉=6 時, 邊移除比例為0.1, 網(wǎng)絡(luò)能控性nD上升大約20%; iii) 按介數(shù)失效和隨機失效、按度失效相比, 當(dāng)網(wǎng)絡(luò)平均度 〈k〉 較小時, 三者差別不大,隨著網(wǎng)絡(luò)平均度 〈k〉 的增大, 按介數(shù)失效相較于隨機失效、按度失效, 對網(wǎng)絡(luò)能控性的影響逐漸明顯.

4.2.4 隨機矩形網(wǎng)絡(luò)

本節(jié)生成節(jié)點總數(shù)分別為300, 500, 700, 平均度為2的隨機矩形網(wǎng)絡(luò), 又生成節(jié)點總數(shù)分別為300, 500, 700, 平均度為6的隨機矩形網(wǎng)絡(luò), 選取4種失效方式分別對網(wǎng)絡(luò)中的邊進行移除記錄能控性變化nD與邊失效比例p的曲線, 如圖11(a)—圖11(f)所示.

圖11 不同節(jié)點總數(shù)和平均度的隨機矩形網(wǎng)絡(luò)在四4邊失效方式下網(wǎng)絡(luò)能控性 n D 的變化 (a) 節(jié)點總數(shù) N =300 , 平均度〈kin〉=〈kout〉=2 的隨機矩形網(wǎng)絡(luò); (b) 節(jié)點總數(shù) N =500 , 平均度 〈 kin〉=〈kout〉=2 的隨機矩形網(wǎng)絡(luò); (c) 節(jié)點總數(shù) N =700 , 平均度 〈 kin〉=〈kout〉=2 的隨機矩形形網(wǎng)絡(luò); (d) 節(jié)點總數(shù) N =300 , 平均度 〈 kin〉=〈kout〉=6 的隨機矩形網(wǎng)絡(luò); (e) 節(jié)點總數(shù)N=500 , 平均度 〈 kin〉=〈kout〉=6 的隨機矩形網(wǎng)絡(luò); (f) 節(jié)點總數(shù) N =700 , 平均度 〈 kin〉=〈kout〉=6 的隨機矩形網(wǎng)絡(luò)Fig. 11. The change of controllability n D of random rectangle networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random rectangle network with number of nodes N =300 and average degree〈kin〉=〈kout〉=2 ; (b) a random rectangle network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ; (c) a random rectangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random rectangle network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=6 ; (e) a random rectangle network with number of nodes N=500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random rectangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通過仿真發(fā)現(xiàn): i)在不同的4種失效方式下,隨著網(wǎng)絡(luò)邊移除比例p的增加, 網(wǎng)絡(luò)能控性nD也在一直增加, 說明網(wǎng)絡(luò)的能控性在不斷降低; ii)不管網(wǎng)絡(luò)節(jié)點總數(shù)N和平均度 〈k〉 如何變化, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性的影響最大. 在網(wǎng)絡(luò)邊移除前期, 當(dāng) 〈kin〉=〈kout〉=3 時, 邊移除比例為0.1, 網(wǎng)絡(luò)能控性nD上升大約25%, 當(dāng) 〈kin〉=〈kout〉=6 時,邊移除比例為0.1, 網(wǎng)絡(luò)能控性nD上升大約20%;iii) 按介數(shù)失效和隨機失效、按度失效相比, 當(dāng)網(wǎng)絡(luò)平均度 〈k〉 較小時, 三者差別不大, 隨著網(wǎng)絡(luò)平均度 〈k〉 的增大, 按介數(shù)失效相較于隨機失效、按度失效, 對網(wǎng)絡(luò)能控性的影響逐漸明顯; iv)隨機失效和按度失效相比, 當(dāng)網(wǎng)絡(luò)平均度 〈k〉 較小時, 隨機失效對網(wǎng)絡(luò)影響較大, 隨著網(wǎng)絡(luò)平均度 〈k〉 的增大, 按度失效對網(wǎng)絡(luò)能控性影響大.

4.2.5 實際網(wǎng)絡(luò)

下面將4種邊失效方式應(yīng)用到實際網(wǎng)絡(luò)中, 進一步比較4種失效方式(關(guān)鍵邊集失效、隨機失效、按度失效和按介數(shù)失效)對網(wǎng)絡(luò)能控性nD的影響. 選取電力網(wǎng)絡(luò)、動物網(wǎng)絡(luò)、人際關(guān)系網(wǎng)絡(luò)和商品貿(mào)易網(wǎng)絡(luò)等不同領(lǐng)域的26種網(wǎng)絡(luò)[40]. 這些網(wǎng)絡(luò)的規(guī)模從幾十個到幾百個節(jié)點不等, 既有稀疏網(wǎng)絡(luò)又有致密網(wǎng)絡(luò). 針對4種失效方式, 分別計算當(dāng)邊移除比例p=0.2 ,p=0.5 和p=0.8 時網(wǎng)絡(luò)能控性nD的數(shù)值, 結(jié)果見表1.

對比表1中同一移除比例下4種失效方式的能控性nD的大小, 可以發(fā)現(xiàn): i)不管是哪種失效方式, 網(wǎng)絡(luò)能控性nD都在不斷增加, 且類關(guān)鍵邊集失效方式對應(yīng)的nD比其余3種邊失效方式都要大;ii)對于類關(guān)鍵邊集失效, 當(dāng)邊移除比例p=0.8 時,以上不同類型的所有網(wǎng)絡(luò)的能控性nD都可以達到80%以上, 且與初始nD和網(wǎng)絡(luò)平均度的大小無關(guān);iii)對于節(jié)點總數(shù)少、邊總數(shù)多(平均度大)的網(wǎng)絡(luò),例如Animal Hens, Collaboration in jazz, Joint senate press releases, Children’s network of friendship, Trade goods in different countries和Questionnaire for grade seven students等, 網(wǎng)絡(luò)能控性的初始值nD比較小, 在邊失效初期, 隨機失效、按介數(shù)失效和按度失效在移除邊數(shù)比較少時對網(wǎng)絡(luò)能控性影響較小, 但是, 類關(guān)鍵邊集失效對網(wǎng)絡(luò)能控性nD造成的破壞性較大; iv) 對于平均度比較大的網(wǎng)絡(luò), 隨機攻擊對網(wǎng)絡(luò)能控性的影響最小,當(dāng)網(wǎng)絡(luò)中邊失效比例達80%時, 能控性nD還未達到50%, 例如Animal Hens, Collaboration in jazz,Joint senate press releases, corporate law partnership_law firm, Trade goods in different countries_Foods, Trade goods in different countries_Crude materials和 Trade goods in different countries_Diplomacy等, 這與模型網(wǎng)絡(luò)中的結(jié)論一致.

表1 實際網(wǎng)絡(luò)中4 種邊失效對能控性的影響Table 1. Influence of four edge failures on controllability in real networks.

5 結(jié) 論

本文通過對節(jié)點和邊分類, 提出了類關(guān)鍵邊集的概念, 得到了類關(guān)鍵邊集的判定定理, 并提出了基于類關(guān)鍵邊集的邊失效模型. 對類關(guān)鍵邊集失效曲線進行理論分析, 發(fā)現(xiàn)失效曲線為一次分段函數(shù), 其最大(初始)斜率與網(wǎng)絡(luò)度有關(guān), 并且類關(guān)鍵邊集是對網(wǎng)絡(luò)能控性影響最大的一類邊, 和常見的邊失效方式相比, 該失效模型對網(wǎng)絡(luò)能控性破壞最大. 通過在4種模型網(wǎng)絡(luò)和26種實際網(wǎng)絡(luò)中對比常用的3種邊失效方式(隨機失效、按度失效和按介數(shù)失效)進行仿真, 結(jié)果驗證了類關(guān)鍵邊集是對網(wǎng)絡(luò)能控性影響最大的一類邊, 以及基于類關(guān)鍵邊集的失效模型也是對網(wǎng)絡(luò)能控性破壞力最大的邊失效方式. 在實際生活中, 對于癌細(xì)胞網(wǎng)絡(luò)、恐怖主義通信網(wǎng)絡(luò)等對人類存在危害的網(wǎng)絡(luò), 該失效模型可提供一種可行的攻擊方案.

本文只考慮到有向網(wǎng)絡(luò)一類邊在能控性方面的屬性, 有沒有一類節(jié)點也影響網(wǎng)絡(luò)能控性, 或者是否存在一類影響網(wǎng)絡(luò)多種性質(zhì)(能控性、連通性等)的節(jié)點或者邊, 需要進行深入研究. 另外, 類關(guān)鍵邊集的概念只適合有向網(wǎng)絡(luò), 是否可以推廣至無向網(wǎng)絡(luò)同樣值得去探索. 與此同時, 和攻擊策略對應(yīng)的就是防御策略, 如何去增強網(wǎng)絡(luò)魯棒性又是另一個有意義的研究方向.