樓洋 李均利 李升 鄧浩

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

復(fù)雜網(wǎng)絡(luò)能控性(Controllability)是復(fù)雜網(wǎng)絡(luò)研究的一個(gè)核心問題[18?33],其概念是指在有限時(shí)間內(nèi),通過適當(dāng)?shù)目刂戚斎?控制網(wǎng)絡(luò)從任意初始狀態(tài)到達(dá)一個(gè)目標(biāo)狀態(tài)的能力.人類對(duì)自然系統(tǒng)和技術(shù)系統(tǒng)的理解,最終體現(xiàn)在如何有效地控制它們,使之為人類的生存和發(fā)展服務(wù).作為一個(gè)跨學(xué)科的研究領(lǐng)域,網(wǎng)絡(luò)科學(xué)與控制系統(tǒng)理論之間的跨學(xué)科研究在過去20 年里得到迅速的發(fā)展.

由于復(fù)雜網(wǎng)絡(luò)通常具有大量的節(jié)點(diǎn)和連邊,其中高維動(dòng)態(tài)節(jié)點(diǎn)系統(tǒng)相互連接,這給經(jīng)典控制理論和技術(shù)帶來了新的機(jī)遇,但同時(shí)也帶來了巨大的挑戰(zhàn).對(duì)于復(fù)雜的動(dòng)態(tài)網(wǎng)絡(luò),要達(dá)到最佳控制目標(biāo),往往只需要通過外部輸入控制小部分節(jié)點(diǎn)或連邊.作為實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化控制的實(shí)用方法之一,牽引控制(Pinning control)策略[34]旨在通過高效的算法來回答 “牽引控制多少節(jié)點(diǎn)和哪些節(jié)點(diǎn)” 的問題,以最少的能量消耗和代價(jià),達(dá)到牽一發(fā)而動(dòng)全身的最優(yōu)效果.

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

在不同背景下,復(fù)雜網(wǎng)絡(luò)抵御攻擊的能力 (或稱 “抗毀性”) 具有不同的定義和度量[47].在維持連通性能力(Connectedness)[37, 45,47?48]的研究中,抗毀性是指復(fù)雜網(wǎng)絡(luò)在攻擊情況下保持連通性的能力.在能控性研究中,抗毀性是指網(wǎng)絡(luò)維持能控性的能力.為避免混淆,本文將保持連通的抗毀性稱為 “連通魯棒性”;將保持能控性的抗毀性稱為 “能控性魯棒性”,也是本文的主要討論對(duì)象.良好的能控性以較強(qiáng)的連通性為基礎(chǔ),但是,強(qiáng)的連通性卻不能保證良好的能控性.同樣地,良好的能控性魯棒性以良好的連通魯棒性為基礎(chǔ),而良好的連通魯棒性并不能保證良好的能控性魯棒性.能控性魯棒性較好的網(wǎng)絡(luò)系統(tǒng)具有好的抵御攻擊的能力,同時(shí)能延遲系統(tǒng)的整體癱瘓,為攻擊后的補(bǔ)救爭取時(shí)間.相反地,能控性魯棒性差的系統(tǒng)則容易在受到攻擊以后,迅速導(dǎo)致網(wǎng)絡(luò)系統(tǒng)的整體失效.因此,實(shí)用的控制網(wǎng)絡(luò)模型應(yīng)同時(shí)兼?zhèn)淞己玫哪芸匦院湍芸匦贼敯粜?基于當(dāng)前理論研究的局限和日益發(fā)展的超級(jí)計(jì)算能力,復(fù)雜網(wǎng)絡(luò)的能控性魯棒性研究以仿真實(shí)驗(yàn)研究為主[49?50].同時(shí),深度學(xué)習(xí)的發(fā)展也為這一領(lǐng)域提供新的研究技術(shù)[51?53].不同類型網(wǎng)絡(luò)系統(tǒng)具有不同的能控性計(jì)算方式,如有向和無向網(wǎng)絡(luò),無權(quán)和有權(quán)網(wǎng)絡(luò),以及單輸入單輸出和多輸入多輸出系統(tǒng)等,因而其能控性魯棒性的研究與優(yōu)化也有所不同.本文主要闡述針對(duì)有向網(wǎng)絡(luò)的能控性魯棒性研究,主要關(guān)注以下3 個(gè)關(guān)鍵問題:

1) 如何定義和度量復(fù)雜網(wǎng)絡(luò)的能控性魯棒性?能控性魯棒性的定義和度量為不同拓?fù)浣Y(jié)構(gòu)的優(yōu)劣提供比較標(biāo)準(zhǔn),為不同攻擊方式的破壞能力提供參考,也為復(fù)雜網(wǎng)絡(luò)的優(yōu)化提供依據(jù).不同的定義方式具有不同的理論依據(jù)及其側(cè)重點(diǎn),導(dǎo)致不同的比較結(jié)果.在計(jì)算方式上,基于仿真的能控性魯棒性的計(jì)算得到的結(jié)果真實(shí)準(zhǔn)確,但需要較大的計(jì)算量,而基于深度神經(jīng)網(wǎng)絡(luò)的能控性魯棒性預(yù)測則可以較小的計(jì)算代價(jià)取得相對(duì)準(zhǔn)確的估值.

2) 常見的攻擊方式有哪些? 哪些攻擊對(duì)能控性的危害最大? 針對(duì)不同的攻擊方式,復(fù)雜網(wǎng)絡(luò)可能表現(xiàn)出不同的能控性魯棒性,所以研究攻擊方式對(duì)于復(fù)雜網(wǎng)絡(luò)的能控性魯棒性有重要意義.通過分析常見的攻擊方式及其危害程度,可以理解網(wǎng)絡(luò)中節(jié)點(diǎn)、連邊和其他特征對(duì)能控性魯棒性的重要程度;找到危害最大的攻擊對(duì)于評(píng)價(jià)網(wǎng)絡(luò)的性能也有著重要的意義,啟發(fā)式攻擊由計(jì)算智能算法自主選擇攻擊對(duì)象,可以達(dá)到相較于傳統(tǒng)方法更大的破壞效果.同時(shí),對(duì)網(wǎng)絡(luò)攻擊的研究也有助于對(duì)網(wǎng)絡(luò)優(yōu)化的研究,對(duì)網(wǎng)絡(luò)的攻擊的理解和將其應(yīng)用于優(yōu)化猶如理解 “矛與盾” 的關(guān)系,既相互抑制,又相互促進(jìn).

3) 怎樣提高能控性魯棒性? 如何達(dá)到最優(yōu)的能控性魯棒性? 對(duì)復(fù)雜網(wǎng)絡(luò)的能控性魯棒性優(yōu)化問題屬于NP (Nondeterministic polynomial time)難問題.但是由于能控性魯棒性度量方式,攻擊方式,以及限制條件等的不同,使其成為一個(gè)多目標(biāo)優(yōu)化問題.同時(shí),由于基于仿真的能控性魯棒性度量普遍耗時(shí)較多,以及節(jié)點(diǎn)和連邊特征與能控性魯棒性之間相關(guān)性不夠明確等問題,給該優(yōu)化問題帶來了挑戰(zhàn).

圍繞以上3 個(gè)問題,本文就能控性魯棒性研究現(xiàn)狀與進(jìn)展進(jìn)行歸納總結(jié),指出當(dāng)前研究中存在的問題與技術(shù)挑戰(zhàn),并探討了未來發(fā)展趨勢.

1 復(fù)雜網(wǎng)絡(luò)的能控性魯棒性

1.1 預(yù)備知識(shí)

1.1.1 無權(quán)有向網(wǎng)絡(luò)

對(duì)于一個(gè)無權(quán)有向網(wǎng)絡(luò)G=(V,E),其中,V={1,2,···,N}和E={Aij|i,j∈V}分別為節(jié)點(diǎn)和連邊集合.鄰接矩陣A中元素Aij定義為

其各節(jié)點(diǎn)的出度和入度可由鄰接矩陣計(jì)算,即

各節(jié)點(diǎn)的介數(shù)可由式(3)計(jì)算,即

其中,σst是從節(jié)點(diǎn)s到節(jié)點(diǎn)t的所有最短路徑總數(shù),σst(i) 表示這些路徑經(jīng)過節(jié)點(diǎn)i的次數(shù).對(duì)于有向網(wǎng)絡(luò),如果從節(jié)點(diǎn)s到t存在最短路徑,則稱節(jié)點(diǎn)s到t可達(dá),否則稱為不可達(dá).

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

復(fù)雜網(wǎng)絡(luò)能控性的概念由卡爾曼[54]在1960 年首先提出.對(duì)于一個(gè)復(fù)雜網(wǎng)絡(luò)系統(tǒng)或線性時(shí)不變(Linear time invariant,LTI)系統(tǒng)

其中,A和B分別為N ×N和N ×ND常系數(shù)矩陣,分別代表網(wǎng)絡(luò)的鄰接矩陣和LTI 系統(tǒng)外部控制器所控制的節(jié)點(diǎn),x是狀態(tài)向量,u是控制輸入,卡爾曼準(zhǔn)則 (Kalman criterion)[54]提出該系統(tǒng)能控的充分必要條件是系統(tǒng)的能控性矩陣

滿足行滿秩,該能控性稱為復(fù)雜網(wǎng)絡(luò)的狀態(tài)能控性(State controllable).結(jié)構(gòu)能控性的概念是狀態(tài)能控性的泛化.對(duì)于常參數(shù)系數(shù)矩陣A和B,如果存在一組非零參數(shù)值可以確保系統(tǒng)是狀態(tài)能控的,那么則稱該系統(tǒng)是結(jié)構(gòu)能控的(Structural controllable).對(duì)于一個(gè)能控系統(tǒng),其狀態(tài)向量x可以通過適當(dāng)?shù)目刂戚斎雞(ND×1 向量),從任意初始狀態(tài)驅(qū)動(dòng)至任意目標(biāo)狀態(tài).

1.1.3 匹配

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

圖1 匹配和節(jié)點(diǎn)控制中心性的例子Fig.1 Examples of matching and node control centrality

1.1.4 節(jié)點(diǎn)控制中心性

節(jié)點(diǎn)控制中心性(Control centrality)[38]度量單個(gè)節(jié)點(diǎn)做為控制節(jié)點(diǎn)的控制范圍,其定義為

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

1.1.5 關(guān)鍵連邊和關(guān)鍵節(jié)點(diǎn)

Liu等[18]將有向網(wǎng)絡(luò)連邊依據(jù)其對(duì)能控性的貢獻(xiàn)分為3 類: 1)關(guān)鍵連邊,刪除任一關(guān)鍵連邊會(huì)導(dǎo)致系統(tǒng)能控性下降,也就是需要額外增加一個(gè)控制節(jié)點(diǎn);2)冗余連邊,刪除任一冗余連邊不影響系統(tǒng)的能控性;3)普通連邊,刪除一條普通連邊不會(huì)導(dǎo)致能控性下降,但是會(huì)改變可能的最大匹配.其中冗余連邊和普通連邊可稱為非關(guān)鍵連邊.圖2(a)和圖2(c)分別舉例說明了關(guān)鍵連邊與普通連邊.

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

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

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

圖3 給出了節(jié)點(diǎn)分類舉例.圖3(a)中節(jié)點(diǎn)2 是關(guān)鍵節(jié)點(diǎn),遭攻擊后節(jié)點(diǎn)1和3 分別須單獨(dú)的控制輸入;圖3(b)中節(jié)點(diǎn)6 是亞關(guān)鍵節(jié)點(diǎn),遭攻擊后雖然控制節(jié)點(diǎn)數(shù)不變,但節(jié)點(diǎn)4 由匹配節(jié)點(diǎn)變?yōu)榉瞧ヅ涔?jié)點(diǎn);圖3(c)中節(jié)點(diǎn)7 為普通節(jié)點(diǎn),遭攻擊后控制節(jié)點(diǎn)數(shù)不變,非匹配節(jié)點(diǎn)數(shù)也不變(原先非匹配節(jié)點(diǎn)為7和9,攻擊后非匹配節(jié)點(diǎn)為8和9);圖3(d)中節(jié)點(diǎn)8 為冗余節(jié)點(diǎn),將其刪除后,系統(tǒng)所需控制節(jié)點(diǎn)減少1.

圖3 按文獻(xiàn)[57]節(jié)點(diǎn)分類舉例Fig.3 An example of node classification according to [57]

1.2 能控性度量

通常,復(fù)雜網(wǎng)絡(luò)能控性可由控制節(jié)點(diǎn)的密度(nD)來量化表示,即

其中,ND是系統(tǒng)所需控制節(jié)點(diǎn)的總和,N是系統(tǒng)中節(jié)點(diǎn)數(shù)總和.nD∈[1/N,1],當(dāng)nD=1/N表示當(dāng)前網(wǎng)絡(luò)的N節(jié)點(diǎn)只需一個(gè)控制節(jié)點(diǎn),此時(shí)的能控性最佳;而當(dāng)nD=1 則表示當(dāng)前網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)都需要一個(gè)單獨(dú)的控制器,此時(shí)網(wǎng)絡(luò)能控性最差.系統(tǒng)具有較小的nD值,表示該系統(tǒng)的能控性較好.

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

其中,|E?|是最大匹配E?中的連邊數(shù).式(8)說明網(wǎng)絡(luò)所需控制節(jié)點(diǎn)數(shù)等于網(wǎng)絡(luò)中非匹配節(jié)點(diǎn)的個(gè)數(shù).當(dāng)網(wǎng)絡(luò)非完全匹配時(shí),需ND=N ?|E?|個(gè)控制節(jié)點(diǎn),即將控制器加載于ND個(gè)非匹配節(jié)點(diǎn).當(dāng)網(wǎng)絡(luò)為完全匹配時(shí),僅需ND=1 個(gè)控制節(jié)點(diǎn),此時(shí)控制器可加載于任意節(jié)點(diǎn).

為了識(shí)別任意結(jié)構(gòu)以及加權(quán)網(wǎng)絡(luò)達(dá)到能控狀態(tài)所需的最小驅(qū)動(dòng)節(jié)點(diǎn)數(shù),Yuan等[20]根據(jù)卡爾曼準(zhǔn)則的等價(jià)條件PBH (Popov-Belevitch-Hautus) 秩提出精確能控性,其所需控制節(jié)點(diǎn)個(gè)數(shù)可由式(9)計(jì)算獲得,即

如果矩陣A滿秩,需ND=1 個(gè)控制節(jié)點(diǎn);否則,需N ?rank(A)個(gè)控制節(jié)點(diǎn).

1.3 能控性魯棒性定義

復(fù)雜網(wǎng)絡(luò)能控性描述了當(dāng)前系統(tǒng)的能控性狀態(tài);而能控性魯棒性則刻畫在受到攻擊的情況下,復(fù)雜網(wǎng)絡(luò)能控性的變化情況.

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

其中,Q(i) 表示當(dāng)網(wǎng)絡(luò)中i個(gè)節(jié)點(diǎn)被攻擊之后,最大連通子圖的節(jié)點(diǎn)數(shù)占當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比例,其范圍是 [ 1/N,1],當(dāng)Q(i)=1/N表示該網(wǎng)絡(luò)包含N個(gè)離散節(jié)點(diǎn),而當(dāng)Q(i)=1 則表示該網(wǎng)絡(luò)節(jié)點(diǎn)互相連通.類似地,RLCC在連邊攻擊時(shí)計(jì)算為

其中,Q(i) 表示當(dāng)網(wǎng)絡(luò)中i條連邊被攻擊之后,最大聯(lián)通子圖的節(jié)點(diǎn)數(shù)占當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比例;M為網(wǎng)絡(luò)中的連邊總數(shù).式(10)～(15)中的上標(biāo)N和E分別表示節(jié)點(diǎn)攻擊和連邊攻擊.

1.3.1 基于能控性曲線的定義

能控性魯棒性即系統(tǒng)在遭受節(jié)點(diǎn)或連邊攻擊之后,余下網(wǎng)絡(luò)的能控性.它是一組能控性值的序列,其中節(jié)點(diǎn)攻擊下能控性魯棒性定義為

其中,ND(i) 是當(dāng)i個(gè)節(jié)點(diǎn)遭受攻擊后,所需的控制節(jié)點(diǎn)數(shù);N ?i為i個(gè)節(jié)點(diǎn)遭攻擊后的網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù),隨著每次攻擊逐一減少.同樣地,連邊攻擊下能控性魯棒性定義為

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

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

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

1.3.2 基于節(jié)點(diǎn)控制中心性的定義

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

其中,G′(n)是由G刪除n節(jié)點(diǎn)后得到的網(wǎng)絡(luò);Cc(G,i)表示網(wǎng)絡(luò)G中節(jié)點(diǎn)i的節(jié)點(diǎn)控制中心性; E [·] 表示數(shù)學(xué)期望.作為預(yù)期魯棒控制中心性的擴(kuò)展,即

其中,e是節(jié)點(diǎn)i可達(dá)的任意一條邊.相較于ERCC而言,GRCC (Generic robust control centrality)不限定在當(dāng)前網(wǎng)絡(luò)中攻擊n個(gè)節(jié)點(diǎn)這一條件.ERCC和GRCC 適用于度量隨機(jī)攻擊情況下,某節(jié)點(diǎn)i的控制范圍的魯棒程度,因而可根據(jù)ERCC 或GRCC 選擇適當(dāng)?shù)目刂乒?jié)點(diǎn).

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

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

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

圖4 列舉了兩個(gè)復(fù)雜網(wǎng)絡(luò)net1和net2 在受到同種攻擊情況下的能控性曲線,其中Rc表示基于能控性曲線的能控性魯棒性,Rk表示基于排序的能控性魯棒性.對(duì)兩個(gè)網(wǎng)絡(luò)在相同的受攻擊節(jié)點(diǎn)比例下進(jìn)行比較排序,例如,當(dāng)受攻擊節(jié)點(diǎn)比例為0.1 時(shí),net2 排序?yàn)?,net1 排序?yàn)?.Rk為其排序的整體平均值.

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

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

1.4 能控性魯棒性的預(yù)測

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

1.5 能控性魯棒性研究框架

目前的研究成果主要集中在對(duì)復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的探索和優(yōu)化兩個(gè)方面.

對(duì)拓?fù)浣Y(jié)構(gòu)的探索體現(xiàn)在研究復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)和連邊對(duì)維持能控性魯棒性的重要性,即尋找網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)和連邊.由于目前尚沒有可以預(yù)測能控性魯棒性優(yōu)劣的可靠詳實(shí)的理論依據(jù),而且經(jīng)驗(yàn)指標(biāo)也不充足,這一研究目標(biāo)主要依靠設(shè)計(jì)高效的攻擊策略來實(shí)現(xiàn).本文第2 節(jié)回溯了隨機(jī)攻擊、基于特征的蓄意攻擊和啟發(fā)式攻擊,其中基于特征的蓄意攻擊和啟發(fā)式攻擊的研究對(duì)探索預(yù)測能控性魯棒性優(yōu)劣的指標(biāo) (或經(jīng)驗(yàn)指標(biāo)) 具有重要意義.

對(duì)拓?fù)浣Y(jié)構(gòu)的優(yōu)化主要包括模型優(yōu)化設(shè)計(jì)和重新連邊.本文第3 節(jié)回顧了主要的優(yōu)化策略,同時(shí)介紹了全齊性和模體 (包括環(huán)和鏈等) 結(jié)構(gòu)對(duì)提高能控性魯棒性的重要意義.

2 針對(duì)能控性魯棒性的攻擊

能控性魯棒性體現(xiàn)了在攻擊下,系統(tǒng)保持能控狀態(tài)的優(yōu)劣.在不同攻擊方式下,不同的復(fù)雜網(wǎng)絡(luò)系統(tǒng)呈現(xiàn)出不同的魯棒性.攻擊的類別基于對(duì)象可分為節(jié)點(diǎn)攻擊和連邊攻擊.通常,對(duì)節(jié)點(diǎn)攻擊后,該節(jié)點(diǎn)及其所有連邊從當(dāng)前網(wǎng)絡(luò)中刪除;對(duì)連邊攻擊后,僅該連邊從當(dāng)前網(wǎng)絡(luò)中刪除.

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

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

由于網(wǎng)絡(luò)連通性和能控性既有一定的相關(guān)性又存在差別,即能控必須連通,而連通未必能控.本文討論的攻擊以破壞網(wǎng)絡(luò)能控性為主,文中描述的攻擊效果以破壞網(wǎng)絡(luò)能控性為目標(biāo).

2.1 隨機(jī)攻擊

隨機(jī)攻擊是指均勻隨機(jī)地選擇復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)或連邊進(jìn)行攻擊.Sun等[61]指出,在隨機(jī)攻擊下,網(wǎng)絡(luò)所需控制節(jié)點(diǎn)數(shù)的增量,可以根據(jù)網(wǎng)絡(luò)中關(guān)鍵連邊的數(shù)量估算得到,即

當(dāng)被攻擊的連邊數(shù)小于關(guān)鍵連邊數(shù)時(shí),關(guān)鍵連邊會(huì)以p(Mc)=Mc/M的概率被攻擊.每攻擊一條關(guān)鍵連邊,所需的控制節(jié)點(diǎn)數(shù)增加1;若攻擊到非關(guān)鍵連邊,所需控制節(jié)點(diǎn)數(shù)保持不變.如果被攻擊的連邊總數(shù)大于關(guān)鍵連邊數(shù)(即Mr >Mc),則式(18)不成立,因?yàn)榇藭r(shí)網(wǎng)絡(luò)中的關(guān)鍵連邊已經(jīng)發(fā)生變化.實(shí)際上,攻擊1 條連邊就可能引起關(guān)鍵連邊的變化,如圖6 舉例所示.在圖6(a)中 連邊(2,4)原本是非關(guān)鍵連邊,當(dāng)連邊(2,3)和(3,4)被攻擊以后,則變成了關(guān)鍵連邊;在圖6(b)中節(jié)點(diǎn)2,3,4原本都是關(guān)鍵節(jié)點(diǎn),但當(dāng)節(jié)點(diǎn)1 被攻擊以后,它們都成為非關(guān)鍵節(jié)點(diǎn);接著,當(dāng)節(jié)點(diǎn)4 遭受攻擊之后,節(jié)點(diǎn)2 又成為關(guān)鍵節(jié)點(diǎn).

圖6 關(guān)鍵連邊和關(guān)鍵節(jié)點(diǎn)在遭受攻擊過程中變化Fig.6 Critical edges and nodes may change during attacks

Liu等[38]利用有向網(wǎng)絡(luò)中的層級(jí)結(jié)構(gòu),設(shè)計(jì)了隨機(jī)上/下游攻擊,旨在攻擊隨機(jī)選取的節(jié)點(diǎn)的上游或者下游節(jié)點(diǎn).該攻擊比普通隨機(jī)攻擊以更大的概率攻擊到樞紐(Hub)節(jié)點(diǎn),因而比普通隨機(jī)攻擊更有效.以圖1(c)中節(jié)點(diǎn)5 為例,其上游節(jié)點(diǎn)為節(jié)點(diǎn)1,下游節(jié)點(diǎn)為節(jié)點(diǎn)6和7.

2.2 基于特征的蓄意攻擊

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

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與能控性之間關(guān)聯(lián)的研究較多[27,32,71?73],而與能控性魯棒性相關(guān)的指標(biāo)或特征研究相對(duì)較少.目前尚無可以預(yù)測能控性魯棒性優(yōu)劣的可靠詳實(shí)的理論依據(jù),而且經(jīng)驗(yàn)指標(biāo)也不充足.節(jié)點(diǎn)攻擊的研究較多,而連邊攻擊的研究較少[74],其原因是: 1) 節(jié)點(diǎn)攻擊相對(duì)有效,攻擊節(jié)點(diǎn)時(shí)其連邊也同時(shí)被刪除,而連邊攻擊并不影響節(jié)點(diǎn);2) 節(jié)點(diǎn)的特征屬性相對(duì)明確,而連邊的屬性相對(duì)模糊,如有向圖的節(jié)點(diǎn)具有明確的出度和入度定義,而連邊的出度和入度不同定義較多[35,47,75].

2.2.1 基于度數(shù)和介數(shù)的攻擊

基于度數(shù)的攻擊旨在攻擊網(wǎng)絡(luò)中度數(shù)最大的節(jié)點(diǎn)(或連邊).Holme等[35]將基于度和介數(shù)的節(jié)點(diǎn)攻擊分別分為基于初始分布的攻擊和重新計(jì)算分布的攻擊.前者依據(jù)最初網(wǎng)絡(luò)的度數(shù)或介數(shù)分布,由大到小依次攻擊,而后者則在每次攻擊后重新計(jì)算.由于網(wǎng)絡(luò)的統(tǒng)計(jì)特征在攻擊后通常會(huì)發(fā)生較大變化,重新計(jì)算的攻擊效果要優(yōu)于基于初始分布的攻擊[35,76],因而本文默認(rèn)基于度數(shù)或介數(shù)的攻擊中,度數(shù)或介數(shù)最大的節(jié)點(diǎn)需要在每次攻擊后重新計(jì)算.

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

Nguyen等[77]觀察發(fā)現(xiàn)基于介數(shù)攻擊在攻擊后期效果變?nèi)?由此設(shè)計(jì)了一個(gè)約束條件,即如果當(dāng)前(全局)介數(shù)最高節(jié)點(diǎn)屬于最大連通子圖,則攻擊該節(jié)點(diǎn);否則攻擊最大連通子圖(局部)介數(shù)最大的節(jié)點(diǎn).

作為最常用的攻擊度量,度數(shù)和介數(shù)經(jīng)常一起用于攻擊.Nie等[76]通過預(yù)先給度數(shù)最大和介數(shù)最大的節(jié)點(diǎn)分配權(quán)值來分配兩者被攻擊的概率,即

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

研究發(fā)現(xiàn),基于度數(shù)的節(jié)點(diǎn)攻擊[86]比隨機(jī)節(jié)點(diǎn)攻擊更能有效地破壞隨機(jī)網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的能控性.Lu等[87]發(fā)現(xiàn)節(jié)點(diǎn)攻擊的破壞力大于連邊攻擊,同時(shí),異質(zhì)網(wǎng)絡(luò)的能控性魯棒性要劣于同質(zhì)網(wǎng)絡(luò).此外,對(duì)于許多實(shí)際網(wǎng)絡(luò)來說,基于介數(shù)攻擊對(duì)能控性破壞力最強(qiáng)[87].

對(duì)于本地世界網(wǎng)絡(luò)(Local-world network)[88?89],Sun等[90]發(fā)現(xiàn)基于度數(shù)的節(jié)點(diǎn)攻擊對(duì)本地世界規(guī)模較大的網(wǎng)絡(luò)更具破壞力,而對(duì)本地世界規(guī)模小的網(wǎng)絡(luò)破壞力較小.文獻(xiàn)[90]的研究包括連通魯棒性和能控性魯棒性.Lou等[57]以最大度數(shù)和最大介數(shù)為依據(jù),每次選取破壞程度較大的對(duì)象進(jìn)行攻擊.基于負(fù)載(介數(shù))的連邊攻擊[91]能有效地破壞網(wǎng)絡(luò)能控性.連邊攻擊不僅能破壞連通性和能控性,也能引起無標(biāo)度網(wǎng)絡(luò)的級(jí)聯(lián)故障.

2.2.2 其他蓄意攻擊

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

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

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

2.3 啟發(fā)式攻擊

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

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

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

本小節(jié)和第3.2 節(jié)可視為同一問題的不同角度分析.對(duì)于同一種網(wǎng)絡(luò)在不同攻擊下,使其能控性下降最快速明顯的攻擊為最有效攻擊;將同一種攻擊方式用于不同拓?fù)浣Y(jié)構(gòu),其中能控性保持最好的網(wǎng)絡(luò)可視為能控性魯棒性最好的拓?fù)浣Y(jié)構(gòu).

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

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

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

3 能控性魯棒性優(yōu)化

能控性魯棒性優(yōu)化旨在提高復(fù)雜網(wǎng)絡(luò)對(duì)各種攻擊的抵御能力.以第1.3.1 節(jié)的度量為例,定義如下.

定義 1.一個(gè)復(fù)雜網(wǎng)絡(luò)G?稱為能控性魯棒性最優(yōu)網(wǎng)絡(luò)(簡稱最優(yōu)網(wǎng)絡(luò)),當(dāng)且僅當(dāng)

成立,其中,? 為適用解空間,即所有滿足約束條件的復(fù)雜網(wǎng)絡(luò)G構(gòu)成的解空間;Rc可由式(14)或式(15)計(jì)算得到.

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

網(wǎng)絡(luò)模型優(yōu)化設(shè)計(jì)和對(duì)網(wǎng)絡(luò)進(jìn)行重新連邊為常用的能控性魯棒性優(yōu)化手段.全齊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在研究中認(rèn)為是具有最優(yōu)的能控性魯棒性.此外,復(fù)雜網(wǎng)絡(luò)中模體對(duì)保持網(wǎng)絡(luò)能控性魯棒性具有一定的促進(jìn)作用.表1 列舉了常見優(yōu)化策略的優(yōu)點(diǎn)與不足.以下各小節(jié)針對(duì)這幾個(gè)方面分別進(jìn)行討論.

表1 常用能控性魯棒性優(yōu)化策略的優(yōu)點(diǎn)與不足Table 1 Pros and cons of the strategies for controllability robustness optimization

3.1 網(wǎng)絡(luò)模型優(yōu)化設(shè)計(jì)

Yan 等基于同余論(Congruence theory)構(gòu)造了同余網(wǎng)絡(luò)MCN (Multiplex congruence network)[122],其生成方式如下: 首先對(duì)所有N節(jié)點(diǎn)進(jìn)行1 到N編號(hào),如果兩個(gè)節(jié)點(diǎn)i和j滿足:

則存在一條連邊Aij,其中r為j除以i得到的余數(shù).相同余數(shù)的所有節(jié)點(diǎn)構(gòu)成同于網(wǎng)絡(luò)的一層.同余網(wǎng)絡(luò)的每一層是無標(biāo)度網(wǎng)絡(luò),屬異質(zhì)(Heterogeneous)網(wǎng)絡(luò),其出度分布服從

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

Lou等[113?114]發(fā)現(xiàn)多鏈和多環(huán)結(jié)構(gòu)有助于提高能控性魯棒性,提出了基于工業(yè)流水線的q-回路網(wǎng)絡(luò)QSN,由一條主鏈和若干回路構(gòu)成,回路的數(shù)量由參數(shù)q∈[0,1] 控制.其第r(r=1,···,N ?1) 層第i(i=1,···,N) 節(jié)點(diǎn)的出度可由下式計(jì)算:

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

隨機(jī)三角形網(wǎng)絡(luò)RTN[50,106]基于Henneberg 增長,由大量的有向三角形構(gòu)成.將其擴(kuò)展到四邊形,就形成了隨機(jī)四邊形網(wǎng)絡(luò)RRN[50].在這兩個(gè)模型中,任意一個(gè)節(jié)點(diǎn)都至少處于一個(gè)三角形/四邊形(有向環(huán))當(dāng)中.這些多環(huán)結(jié)構(gòu)的存在,使它們的能控性魯棒性較好.

極同質(zhì)EH 網(wǎng)絡(luò)[116]中任一節(jié)點(diǎn)i(i=1,2,···,N) 的出度和入度被限定在極小范圍內(nèi),也就是

3.2 不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的能控性魯棒性比較

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

文獻(xiàn)[115]通過實(shí)驗(yàn)比較得出當(dāng)反向連邊概率為0.5 時(shí),QSNR 網(wǎng)絡(luò)的能控性魯棒性最佳,此時(shí)QSNR 的能控性魯棒性優(yōu)于QSN.

現(xiàn)有研究證實(shí),極同質(zhì)EH 網(wǎng)絡(luò)[116]是在給定網(wǎng)絡(luò)規(guī)模(N節(jié)點(diǎn)和M連邊)情況下,能控性魯棒性最優(yōu)的結(jié)構(gòu)(如圖7 所示).同時(shí),Lou等[116]提出的隨機(jī)連邊矯正RER (Random edge rectification)策略,可將任何網(wǎng)絡(luò)結(jié)構(gòu),改變?yōu)镋H 網(wǎng)絡(luò),同時(shí),與EH 網(wǎng)絡(luò)越近似則該網(wǎng)絡(luò)的能控性魯棒性越好.

表2 列舉了幾種能控性魯棒性優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu).這些網(wǎng)絡(luò)都由優(yōu)化設(shè)計(jì)得到,其中QSNR和EH 需要進(jìn)行重新連邊優(yōu)化.僅EH 結(jié)構(gòu)具有全齊屬性.除了MCN 僅具有多鏈結(jié)構(gòu),其余5種網(wǎng)絡(luò)同時(shí)具有多鏈和多環(huán)結(jié)構(gòu).

表2 能控性魯棒性優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)Table 2 Comparison of network topologies with optimized controllability robustness

3.3 重新連邊優(yōu)化

重新連邊(Rewiring)[119]通常分為3種形式:1)基于度保持(Degree-preserving)的重新連邊: 保持各節(jié)點(diǎn)出度和入度不變,重新調(diào)整連邊;2)保持網(wǎng)絡(luò)基本骨架不變,對(duì)連邊的方向進(jìn)行調(diào)整;3)保持網(wǎng)絡(luò)整體節(jié)點(diǎn)和連邊數(shù)目不變,對(duì)網(wǎng)絡(luò)進(jìn)行任意重構(gòu).其中第1種方式為最常用的策略.本小節(jié)只討論前兩種方式,第3種將在第3.4 節(jié)討論.不同的重新連邊策略本質(zhì)上是對(duì)式(22)的 ? 進(jìn)行了不同約束,而優(yōu)化的目標(biāo)是相同的.

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

重新連邊可看作優(yōu)化問題,基于不同的目標(biāo)函數(shù),網(wǎng)絡(luò)的優(yōu)化趨向不同.Chan等[65]以譜度量[124?128]為目標(biāo)函數(shù),通過基于度保持的重新連邊策略來優(yōu)化連通魯棒性.譜度量是常用的用于估算和預(yù)測復(fù)雜網(wǎng)絡(luò)連通魯棒性的工具[129].然而,目前尚未發(fā)現(xiàn)譜度量或其他復(fù)雜網(wǎng)絡(luò)特征與能控性魯棒性具有較強(qiáng)的相關(guān)性[49].

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

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

啟發(fā)式算法不僅應(yīng)用于網(wǎng)絡(luò)攻擊(見第2.3 節(jié)),同時(shí)也應(yīng)用于優(yōu)化復(fù)雜網(wǎng)絡(luò)魯棒性.啟發(fā)式算法包含一個(gè)種群的解,其中每個(gè)解代表一個(gè)網(wǎng)絡(luò)結(jié)構(gòu),通過變異和交叉,以適當(dāng)?shù)剡x擇算子來引導(dǎo)解的演化趨勢,從而產(chǎn)生出高質(zhì)量的解,即魯棒性好的網(wǎng)絡(luò)結(jié)構(gòu).

Buesser等[133]用模擬退火(Simulated annealing)算法來優(yōu)化網(wǎng)絡(luò)連通魯棒性.Zhou等[134]以式(10)作為目標(biāo)函數(shù),用文化基因算法(Memetic algorithm)來優(yōu)化無標(biāo)度網(wǎng)絡(luò)的連通魯棒性.

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

與攻擊方式一樣,已有研究大部分側(cè)重于提高連通魯棒性.能控性魯棒性的優(yōu)化可借鑒連通魯棒性的優(yōu)化方法,但是由于評(píng)價(jià)標(biāo)準(zhǔn)和優(yōu)化目標(biāo)的不同,能控性魯棒性的優(yōu)化有其自身特點(diǎn).通過刪除冗余連邊和增加關(guān)鍵或普通連邊的方式[139?140],減少網(wǎng)絡(luò)中非匹配節(jié)點(diǎn)數(shù),可以提高復(fù)雜網(wǎng)絡(luò)能控性.Wang等[141]以合作者比例(維持合作能力)和式(14)所示能控性魯棒性定義作為兩個(gè)優(yōu)化目標(biāo),以多目標(biāo)進(jìn)化算法來同時(shí)優(yōu)化它們.

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

3.4 全齊網(wǎng)絡(luò)

基本的網(wǎng)絡(luò)結(jié)構(gòu),如鏈?zhǔn)健h(huán)式、星型等結(jié)構(gòu)無法解決一些新涌現(xiàn)的網(wǎng)絡(luò)問題,如能控性網(wǎng)絡(luò)子結(jié)構(gòu)的設(shè)計(jì)和優(yōu)化網(wǎng)絡(luò)同步性等問題.Shi等[143]借鑒龐加萊的剖分思想,把網(wǎng)絡(luò)分解為全齊性子網(wǎng)絡(luò).以團(tuán)(Clique)為基本單位建立一系列二元域上的向量空間表述網(wǎng)絡(luò)結(jié)構(gòu).模型和實(shí)際網(wǎng)絡(luò)中都存在大量全齊性子網(wǎng)絡(luò),是支持網(wǎng)絡(luò)功能的重要基礎(chǔ)結(jié)構(gòu),對(duì)網(wǎng)絡(luò)同步性[144]、能控性[18,33]、連通魯棒性[37]等具有重要意義.Fan等[145]研究了網(wǎng)絡(luò)的圈結(jié)構(gòu),提出刻畫網(wǎng)絡(luò)圈結(jié)構(gòu)的邊界矩陣和衡量節(jié)點(diǎn)重要性的圈指標(biāo).

Lou等[116]基于小規(guī)模網(wǎng)絡(luò)的遍歷搜索,歸納了經(jīng)驗(yàn)必要條件ENC (Empirical necessary condition).ENC 指出滿足式(22)的最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu),應(yīng)滿足式(26).Lou等[116]發(fā)現(xiàn)對(duì)于給定N節(jié)點(diǎn)和M連邊,其所有網(wǎng)絡(luò)結(jié)構(gòu)、滿足ENC 的網(wǎng)絡(luò)、以及最優(yōu)網(wǎng)絡(luò)之間的關(guān)系如圖8 所示.

圖8 所有N 節(jié)點(diǎn)和M 連邊網(wǎng)絡(luò),滿足ENC 的網(wǎng)絡(luò)、全齊網(wǎng)絡(luò),以及最優(yōu)網(wǎng)絡(luò)之間的關(guān)系圖Fig.8 The relationship diagram of theN-nodeM-edge networks,ENC networks,totally homogeneous networks,and the optimal networks

同時(shí),Lou等[116]提出了隨機(jī)連邊矯正RER(Random edge rectification)策略,該策略使復(fù)雜網(wǎng)絡(luò)趨于滿足式(26)的結(jié)構(gòu),此外,使用RER 策略的次數(shù)與網(wǎng)絡(luò)能控性魯棒性的提高成正比.RER屬于第3種重新連邊優(yōu)化方式,即保持網(wǎng)絡(luò)整體節(jié)點(diǎn)數(shù)N和連邊數(shù)M不變,對(duì)網(wǎng)絡(luò)進(jìn)行(任意)重構(gòu),以達(dá)到優(yōu)化能控性魯棒性的目的.

經(jīng)驗(yàn)地,全齊網(wǎng)絡(luò)滿足ENC 條件,同時(shí)也是最優(yōu)網(wǎng)絡(luò);然而顯然并非所有的最優(yōu)網(wǎng)絡(luò)都屬于全齊網(wǎng)絡(luò),其關(guān)系如圖8 所示.

3.5 模體

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

同余網(wǎng)絡(luò)MCN[122]中存在較多鏈?zhǔn)侥ｓw結(jié)構(gòu).每一條鏈僅用一個(gè)控制器即可保證鏈路能控性.在受到攻擊時(shí),針對(duì)驅(qū)動(dòng)節(jié)點(diǎn)的攻擊不會(huì)破壞鏈路能控性;反而隨機(jī)攻擊更容易造成鏈路斷裂,從而增加額外控制器.Lou等[113]進(jìn)一步將鏈?zhǔn)侥ｓw擴(kuò)展至環(huán)式模體.環(huán)式模體的反饋連接比鏈?zhǔn)降那梆佭B接具有更好的能控性魯棒性.QSN 網(wǎng)絡(luò)中含有大量的鏈?zhǔn)胶铜h(huán)式模體[113].多模體結(jié)構(gòu)的QSN和MCN在抵御攻擊方面優(yōu)于一般的無標(biāo)度網(wǎng)絡(luò).進(jìn)一步地,對(duì)QSN 的非主鏈連邊隨機(jī)反向重連可增加3-環(huán)、4-環(huán)和4-鏈(n-環(huán)/鏈指由n個(gè)節(jié)點(diǎn)構(gòu)成的環(huán)/鏈)結(jié)構(gòu),增強(qiáng)了能控性魯棒性.

Chen等[50]比較了具有鏈?zhǔn)侥ｓw的MCN,具有環(huán)式模體的QSN,以3-環(huán)為基礎(chǔ)結(jié)構(gòu)RTN,以4-環(huán)為基礎(chǔ)結(jié)構(gòu)的RRN 等在不同攻擊下的能控性魯棒性,發(fā)現(xiàn)3-環(huán)和4-環(huán)的RRN和RTN 結(jié)構(gòu)在各種連邊攻擊下,保持較好的能控性.

4 展望與總結(jié)

本文圍繞3 個(gè)問題進(jìn)行歸納與總結(jié):

1)復(fù)雜網(wǎng)絡(luò)能控性魯棒性的定義和度量.不同的定義因側(cè)重點(diǎn)不同而稍有區(qū)別,須根據(jù)實(shí)際應(yīng)用場景選取適當(dāng)?shù)亩x和度量方式.

2)常見的復(fù)雜網(wǎng)絡(luò)攻擊方式及其對(duì)網(wǎng)絡(luò)連通性和能控性的危害.隨機(jī)攻擊的危害較小,對(duì)攻擊者來說需要掌握的網(wǎng)絡(luò)相關(guān)信息較少;基于特征的蓄意攻擊依據(jù)預(yù)先設(shè)定的特征對(duì)網(wǎng)絡(luò)的節(jié)點(diǎn)或連邊實(shí)施攻擊,取得的攻擊效果往往較好,對(duì)攻擊者來說需要掌握較多網(wǎng)絡(luò)相關(guān)信息;啟發(fā)式攻擊以智能計(jì)算優(yōu)化攻擊,往往需要具備較全面的網(wǎng)絡(luò)相關(guān)信息和較多的計(jì)算資源,同時(shí)攻擊效果的提升也較為顯著.

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

針對(duì)以上3 個(gè)問題,未來可研究內(nèi)容包括:

1)深度學(xué)習(xí)和計(jì)算智能可更廣泛地應(yīng)用于復(fù)雜網(wǎng)絡(luò)能控性魯棒性的預(yù)測、分析和優(yōu)化.目前,利用深度學(xué)習(xí)預(yù)測復(fù)雜網(wǎng)絡(luò)能控性魯棒性的研究和利用計(jì)算智能來生成優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究處于起步階段.深度學(xué)習(xí)和計(jì)算智能處理大規(guī)模問題能力的進(jìn)一步發(fā)展,將會(huì)對(duì)包括能控性魯棒性在內(nèi)的復(fù)雜網(wǎng)絡(luò)各項(xiàng)研究帶來新的機(jī)遇和挑戰(zhàn).

2)相關(guān)網(wǎng)絡(luò)特征與能控性魯棒性的相關(guān)性值得進(jìn)一步探索和研究,包括相關(guān)拓?fù)浣Y(jié)構(gòu)特征、關(guān)鍵節(jié)點(diǎn)和關(guān)鍵連邊的定義與搜索等.這一研究方向的難點(diǎn)在于網(wǎng)絡(luò)規(guī)模、拓?fù)浣Y(jié)構(gòu)、攻擊方式等同時(shí)具有多樣性.同時(shí),在實(shí)際網(wǎng)絡(luò)中,各節(jié)點(diǎn)和連邊存在權(quán)值等因素,因此,相對(duì)不容易形成一般性可泛化的理論結(jié)果.

3)全齊性網(wǎng)絡(luò)和經(jīng)驗(yàn)必要條件的進(jìn)一步研究和理論拓展.全齊性網(wǎng)絡(luò)和經(jīng)驗(yàn)必要條件的研究從簡單結(jié)構(gòu)開始,逐步推向一般情況,簡單的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比一般實(shí)際網(wǎng)絡(luò)更容易研究分析,實(shí)現(xiàn)理論突破.對(duì)經(jīng)驗(yàn)必要條件的理論證明,以及對(duì)經(jīng)驗(yàn)和理論充分條件的探索,將從理論上實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)能控性魯棒性的最優(yōu)化.

附錄A 本文所用符號(hào)列表

A鄰接矩陣

Aij鄰接矩陣中節(jié)點(diǎn)i和j之間的連邊

bi節(jié)點(diǎn)i的介數(shù)

B輸入矩陣

C能控性矩陣

E網(wǎng)絡(luò)連邊集合

G復(fù)雜網(wǎng)絡(luò)

ki節(jié)點(diǎn)i的度數(shù)

節(jié)點(diǎn)i的出度

節(jié)點(diǎn)i的入度

M網(wǎng)絡(luò)連邊數(shù)

Mc關(guān)鍵連邊數(shù)

Mr當(dāng)前已攻擊的連邊數(shù)

N網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)

ND網(wǎng)絡(luò)所需控制節(jié)點(diǎn)數(shù)

?ND網(wǎng)絡(luò)所需控制節(jié)點(diǎn)數(shù)增量

Nr當(dāng)前已攻擊的節(jié)點(diǎn)數(shù)

nD網(wǎng)絡(luò)所需控制節(jié)點(diǎn)密度

p(Mc)關(guān)鍵連邊比例

Rc平均能控性魯棒性

RLCC平均連通魯棒性

u控制向量

V網(wǎng)絡(luò)節(jié)點(diǎn)集合

x狀態(tài)向量

σij從節(jié)點(diǎn)i到j(luò)的最短路徑

? 適用解空間