復雜網絡能控性魯棒性研究進展

樓洋 李均利 李升 鄧浩

復雜網絡作為現今科學研究中的一個熱點學科,在過去20 年里得到了巨大的發展[1?4].復雜網絡普遍存在,如互聯網、神經網絡、交通運輸網[5]等.同時許多系統,如人際社會關系[6]、學術合作[7]、人類遷徙[8]等都可以抽象為復雜網絡,以進行系統地分析和研究.除了廣泛應用于數學、工程、經濟等學科之外,復雜網絡更與我們的日常生活息息相關,如在信息的傳播[9]、語言的演變[6,10?12]、流行病的傳播和阻斷[13?15]、網絡群體智能[16?17]等方面,復雜網絡都提供了極有價值的參考模型和分析工具.

復雜網絡能控性(Controllability)是復雜網絡研究的一個核心問題[18?33],其概念是指在有限時間內,通過適當的控制輸入,控制網絡從任意初始狀態到達一個目標狀態的能力.人類對自然系統和技術系統的理解,最終體現在如何有效地控制它們,使之為人類的生存和發展服務.作為一個跨學科的研究領域,網絡科學與控制系統理論之間的跨學科研究在過去20 年里得到迅速的發展.

由于復雜網絡通常具有大量的節點和連邊,其中高維動態節點系統相互連接,這給經典控制理論和技術帶來了新的機遇,但同時也帶來了巨大的挑戰.對于復雜的動態網絡,要達到最佳控制目標,往往只需要通過外部輸入控制小部分節點或連邊.作為實現網絡優化控制的實用方法之一,牽引控制(Pinning control)策略[34]旨在通過高效的算法來回答 “牽引控制多少節點和哪些節點” 的問題,以最少的能量消耗和代價,達到牽一發而動全身的最優效果.

復雜網絡在攻擊下維持能控性的能力稱為能控性魯棒性(Controllability robustness).本文中 “攻擊” 的表現形式為刪除節點或連邊.近年來,對復雜網絡的攻擊成為主要關注的問題之一[35?45].這些隨機或惡意的攻擊可能導致系統癱瘓等嚴重后果.復雜網絡的能控性理論為研究神經網絡結構和功能之間的聯系提供了分析工具,如分析秀麗線蟲(Caenorhabditis elegans) 的各神經元功能及其與肌肉運動的聯系[46].而能控性魯棒性則為進一步研究提供分析基礎,如秀麗線蟲部分神經元損壞可導致生物功能障礙和疾病[46],這里神經元損傷可看作網絡拓撲結構受到攻擊,即網絡中的節點和連邊受到破壞和攻擊.此外,能控性魯棒性的研究對交通運輸、電力、社交網絡的魯棒控制具有重要的指導意義.

在不同背景下,復雜網絡抵御攻擊的能力 (或稱 “抗毀性”) 具有不同的定義和度量[47].在維持連通性能力(Connectedness)[37, 45,47?48]的研究中,抗毀性是指復雜網絡在攻擊情況下保持連通性的能力.在能控性研究中,抗毀性是指網絡維持能控性的能力.為避免混淆,本文將保持連通的抗毀性稱為 “連通魯棒性”;將保持能控性的抗毀性稱為 “能控性魯棒性”,也是本文的主要討論對象.良好的能控性以較強的連通性為基礎,但是,強的連通性卻不能保證良好的能控性.同樣地,良好的能控性魯棒性以良好的連通魯棒性為基礎,而良好的連通魯棒性并不能保證良好的能控性魯棒性.能控性魯棒性較好的網絡系統具有好的抵御攻擊的能力,同時能延遲系統的整體癱瘓,為攻擊后的補救爭取時間.相反地,能控性魯棒性差的系統則容易在受到攻擊以后,迅速導致網絡系統的整體失效.因此,實用的控制網絡模型應同時兼備良好的能控性和能控性魯棒性.基于當前理論研究的局限和日益發展的超級計算能力,復雜網絡的能控性魯棒性研究以仿真實驗研究為主[49?50].同時,深度學習的發展也為這一領域提供新的研究技術[51?53].不同類型網絡系統具有不同的能控性計算方式,如有向和無向網絡,無權和有權網絡,以及單輸入單輸出和多輸入多輸出系統等,因而其能控性魯棒性的研究與優化也有所不同.本文主要闡述針對有向網絡的能控性魯棒性研究,主要關注以下3 個關鍵問題:

1) 如何定義和度量復雜網絡的能控性魯棒性?能控性魯棒性的定義和度量為不同拓撲結構的優劣提供比較標準,為不同攻擊方式的破壞能力提供參考,也為復雜網絡的優化提供依據.不同的定義方式具有不同的理論依據及其側重點,導致不同的比較結果.在計算方式上,基于仿真的能控性魯棒性的計算得到的結果真實準確,但需要較大的計算量,而基于深度神經網絡的能控性魯棒性預測則可以較小的計算代價取得相對準確的估值.

2) 常見的攻擊方式有哪些? 哪些攻擊對能控性的危害最大? 針對不同的攻擊方式,復雜網絡可能表現出不同的能控性魯棒性,所以研究攻擊方式對于復雜網絡的能控性魯棒性有重要意義.通過分析常見的攻擊方式及其危害程度,可以理解網絡中節點、連邊和其他特征對能控性魯棒性的重要程度;找到危害最大的攻擊對于評價網絡的性能也有著重要的意義,啟發式攻擊由計算智能算法自主選擇攻擊對象,可以達到相較于傳統方法更大的破壞效果.同時,對網絡攻擊的研究也有助于對網絡優化的研究,對網絡的攻擊的理解和將其應用于優化猶如理解 “矛與盾” 的關系,既相互抑制,又相互促進.

3) 怎樣提高能控性魯棒性? 如何達到最優的能控性魯棒性? 對復雜網絡的能控性魯棒性優化問題屬于NP (Nondeterministic polynomial time)難問題.但是由于能控性魯棒性度量方式,攻擊方式,以及限制條件等的不同,使其成為一個多目標優化問題.同時,由于基于仿真的能控性魯棒性度量普遍耗時較多,以及節點和連邊特征與能控性魯棒性之間相關性不夠明確等問題,給該優化問題帶來了挑戰.

圍繞以上3 個問題,本文就能控性魯棒性研究現狀與進展進行歸納總結,指出當前研究中存在的問題與技術挑戰,并探討了未來發展趨勢.

1 復雜網絡的能控性魯棒性

1.1 預備知識

1.1.1 無權有向網絡

對于一個無權有向網絡G=(V,E),其中,V={1,2,···,N}和E={Aij|i,j∈V}分別為節點和連邊集合.鄰接矩陣A中元素Aij定義為

其各節點的出度和入度可由鄰接矩陣計算,即

各節點的介數可由式(3)計算,即

其中,σst是從節點s到節點t的所有最短路徑總數,σst(i) 表示這些路徑經過節點i的次數.對于有向網絡,如果從節點s到t存在最短路徑,則稱節點s到t可達,否則稱為不可達.

1.1.2 復雜網絡能控性

復雜網絡能控性的概念由卡爾曼[54]在1960 年首先提出.對于一個復雜網絡系統或線性時不變(Linear time invariant,LTI)系統

其中,A和B分別為N ×N和N ×ND常系數矩陣,分別代表網絡的鄰接矩陣和LTI 系統外部控制器所控制的節點,x是狀態向量,u是控制輸入,卡爾曼準則 (Kalman criterion)[54]提出該系統能控的充分必要條件是系統的能控性矩陣

滿足行滿秩,該能控性稱為復雜網絡的狀態能控性(State controllable).結構能控性的概念是狀態能控性的泛化.對于常參數系數矩陣A和B,如果存在一組非零參數值可以確保系統是狀態能控的,那么則稱該系統是結構能控的(Structural controllable).對于一個能控系統,其狀態向量x可以通過適當的控制輸入u(ND×1 向量),從任意初始狀態驅動至任意目標狀態.

1.1.3 匹配

匹配(Matching)是指由連邊所組成的集合,該集合中的任意兩條連邊不共享起始節點和終止節點.連邊集合E中除了匹配連邊,其余均為非匹配.最大匹配(Maximum matching)包含了最大可能的匹配數目.最大匹配并不唯一.如果一個節點是一條匹配連邊的終止節點,則該節點是匹配節點(Matched node),否則是非匹配節點.在完全匹配(Perfect matching)中,所有的網絡節點均為匹配節點.圖1(a)鏈式網絡的最大匹配包含3 條連邊,除了起始節點1之外都是匹配節點;圖1(b)所示4 節點星型網絡的最大匹配包含1 條連邊,且不唯一(3種情況);圖1(c)網絡的最大匹配包含5 條連邊,且不唯一(最大匹配可包含連邊(5,6)或(5,7)).其類仙人掌型結構具有較好的能控性[55].

圖1 匹配和節點控制中心性的例子Fig.1 Examples of matching and node control centrality

1.1.4 節點控制中心性

節點控制中心性(Control centrality)[38]度量單個節點做為控制節點的控制范圍,其定義為

其中,Cc(G,i) 表示復雜網絡G中節點i的節點控制中心性,C表示網絡能控性矩陣(Controllability matrix),可由式(5)計算; r ankg(C(i)) 表示能控子空間的一般維度,可根據Hosoe 理論[56]計算.控制中心性大的節點能控制的范圍較大,適合作為控制節點.圖1 中陰影部分表示每個網絡中節點1 的能控子空間.圖1 給出了節點控制中心性的相關例子: 圖1(a)中節點1 的控制中心性為4;圖1(b)中節點1 在3種情況下的控制中心性都為2;圖1(c)中節點1 的控制中心性為6.

1.1.5 關鍵連邊和關鍵節點

Liu等[18]將有向網絡連邊依據其對能控性的貢獻分為3 類: 1)關鍵連邊,刪除任一關鍵連邊會導致系統能控性下降,也就是需要額外增加一個控制節點;2)冗余連邊,刪除任一冗余連邊不影響系統的能控性;3)普通連邊,刪除一條普通連邊不會導致能控性下降,但是會改變可能的最大匹配.其中冗余連邊和普通連邊可稱為非關鍵連邊.圖2(a)和圖2(c)分別舉例說明了關鍵連邊與普通連邊.

圖2 按文獻[57]連邊分類舉例Fig.2 An example of edge classification according to [57]

Lou等[57]依據其對結構能控性(見式(8))魯棒性的貢獻,將所有連邊分為3 類: 1) 關鍵連邊,定義與文獻[18]相同;2) 亞關鍵(Subcritical)連邊,遭攻擊后不會改變控制節點數,但是會增加1 個非匹配節點;3) 普通連邊,被攻擊后既不會影響控制節點數,也不會增加非匹配節點數.注意文獻[57]定義的 “普通” 連邊包含了文獻[18]定義的 “普通”和“冗余” 連邊.

圖2 分別給出了關鍵連邊(圖2(a))、亞關鍵連邊(圖2(b))和普通連邊(圖2(c))的例子.同時,文獻[57]將該分類擴展到節點,將所有節點分為4 類:1)關鍵節點,其遭攻擊后須額外增加1 個控制節點;2)亞關鍵節點,遭受攻擊后不影響控制節點數,但會使非匹配節點增加1;3)普通節點,其遭攻擊既不影響控制節點數,也不影響非匹配節點數;4)冗余節點,其遭受攻擊后使得所需控制節點數下降1,冗余節點是從能控性角度的 “孤立節點” (不一定與其他節點沒有連邊).

圖3 給出了節點分類舉例.圖3(a)中節點2 是關鍵節點,遭攻擊后節點1和3 分別須單獨的控制輸入;圖3(b)中節點6 是亞關鍵節點,遭攻擊后雖然控制節點數不變,但節點4 由匹配節點變為非匹配節點;圖3(c)中節點7 為普通節點,遭攻擊后控制節點數不變,非匹配節點數也不變(原先非匹配節點為7和9,攻擊后非匹配節點為8和9);圖3(d)中節點8 為冗余節點,將其刪除后,系統所需控制節點減少1.

圖3 按文獻[57]節點分類舉例Fig.3 An example of node classification according to [57]

1.2 能控性度量

通常,復雜網絡能控性可由控制節點的密度(nD)來量化表示,即

其中,ND是系統所需控制節點的總和,N是系統中節點數總和.nD∈[1/N,1],當nD=1/N表示當前網絡的N節點只需一個控制節點,此時的能控性最佳;而當nD=1 則表示當前網絡的每個節點都需要一個單獨的控制器,此時網絡能控性最差.系統具有較小的nD值,表示該系統的能控性較好.

常用的控制節點數ND計算方法有兩種,分別根據結構能控性[18]和精確能控性(Exact controllability)[20].結構能控性可由匹配(Matching)計算,依據最小輸入理論(Minimum inputs theorem)[18],控制節點數可由最大匹配計算得到,即

其中,|E?|是最大匹配E?中的連邊數.式(8)說明網絡所需控制節點數等于網絡中非匹配節點的個數.當網絡非完全匹配時,需ND=N ?|E?|個控制節點,即將控制器加載于ND個非匹配節點.當網絡為完全匹配時,僅需ND=1 個控制節點,此時控制器可加載于任意節點.

為了識別任意結構以及加權網絡達到能控狀態所需的最小驅動節點數,Yuan等[20]根據卡爾曼準則的等價條件PBH (Popov-Belevitch-Hautus) 秩提出精確能控性,其所需控制節點個數可由式(9)計算獲得,即

如果矩陣A滿秩,需ND=1 個控制節點;否則,需N ?rank(A)個控制節點.

1.3 能控性魯棒性定義

復雜網絡能控性描述了當前系統的能控性狀態;而能控性魯棒性則刻畫在受到攻擊的情況下,復雜網絡能控性的變化情況.

常用的能控性魯棒性定義包括基于能控性曲線的定義,基于節點控制中心性的定義,以及基于排序的定義.其中基于能控性曲線的定義參照常用的連通魯棒性定義.常用的連通魯棒性度量基于最大連通子圖LCC (Largest connected component)[37],在節點攻擊情況下,其計算為

其中,Q(i) 表示當網絡中i個節點被攻擊之后,最大連通子圖的節點數占當前網絡節點總數的比例,其范圍是 [ 1/N,1],當Q(i)=1/N表示該網絡包含N個離散節點,而當Q(i)=1 則表示該網絡節點互相連通.類似地,RLCC在連邊攻擊時計算為

其中,Q(i) 表示當網絡中i條連邊被攻擊之后,最大聯通子圖的節點數占當前網絡節點總數的比例;M為網絡中的連邊總數.式(10)～(15)中的上標N和E分別表示節點攻擊和連邊攻擊.

1.3.1 基于能控性曲線的定義

能控性魯棒性即系統在遭受節點或連邊攻擊之后,余下網絡的能控性.它是一組能控性值的序列,其中節點攻擊下能控性魯棒性定義為

其中,ND(i) 是當i個節點遭受攻擊后,所需的控制節點數;N ?i為i個節點遭攻擊后的網絡剩余節點數,隨著每次攻擊逐一減少.同樣地,連邊攻擊下能控性魯棒性定義為

其中,ND(i) 是當i條連邊遭受攻擊后,所需的控制節點數;N和M分別表示網絡節點和連邊數.注意在連邊攻擊下節點數不變,而連邊數逐一減少.當表示遭受攻擊前的初始網絡能控性.

式(12)和式(13)定義了攻擊情況下能控性變化的動態過程.而整體的能控性魯棒性可由平均得到,如式(14)和式(15)所示.

其中,較小的或值分別表示在節點或連邊攻擊的情況下,具備較好的整體能控性魯棒性.該度量方式與常用的連通性魯棒性的度量LCC[37]類似.式(14)與式(10) 區別在于: 1) 函數(·)和Q(·)的物理意義和計算方式不同;2)考慮到各網絡的初始能控性(0) 不同,因而須從i=0 開始累加,而一般情況下,網絡的初始狀態均連通,即Q(0)=1,因而可忽略.

1.3.2 基于節點控制中心性的定義

Usman等[58]將能控性魯棒性定義為節點和連邊受攻擊以后能控子空間(Controllable subspace)的剩余維度,提出了預期魯棒控制中心性ERCC(Expected robust control centrality).假設對復雜網絡G中任意n個節點進行攻擊,則節點i做為控制節點的預期魯棒控制中心性可由如下計算得到,即

其中,G′(n)是由G刪除n節點后得到的網絡;Cc(G,i)表示網絡G中節點i的節點控制中心性; E [·] 表示數學期望.作為預期魯棒控制中心性的擴展,即

其中,e是節點i可達的任意一條邊.相較于ERCC而言,GRCC (Generic robust control centrality)不限定在當前網絡中攻擊n個節點這一條件.ERCC和GRCC 適用于度量隨機攻擊情況下,某節點i的控制范圍的魯棒程度,因而可根據ERCC 或GRCC 選擇適當的控制節點.

由于式(16)和式(17)計算量巨大,Usman等[58]提出了一種均勻采樣的估值方式,降低了部分計算量.該魯棒性度量適合于評估選擇哪些節點適于作為魯棒的控制節點.

1.3.3 基于排序的能控性魯棒性度量

Chen等[50]提出一種基于排序比較的能控性魯棒性度量.該度量計算在相同的受攻擊程度下(受攻擊的節點或連邊比例相同),不同網絡的能控性(根據式(7)計算)的排序,依照排序確定能控性魯棒性: 排序靠前的較好,排序靠后的較差.

圖4 列舉了兩個復雜網絡net1和net2 在受到同種攻擊情況下的能控性曲線,其中Rc表示基于能控性曲線的能控性魯棒性,Rk表示基于排序的能控性魯棒性.對兩個網絡在相同的受攻擊節點比例下進行比較排序,例如,當受攻擊節點比例為0.1 時,net2 排序為1,net1 排序為2.Rk為其排序的整體平均值.

圖4 能控性魯棒性度量方式比較舉例Fig.4 Comparison of two different controllability robustness measurements

從網絡攻擊的過程來看,net2 的初始能控性較好,而受到攻擊時能控性下降 (所需控制節點密度上升) 速度較快,net1 的初始能控性較差,但是在攻擊中維持較好.根據能控性曲線的平均值(Rc(net1)=0.72,Rc(net2)=0.69),net2 的能控性魯棒性更好;而根據基于排序的度量(Rk(net1)=Rk(net2)=1.5),兩者能控性魯棒性等價.兩種度量的側重點不同,相對基于能控性曲線的定義,基于排序的度量更注重魯棒性,而弱化了能控性本身和初始能控性的比重;其缺點在于該方法只能根據給定方法和結果比較,無法推廣到的一般情況.基于上述理由,本文對能控性魯棒性的討論以第1.3.1 節的基于能控性曲線的定義為基準.

1.4 能控性魯棒性的預測

對一個N節點M連邊的復雜網絡,其點攻擊和邊攻擊次數范圍分別為 [ 0,N ?1]和[ 0,M],每次攻擊以后以式(8)或式(9)計算網絡的當前能控性,可得能控性曲線.以Hopcroft-Karp算法為例,計算式(8)的復雜度為[59];以Coppersmith-Winograd 算法為例,計算式(9)的復雜度為O(N2.37)[60].通過仿真獲得的曲線精確但耗時.Sun等[61]提出了在隨機和蓄意攻擊下的能控性曲線近似預測.Lou等[52]通過訓練卷積神經網絡[62],獲得能控性魯棒性曲線的近似預測,其預測誤差小于樣本方差,同時將計算速度提升 1 02～103倍[52].進一步地,文獻[63?64]通過加入先驗知識,提高了卷積神經網絡的預測精度,同時比較得出該預測精度優于譜度量(Spectral measures)[65]和異質性(Heterogeneity)[66]等方法.值得一提的是,深度學習也應用于分析和預測其他非解析的網絡屬性[53,67].

1.5 能控性魯棒性研究框架

目前的研究成果主要集中在對復雜網絡的拓撲結構的探索和優化兩個方面.

對拓撲結構的探索體現在研究復雜網絡中節點和連邊對維持能控性魯棒性的重要性,即尋找網絡中的關鍵節點和連邊.由于目前尚沒有可以預測能控性魯棒性優劣的可靠詳實的理論依據,而且經驗指標也不充足,這一研究目標主要依靠設計高效的攻擊策略來實現.本文第2 節回溯了隨機攻擊、基于特征的蓄意攻擊和啟發式攻擊,其中基于特征的蓄意攻擊和啟發式攻擊的研究對探索預測能控性魯棒性優劣的指標 (或經驗指標) 具有重要意義.

對拓撲結構的優化主要包括模型優化設計和重新連邊.本文第3 節回顧了主要的優化策略,同時介紹了全齊性和模體 (包括環和鏈等) 結構對提高能控性魯棒性的重要意義.

2 針對能控性魯棒性的攻擊

能控性魯棒性體現了在攻擊下,系統保持能控狀態的優劣.在不同攻擊方式下,不同的復雜網絡系統呈現出不同的魯棒性.攻擊的類別基于對象可分為節點攻擊和連邊攻擊.通常,對節點攻擊后,該節點及其所有連邊從當前網絡中刪除;對連邊攻擊后,僅該連邊從當前網絡中刪除.

按攻擊目標的不同可分為隨機攻擊和蓄意攻擊.隨機攻擊指無差別地破壞、刪除復雜網絡中的節點或連邊;蓄意攻擊則優先攻擊被認為最重要的節點或連邊,例如度數最高的節點.同時,不同的攻擊方式針對不同的復雜網絡功能,如圖5 所示,一種對網絡連通性的破壞較大的攻擊,對于能控性的破壞未必較大.圖5(a) 中的星型網絡,其所需控制節點數為4,其最大連通子圖LCC[37]為6 (即 6 個節點之間均有連邊相連);當中心節點被攻擊后,其所需控制節點數為5 (增加25%),而其最大連通子圖降為1 (減少83%).

圖5 能控性魯棒性與連通性魯棒性Fig.5 Controllability robustness and connectedness robustness

由于網絡連通性和能控性既有一定的相關性又存在差別,即能控必須連通,而連通未必能控.本文討論的攻擊以破壞網絡能控性為主,文中描述的攻擊效果以破壞網絡能控性為目標.

2.1 隨機攻擊

隨機攻擊是指均勻隨機地選擇復雜網絡中的節點或連邊進行攻擊.Sun等[61]指出,在隨機攻擊下,網絡所需控制節點數的增量,可以根據網絡中關鍵連邊的數量估算得到,即

當被攻擊的連邊數小于關鍵連邊數時,關鍵連邊會以p(Mc)=Mc/M的概率被攻擊.每攻擊一條關鍵連邊,所需的控制節點數增加1;若攻擊到非關鍵連邊,所需控制節點數保持不變.如果被攻擊的連邊總數大于關鍵連邊數(即Mr >Mc),則式(18)不成立,因為此時網絡中的關鍵連邊已經發生變化.實際上,攻擊1 條連邊就可能引起關鍵連邊的變化,如圖6 舉例所示.在圖6(a)中 連邊(2,4)原本是非關鍵連邊,當連邊(2,3)和(3,4)被攻擊以后,則變成了關鍵連邊;在圖6(b)中節點2,3,4原本都是關鍵節點,但當節點1 被攻擊以后,它們都成為非關鍵節點;接著,當節點4 遭受攻擊之后,節點2 又成為關鍵節點.

圖6 關鍵連邊和關鍵節點在遭受攻擊過程中變化Fig.6 Critical edges and nodes may change during attacks

Liu等[38]利用有向網絡中的層級結構,設計了隨機上/下游攻擊,旨在攻擊隨機選取的節點的上游或者下游節點.該攻擊比普通隨機攻擊以更大的概率攻擊到樞紐(Hub)節點,因而比普通隨機攻擊更有效.以圖1(c)中節點5 為例,其上游節點為節點1,下游節點為節點6和7.

2.2 基于特征的蓄意攻擊

區別于隨機攻擊,蓄意攻擊的攻擊者選取主觀認為的最有效對象進行攻擊,因此,蓄意攻擊的效果一般比隨機攻擊更顯著.通常假設攻擊者具有對被攻擊網絡的必要知識,如最大度數節點、最大介數連邊等,并且該知識能在攻擊后得到更新.常用于破壞復雜網絡連通性的攻擊特征包括度數和介數,以及鄰里相似度(Neighborhood similarity)[68]、分支權重(Branch weighting)[69]、結構孔(Structural holes)[70]等.通常,攻擊者主觀地認為該知識(網絡特征)能帶來最優的破壞效果,然而,度量復雜網絡節點和連邊在維持能控性方面的重要性,是一個復雜而艱巨的任務,尤其是對較大規模網絡.絕大部分基于單一特征的攻擊并不能給網絡帶來持續的、最有效的破壞.

網絡拓撲結構與能控性之間關聯的研究較多[27,32,71?73],而與能控性魯棒性相關的指標或特征研究相對較少.目前尚無可以預測能控性魯棒性優劣的可靠詳實的理論依據,而且經驗指標也不充足.節點攻擊的研究較多,而連邊攻擊的研究較少[74],其原因是: 1) 節點攻擊相對有效,攻擊節點時其連邊也同時被刪除,而連邊攻擊并不影響節點;2) 節點的特征屬性相對明確,而連邊的屬性相對模糊,如有向圖的節點具有明確的出度和入度定義,而連邊的出度和入度不同定義較多[35,47,75].

2.2.1 基于度數和介數的攻擊

基于度數的攻擊旨在攻擊網絡中度數最大的節點(或連邊).Holme等[35]將基于度和介數的節點攻擊分別分為基于初始分布的攻擊和重新計算分布的攻擊.前者依據最初網絡的度數或介數分布,由大到小依次攻擊,而后者則在每次攻擊后重新計算.由于網絡的統計特征在攻擊后通常會發生較大變化,重新計算的攻擊效果要優于基于初始分布的攻擊[35,76],因而本文默認基于度數或介數的攻擊中,度數或介數最大的節點需要在每次攻擊后重新計算.

基于度數和介數的攻擊既是破壞網絡連通性的最常見攻擊方式,也是破壞能控性的常用方式.基于度數的攻擊是局部策略,其重點是盡可能快地減少總連邊;而基于介數攻擊是全局策略,專注于盡可能多地破壞全局最短路徑.基于度數和介數的節點攻擊分別定義為

Nguyen等[77]觀察發現基于介數攻擊在攻擊后期效果變弱,由此設計了一個約束條件,即如果當前(全局)介數最高節點屬于最大連通子圖,則攻擊該節點;否則攻擊最大連通子圖(局部)介數最大的節點.

作為最常用的攻擊度量,度數和介數經常一起用于攻擊.Nie等[76]通過預先給度數最大和介數最大的節點分配權值來分配兩者被攻擊的概率,即

其中,ki和bi分別為節點i的度數和介數,pi是攻擊該節點的概率,α和β為預先設定的權值.Gao等[78]將式(21)中的β替換為 1?α.進一步地,Hao等[79]設定了3 個參數α,β和γ來控制度數、介數和諧波接近度(Harmonic closeness)在攻擊中的權重.這些攻擊策略應用于互依網絡(Interdependent networks)[78?82]、網絡的網絡(Networks of networks)[83?84]以及加權網絡(Weighted networks)[85]等.

研究發現,基于度數的節點攻擊[86]比隨機節點攻擊更能有效地破壞隨機網絡和無標度網絡的能控性.Lu等[87]發現節點攻擊的破壞力大于連邊攻擊,同時,異質網絡的能控性魯棒性要劣于同質網絡.此外,對于許多實際網絡來說,基于介數攻擊對能控性破壞力最強[87].

對于本地世界網絡(Local-world network)[88?89],Sun等[90]發現基于度數的節點攻擊對本地世界規模較大的網絡更具破壞力,而對本地世界規模小的網絡破壞力較小.文獻[90]的研究包括連通魯棒性和能控性魯棒性.Lou等[57]以最大度數和最大介數為依據,每次選取破壞程度較大的對象進行攻擊.基于負載(介數)的連邊攻擊[91]能有效地破壞網絡能控性.連邊攻擊不僅能破壞連通性和能控性,也能引起無標度網絡的級聯故障.

2.2.2 其他蓄意攻擊

Wang等[92]提出的基于破壞力的攻擊(Damage-based attack)以破壞程度作為選擇攻擊的度量,即攻擊帶來破壞程度最大的節點.這里的破壞程度以攻擊前后LCC 大小的變化來度量.Lou等[57]提出在每次攻擊中找到度數和介數最大的節點,選擇帶來破壞力較大的節點作為攻擊對象,該方法對能控性的破壞力接近于基于度數攻擊和基于介數攻擊的破壞力上限.這類基于破壞程度的攻擊要求攻擊者具備比其他攻擊更多的對攻擊對象的知識.

基于模塊的攻擊(Module-based attack) 策略[93?94]旨在攻擊具有多社區(Community)結構的網絡中連接各社區的公共連邊(Inter-community edge),從而達到破壞整體性能的效果.Ma等[95]讓攻擊與防御交替進行,并以此優化網絡結構.

Sun等[61]提出了基于關鍵連邊的攻擊策略.該策略首選搜集網絡中的所有關鍵連邊,將其存儲于列表并優先攻擊,待列表中的關鍵連邊全部攻擊后,采用隨機攻擊策略.如圖6(a)所示,一條關鍵連邊在一次攻擊之后就可能轉換成非關鍵連邊.Lou等[57]在文獻[61]的基礎上,提出了層級攻擊(Hierarchical attack): 層級連邊攻擊依次刪除網絡中的關鍵連邊、亞關鍵連邊和普通連邊.類似地,層級節點攻擊依次刪除網絡中的關鍵節點、亞關鍵節點、普通節點和冗余節點.關鍵連邊和節點的定義及舉例見第1.1.5 節.同時,連邊和節點的層級劃分在每次攻擊后得到更新.該方法計算復雜度較高但獲得了有效的攻擊效果.

2.3 啟發式攻擊

啟發式算法(Heuristic algorithm)屬于計算智能,是一種用于解決NP 難問題的有效方法,常見的算法包括模擬退火算法(Simulated annealing)、遺傳算法(Genetic algorithm)、禁忌搜索(Tabu search)、粒子群算法(Particle swarm optimization)等.

前述的隨機攻擊和蓄意攻擊通過預設的策略逐個選取攻擊節點或連邊;而啟發式攻擊則將整個攻擊過程視作一個優化問題,通過啟發式算法搜索最優攻擊序列(即破壞效果最佳的攻擊序列).對于一個N節點網絡,其攻擊序列的解空間大小為N!;對于一個M節點網絡,其攻擊序列的解空間大小為M!. 常用的編碼方式為自然序號,即預先按1到N(或M)分別標記每個節點(或連邊),通過選用適當的優化目標函數以達到優化攻擊序列的效果.Zhang等[96]采用遺傳算法,以連邊的自然序號作為遺傳編碼,設計了可剔除重復基因的交叉和遺傳算子,這里 “重復基因” 表示在同一個攻擊序列中存在多個位置指向同一節點或連邊.孫昱等[97]使用禁忌搜索最優攻擊序列,通過局部交換,生成新的攻擊序列,如果該序列在禁忌列表中 (在一定時間范圍內生成且已經評價的相同攻擊序列),則放棄該序列.該算法的計算成本高,適用于較小規模網絡.Ventresca[98]利用啟發式算法搜索網絡中的關鍵節點.Deng等[99]通過禁忌搜索關鍵節點集合,提高網絡解體的攻擊效果,該方法計算成本較高.Qi等[100]以禁忌搜索提高多層網絡的分解效果.Lozano等[101]以網絡中最大介數為目標函數,通過人工蜂群算法(Artificial bee colony)來最小化這一目標函數,從而優化攻擊效果.Li等[102]以鄰域信息增強隨機算法搜索關鍵節點集合的能力,顯著提高攻擊效率.

2.4 不同攻擊下的能控性魯棒性

本小節和第3.2 節可視為同一問題的不同角度分析.對于同一種網絡在不同攻擊下,使其能控性下降最快速明顯的攻擊為最有效攻擊;將同一種攻擊方式用于不同拓撲結構,其中能控性保持最好的網絡可視為能控性魯棒性最好的拓撲結構.

圖7 給出了常見的9種網絡模型在基于介數和度數的連邊和節點攻擊下的能控性曲線變化,包括隨機圖網絡RG (Random graph)[103],小世界網絡SW (Small-world)[104?105],隨機三角形網絡RTN(Random triangle network)[50,106],隨機四邊形網絡RRN (Random rectangular network)[50],無標度網絡SF (Scale-free)[107?108],洋蔥型網絡OLN (Onionlike network)[109?112],q-回路網絡QSN (q-snapback network)[113?114],q-回路及反向連邊QSNR (QSN with re-directed edges)模型[115],以及極同質EH(Extremely homogeneous) 網絡[116].圖中pE=Mr/M和pN=Nr/N分別表示已被攻擊的連邊和節點的比例.網絡規模為節點數N=1 000,連邊數M=5 000,所有數據來自20 次攻擊的平均結果.

圖7 常見的網絡模型在攻擊下的能控性曲線變化Fig.7 The controllability curves of 9 network topologies under 4 different attack strategies

由圖可見,極同質EH 網絡在圖7(a)基于介數的連邊攻擊、圖7(c)基于度數的節點攻擊和圖7(d)基于介數的節點攻擊過程中,始終保持所需控制節點比例較低,相較于其他網絡,EH 具有最佳能控性魯棒性;而在圖7(b)基于度數的連邊攻擊中表現較差.而無標度SF 網絡和洋蔥型OLN 網絡則具有相似的能控性曲線,兩者均為能控性魯棒性最差的網絡結構.在不同攻擊下,各網絡表現出不同的能控性魯棒性,如QSN 在圖7(a)基于介數攻擊下的能控性只優于SF和OLN,而劣于其他網絡;但在基于度數的連邊攻擊下,QSN 表現出最好的能控性魯棒性,尤其在攻擊的中后期.值得一提的是,使用不同的連邊度數定義也會影響比較結果.

3 能控性魯棒性優化

能控性魯棒性優化旨在提高復雜網絡對各種攻擊的抵御能力.以第1.3.1 節的度量為例,定義如下.

定義 1.一個復雜網絡G?稱為能控性魯棒性最優網絡(簡稱最優網絡),當且僅當

成立,其中,? 為適用解空間,即所有滿足約束條件的復雜網絡G構成的解空間;Rc可由式(14)或式(15)計算得到.

由于能控性魯棒性優化屬NP 難問題,而進化算法(Evolutionary algorithm)[117?118]和群智能算法[119]等智能計算[120?121]方法本身的計算代價較小,其計算成本通常取決于待優化問題的評價.因而,智能計算方法常應用于這一優化問題.

網絡模型優化設計和對網絡進行重新連邊為常用的能控性魯棒性優化手段.全齊網絡拓撲結構在研究中認為是具有最優的能控性魯棒性.此外,復雜網絡中模體對保持網絡能控性魯棒性具有一定的促進作用.表1 列舉了常見優化策略的優點與不足.以下各小節針對這幾個方面分別進行討論.

表1 常用能控性魯棒性優化策略的優點與不足Table 1 Pros and cons of the strategies for controllability robustness optimization

3.1 網絡模型優化設計

Yan 等基于同余論(Congruence theory)構造了同余網絡MCN (Multiplex congruence network)[122],其生成方式如下: 首先對所有N節點進行1 到N編號,如果兩個節點i和j滿足:

則存在一條連邊Aij,其中r為j除以i得到的余數.相同余數的所有節點構成同于網絡的一層.同余網絡的每一層是無標度網絡,屬異質(Heterogeneous)網絡,其出度分布服從

通常認為異質網絡的能控性和能控性魯棒性都較差[18,50],而同質(Homogeneous)網絡的能控性和能控性魯棒性都較好[18,116].但是由于主鏈(r=1層)的存在,使得同余網絡具有較好的能控性和能控性魯棒性,同時揭示了度分布非影響能控性魯棒性的唯一原因.

Lou等[113?114]發現多鏈和多環結構有助于提高能控性魯棒性,提出了基于工業流水線的q-回路網絡QSN,由一條主鏈和若干回路構成,回路的數量由參數q∈[0,1] 控制.其第r(r=1,···,N ?1) 層第i(i=1,···,N) 節點的出度可由下式計算:

q-回路及反向連邊QSNR 模型[115]基于QSN模型,同時加入隨機反向連邊,并保證主鏈不受影響.QSNR 的度分布服從泊松分布.雖然在不同攻擊方式下,各網絡的能控性魯棒性稍顯不同,整體而言,QSNR和QSN 優于MCN,其中QSNR 又稍優于QSN[115].

隨機三角形網絡RTN[50,106]基于Henneberg 增長,由大量的有向三角形構成.將其擴展到四邊形,就形成了隨機四邊形網絡RRN[50].在這兩個模型中,任意一個節點都至少處于一個三角形/四邊形(有向環)當中.這些多環結構的存在,使它們的能控性魯棒性較好.

極同質EH 網絡[116]中任一節點i(i=1,2,···,N) 的出度和入度被限定在極小范圍內,也就是

3.2 不同網絡拓撲結構的能控性魯棒性比較

Chen等[50]以第1.3.3 節基于排序的度量比較了包括隨機圖網絡RG[103]、無標度網絡SF[107?108]、同余網絡MCN[122]、q-回路網絡QSN[113?114]、隨機三角形網絡RTN[50, 106]和隨機四邊形網絡RRN[50]等6種網絡在6種不同攻擊(包括隨機節點和隨機連邊攻擊,基于度數的節點和連邊攻擊,以及基于介數的節點和連邊攻擊)下的能控性魯棒性,發現ER和RRN 能較好地抵御節點攻擊,而RRN和RTN能較好地抵御各種連邊攻擊.

文獻[115]通過實驗比較得出當反向連邊概率為0.5 時,QSNR 網絡的能控性魯棒性最佳,此時QSNR 的能控性魯棒性優于QSN.

現有研究證實,極同質EH 網絡[116]是在給定網絡規模(N節點和M連邊)情況下,能控性魯棒性最優的結構(如圖7 所示).同時,Lou等[116]提出的隨機連邊矯正RER (Random edge rectification)策略,可將任何網絡結構,改變為EH 網絡,同時,與EH 網絡越近似則該網絡的能控性魯棒性越好.

表2 列舉了幾種能控性魯棒性優化的網絡結構.這些網絡都由優化設計得到,其中QSNR和EH 需要進行重新連邊優化.僅EH 結構具有全齊屬性.除了MCN 僅具有多鏈結構,其余5種網絡同時具有多鏈和多環結構.

表2 能控性魯棒性優化的網絡結構Table 2 Comparison of network topologies with optimized controllability robustness

3.3 重新連邊優化

重新連邊(Rewiring)[119]通常分為3種形式:1)基于度保持(Degree-preserving)的重新連邊: 保持各節點出度和入度不變,重新調整連邊;2)保持網絡基本骨架不變,對連邊的方向進行調整;3)保持網絡整體節點和連邊數目不變,對網絡進行任意重構.其中第1種方式為最常用的策略.本小節只討論前兩種方式,第3種將在第3.4 節討論.不同的重新連邊策略本質上是對式(22)的 ? 進行了不同約束,而優化的目標是相同的.

重新連邊常用于連通魯棒性的優化.基于度保持的重新連邊策略保持每個節點的出度和入度均不變,即將連邊Aij和Ast(is或jt) 重新連接為Ait和Asj,從而保持節點i和s的出度不變;節點j和t的入度不變.異質網絡 (例如無標度網絡等) 在應用基于度保持的重新連邊策略后,網絡趨于洋蔥型(Onion-like)結構,即度數相近的節點之間普遍連接,同時抑制度數相差較大的節點之間的連接,洋蔥型網絡具有較好的連通魯棒性[36,110?112,123],同時也能提高網絡的k-殼組成.

重新連邊可看作優化問題,基于不同的目標函數,網絡的優化趨向不同.Chan等[65]以譜度量[124?128]為目標函數,通過基于度保持的重新連邊策略來優化連通魯棒性.譜度量是常用的用于估算和預測復雜網絡連通魯棒性的工具[129].然而,目前尚未發現譜度量或其他復雜網絡特征與能控性魯棒性具有較強的相關性[49].

Xiao等[130]提出的基于度保持的重新連邊策略首先選擇特定度范圍的4 個節點,然后交換其連邊.該方法在增強網絡連通魯棒性的同時,也降低了網絡同配性系數(Assortativity coefficient)[131].

Louzada等[132]提出的智慧重新連邊(Smart rewiring)策略通過增強樞紐節點的相鄰節點之間的聯系,來增加網絡抵御基于度數攻擊的魯棒性.該方法假設樞紐節點為首要攻擊目標,很多情況下,當樞紐節點遭受攻擊后,其相鄰節點之間的聯系隨即消失.通過智慧重連策略可使樞紐節點遭受攻擊后,網絡仍保持較好的連通性.

啟發式算法不僅應用于網絡攻擊(見第2.3 節),同時也應用于優化復雜網絡魯棒性.啟發式算法包含一個種群的解,其中每個解代表一個網絡結構,通過變異和交叉,以適當地選擇算子來引導解的演化趨勢,從而產生出高質量的解,即魯棒性好的網絡結構.

Buesser等[133]用模擬退火(Simulated annealing)算法來優化網絡連通魯棒性.Zhou等[134]以式(10)作為目標函數,用文化基因算法(Memetic algorithm)來優化無標度網絡的連通魯棒性.

由于抵御連邊攻擊的連通魯棒性往往不能隨著抵御節點攻擊的魯棒性的提高而提高[135],Zeng等[135]以混合貪婪算法(Hybrid greedy algorithm)來同時提高網絡對抗節點攻擊和連邊攻擊的連通魯棒性.Liu等[136]提出了以多目標優化(Multi-objective optimization)來同時優化對抗節點攻擊和連邊攻擊的魯棒性.Wang等[137]以多目標優化,同時優化網絡的連通魯棒性和抵御級聯故障的魯棒性.多目標優化不僅可以優化網絡的不同魯棒性,同時連通魯棒性的多種度量也可以被同時優化[138].Ma等[95]通過攻擊和防守交替的策略提高網絡魯棒性,其中防守策略是指通過隨機、優先或平衡的方式來補充被攻擊的節點或連邊.對于異質網絡的連通魯棒性優化來說,一個普遍共同結果是產生洋蔥型結構網絡[37,110?112].

與攻擊方式一樣,已有研究大部分側重于提高連通魯棒性.能控性魯棒性的優化可借鑒連通魯棒性的優化方法,但是由于評價標準和優化目標的不同,能控性魯棒性的優化有其自身特點.通過刪除冗余連邊和增加關鍵或普通連邊的方式[139?140],減少網絡中非匹配節點數,可以提高復雜網絡能控性.Wang等[141]以合作者比例(維持合作能力)和式(14)所示能控性魯棒性定義作為兩個優化目標,以多目標進化算法來同時優化它們.

Hou等[142]保持了網絡的架構和規模(節點數和連邊數)不變,通過只改變連邊的方向來優化能控性.Lou等[115]通過改變非主鏈連邊的方向,不僅將原先均勻度分布改變成泊松分布,同時也增加了模體的數量和跨度,提高了QSN 的能控性魯棒性.雖然一般來講,同質網絡較異質網絡具有較好的能控性和魯棒性,但是同余網絡的存在否定了這一共識結論[122].然而,Lou等[116]提出對于給定數量的節點和連邊,能控性魯棒性最優的網絡結構(滿足式(22))應具有極同質結構,即所有節點的出度和入度均相等(或者其差值小于等于1).Shi等[143]提出的全齊性(Totally homogeneous)網絡給出了較極同質網絡更為全面的數學定義,且提出全齊性網絡具有最優同步性等多種最優指標.通常地,多鏈結構和多環結構具有較好的能控性魯棒性[50,113,115,122].

3.4 全齊網絡

基本的網絡結構,如鏈式、環式、星型等結構無法解決一些新涌現的網絡問題,如能控性網絡子結構的設計和優化網絡同步性等問題.Shi等[143]借鑒龐加萊的剖分思想,把網絡分解為全齊性子網絡.以團(Clique)為基本單位建立一系列二元域上的向量空間表述網絡結構.模型和實際網絡中都存在大量全齊性子網絡,是支持網絡功能的重要基礎結構,對網絡同步性[144]、能控性[18,33]、連通魯棒性[37]等具有重要意義.Fan等[145]研究了網絡的圈結構,提出刻畫網絡圈結構的邊界矩陣和衡量節點重要性的圈指標.

Lou等[116]基于小規模網絡的遍歷搜索,歸納了經驗必要條件ENC (Empirical necessary condition).ENC 指出滿足式(22)的最優網絡結構,應滿足式(26).Lou等[116]發現對于給定N節點和M連邊,其所有網絡結構、滿足ENC 的網絡、以及最優網絡之間的關系如圖8 所示.

圖8 所有N 節點和M 連邊網絡,滿足ENC 的網絡、全齊網絡,以及最優網絡之間的關系圖Fig.8 The relationship diagram of theN-nodeM-edge networks,ENC networks,totally homogeneous networks,and the optimal networks

同時,Lou等[116]提出了隨機連邊矯正RER(Random edge rectification)策略,該策略使復雜網絡趨于滿足式(26)的結構,此外,使用RER 策略的次數與網絡能控性魯棒性的提高成正比.RER屬于第3種重新連邊優化方式,即保持網絡整體節點數N和連邊數M不變,對網絡進行(任意)重構,以達到優化能控性魯棒性的目的.

經驗地,全齊網絡滿足ENC 條件,同時也是最優網絡;然而顯然并非所有的最優網絡都屬于全齊網絡,其關系如圖8 所示.

3.5 模體

模體(Motif)[146]是復雜網絡中高頻出現的具有統計意義的導出子圖.近年來模體的研究廣泛深入到各個領域,如電力系統網絡[147]和大腸桿菌代謝網絡[148]等.在網絡控制方面,Badhwar等[149]發現秀麗線蟲神經元網絡中,前饋模體的數量對能控性的影響較大.Dey等[150]研究了不同攻擊策略下網絡中模體的變化情況,并分析了歐洲國家的電力系統網絡的連通魯棒性差異.賈承豐等[151]提出了基于模體的攻擊策略,仿真結果表明基于模體攻擊對模體特征明顯的網絡可造成的更大損害.

同余網絡MCN[122]中存在較多鏈式模體結構.每一條鏈僅用一個控制器即可保證鏈路能控性.在受到攻擊時,針對驅動節點的攻擊不會破壞鏈路能控性;反而隨機攻擊更容易造成鏈路斷裂,從而增加額外控制器.Lou等[113]進一步將鏈式模體擴展至環式模體.環式模體的反饋連接比鏈式的前饋連接具有更好的能控性魯棒性.QSN 網絡中含有大量的鏈式和環式模體[113].多模體結構的QSN和MCN在抵御攻擊方面優于一般的無標度網絡.進一步地,對QSN 的非主鏈連邊隨機反向重連可增加3-環、4-環和4-鏈(n-環/鏈指由n個節點構成的環/鏈)結構,增強了能控性魯棒性.

Chen等[50]比較了具有鏈式模體的MCN,具有環式模體的QSN,以3-環為基礎結構RTN,以4-環為基礎結構的RRN 等在不同攻擊下的能控性魯棒性,發現3-環和4-環的RRN和RTN 結構在各種連邊攻擊下,保持較好的能控性.

4 展望與總結

本文圍繞3 個問題進行歸納與總結:

1)復雜網絡能控性魯棒性的定義和度量.不同的定義因側重點不同而稍有區別,須根據實際應用場景選取適當的定義和度量方式.

2)常見的復雜網絡攻擊方式及其對網絡連通性和能控性的危害.隨機攻擊的危害較小,對攻擊者來說需要掌握的網絡相關信息較少;基于特征的蓄意攻擊依據預先設定的特征對網絡的節點或連邊實施攻擊,取得的攻擊效果往往較好,對攻擊者來說需要掌握較多網絡相關信息;啟發式攻擊以智能計算優化攻擊,往往需要具備較全面的網絡相關信息和較多的計算資源,同時攻擊效果的提升也較為顯著.

3)能控性魯棒性的優化問題.對于尚未建立的網絡可采取優化建模,對于已有網絡可采取(全部或部分)重新連邊策略.如果能夠掌握攻擊者的信息,則可更有效地針對某一類攻擊做出防御.一般的,在各類攻擊情況下,極同質網絡具有較好的能控性魯棒性.

針對以上3 個問題,未來可研究內容包括:

1)深度學習和計算智能可更廣泛地應用于復雜網絡能控性魯棒性的預測、分析和優化.目前,利用深度學習預測復雜網絡能控性魯棒性的研究和利用計算智能來生成優化網絡拓撲結構的研究處于起步階段.深度學習和計算智能處理大規模問題能力的進一步發展,將會對包括能控性魯棒性在內的復雜網絡各項研究帶來新的機遇和挑戰.

2)相關網絡特征與能控性魯棒性的相關性值得進一步探索和研究,包括相關拓撲結構特征、關鍵節點和關鍵連邊的定義與搜索等.這一研究方向的難點在于網絡規模、拓撲結構、攻擊方式等同時具有多樣性.同時,在實際網絡中,各節點和連邊存在權值等因素,因此,相對不容易形成一般性可泛化的理論結果.

3)全齊性網絡和經驗必要條件的進一步研究和理論拓展.全齊性網絡和經驗必要條件的研究從簡單結構開始,逐步推向一般情況,簡單的網絡拓撲結構比一般實際網絡更容易研究分析,實現理論突破.對經驗必要條件的理論證明,以及對經驗和理論充分條件的探索,將從理論上實現復雜網絡能控性魯棒性的最優化.

附錄A 本文所用符號列表

A鄰接矩陣

Aij鄰接矩陣中節點i和j之間的連邊

bi節點i的介數

B輸入矩陣

C能控性矩陣

E網絡連邊集合

G復雜網絡

ki節點i的度數

節點i的出度

節點i的入度

M網絡連邊數

Mc關鍵連邊數

Mr當前已攻擊的連邊數

N網絡節點數

ND網絡所需控制節點數

?ND網絡所需控制節點數增量

Nr當前已攻擊的節點數

nD網絡所需控制節點密度

p(Mc)關鍵連邊比例

Rc平均能控性魯棒性

RLCC平均連通魯棒性

u控制向量

V網絡節點集合

x狀態向量

σij從節點i到j的最短路徑

? 適用解空間