節(jié)點(diǎn)分類及失效對(duì)網(wǎng)絡(luò)能控性的影響

孔 芝 袁 航 王立夫 郭 戈

近年來(lái),隨著科學(xué)技術(shù)的發(fā)展,人們已經(jīng)認(rèn)識(shí)到各種復(fù)雜系統(tǒng)是由相互作用和相互依賴的若干部分組成的具有特定功能的有機(jī)整體.而網(wǎng)絡(luò)是由節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊所組成的.如果用節(jié)點(diǎn)表示系統(tǒng)的各個(gè)組成部分,兩節(jié)點(diǎn)之間的邊表示各個(gè)組成部分之間的相互作用,那么網(wǎng)絡(luò)就為研究復(fù)雜系統(tǒng)提供了一種新的描述方式[1-5].例如神經(jīng)系統(tǒng)可以看作是由神經(jīng)細(xì)胞通過(guò)神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)[2];計(jì)算機(jī)網(wǎng)絡(luò)可以看作是自主工作的計(jì)算機(jī)通過(guò)通信介質(zhì)(如光纜、同軸電纜等)相互連接形成的網(wǎng)絡(luò)[3];人際關(guān)系網(wǎng)是將每一個(gè)人作為一個(gè)節(jié)點(diǎn),如果兩個(gè)人之間存在某種關(guān)系(比如相識(shí))就連一條邊[4];類似的還有電力網(wǎng)絡(luò)和交通網(wǎng)絡(luò)等.

復(fù)雜網(wǎng)絡(luò)研究的近年來(lái)受到了許多關(guān)注,其最終目標(biāo)是尋找有效的策略來(lái)控制網(wǎng)絡(luò)的行為使其為人類服務(wù)[6-7].許多學(xué)者對(duì)復(fù)雜網(wǎng)絡(luò)的控制算法進(jìn)行了研究,并取得了豐碩的成果,如牽制控制[8-11],自適應(yīng)控制[12-13],同步控制及存在延時(shí)的網(wǎng)絡(luò)系統(tǒng)同步[14-19],最優(yōu)濾波[20]等方法都已應(yīng)用于網(wǎng)絡(luò)中.然而對(duì)網(wǎng)絡(luò)進(jìn)行控制算法應(yīng)用的前提條件是此網(wǎng)絡(luò)系統(tǒng)必須是能控的.另外,現(xiàn)實(shí)世界中很多復(fù)雜的系統(tǒng)問(wèn)題也可以抽象為網(wǎng)絡(luò)能控性問(wèn)題.例如,在錯(cuò)綜復(fù)雜的基因調(diào)控網(wǎng)絡(luò)中,如何選擇最有效的基因節(jié)點(diǎn)作為藥物的靶標(biāo),使得整個(gè)生物體網(wǎng)絡(luò)系統(tǒng)朝著預(yù)期的良好狀態(tài)發(fā)展;在電力網(wǎng)絡(luò)中,如何優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)使得可以用最少的變電站就能夠控制整個(gè)地區(qū)的電力供應(yīng);在計(jì)算機(jī)網(wǎng)絡(luò)中,當(dāng)部分計(jì)算機(jī)遭遇黑客襲擊后,如何重新選擇控制節(jié)點(diǎn)保證整個(gè)計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn).對(duì)于線性系統(tǒng)能控性的基礎(chǔ)理論已較為成熟,并廣泛應(yīng)用于工程中.然而,要把傳統(tǒng)的線性系統(tǒng)結(jié)構(gòu)能控性理論直接應(yīng)用到復(fù)雜系統(tǒng)或者復(fù)雜網(wǎng)絡(luò)中卻存在諸多困難.如何選擇一部分節(jié)點(diǎn)控制整個(gè)復(fù)雜網(wǎng)絡(luò),首要問(wèn)題是需要多少外界輸入信號(hào)才能使網(wǎng)絡(luò)達(dá)到期望狀態(tài),也就是滿足能控性條件的控制器的最少個(gè)數(shù)是多少.2011 年,Liu 等[21]在Nature上發(fā)表了關(guān)于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)能控性的論文通過(guò)引入圖論中的匹配理論得到了求解最少輸入信號(hào)和驅(qū)動(dòng)節(jié)點(diǎn)的最少(最小)輸入定理,建立復(fù)雜網(wǎng)絡(luò)能控性研究框架.Yuan等[22]從PBH 能控性判據(jù)出發(fā)提出了求解網(wǎng)絡(luò)嚴(yán)格能控性的理論框架,可用于求解具有確定性邊權(quán)和任意結(jié)構(gòu)的網(wǎng)絡(luò)的能控性.許多學(xué)者在這兩個(gè)框架下研究了時(shí)變網(wǎng)絡(luò)的能控性[23]、深度耦合動(dòng)態(tài)網(wǎng)絡(luò)的能控性[24]、對(duì)稱網(wǎng)絡(luò)結(jié)構(gòu)能控性[25]、具有對(duì)抗相互作用的多智能體網(wǎng)絡(luò)的能控性[26]和多層網(wǎng)絡(luò)的能控性[27]等問(wèn)題,這些研究大大提高了人們對(duì)網(wǎng)絡(luò)能控性問(wèn)題的認(rèn)識(shí).

現(xiàn)實(shí)生活中,網(wǎng)絡(luò)某些節(jié)點(diǎn)遭到攻擊或發(fā)生故障失效,可能會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)失控,例如互聯(lián)網(wǎng)絡(luò)中某個(gè)計(jì)算機(jī)或服務(wù)器發(fā)生故障可能導(dǎo)致互聯(lián)網(wǎng)絡(luò)癱瘓;電力網(wǎng)絡(luò)中某個(gè)電站或變壓器發(fā)生故障可能會(huì)導(dǎo)致電力系統(tǒng)癱瘓等.網(wǎng)絡(luò)中不同節(jié)點(diǎn)失效時(shí),對(duì)整個(gè)網(wǎng)絡(luò)功能的影響是不同的.Pu 等[28]研究了單一節(jié)點(diǎn)攻擊和級(jí)聯(lián)失效兩種攻擊模式下網(wǎng)絡(luò)可控性的影響,結(jié)果表明基于度的攻擊方式都比隨機(jī)攻擊對(duì)網(wǎng)絡(luò)能控性的影響更大.Liu 等[29]提出了一種隨機(jī)上游攻擊策略來(lái)破壞有向網(wǎng)絡(luò)的結(jié)構(gòu)能控性,該策略移除隨機(jī)選擇的點(diǎn)的上游節(jié)點(diǎn),相較于依據(jù)節(jié)點(diǎn)度的攻擊策略,該策略不需要知道網(wǎng)絡(luò)全局的拓?fù)浣Y(jié)構(gòu)信息.Lu 等[30]研究了邊失效對(duì)網(wǎng)絡(luò)能控性的影響,Pu 等[31]研究了最長(zhǎng)簡(jiǎn)單路徑失效時(shí)網(wǎng)絡(luò)能控性的影響,以上研究說(shuō)明當(dāng)失效邊介數(shù)越大或失效時(shí)簡(jiǎn)單路徑越長(zhǎng),對(duì)網(wǎng)絡(luò)能控性的影響更大.

綜上所述,可以發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性的影響的研究主要集中在部分節(jié)點(diǎn)或者邊失效對(duì)網(wǎng)絡(luò)能控性的影響上,主要針對(duì)具有某種結(jié)構(gòu)特征的節(jié)點(diǎn)或邊通過(guò)實(shí)驗(yàn)和仿真等手段給出結(jié)論,并未從理論層面給出節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性的影響.對(duì)于整個(gè)網(wǎng)絡(luò)而言,不同類型的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)能控性的影響也不相同:有些節(jié)點(diǎn)失效網(wǎng)絡(luò)能控性會(huì)增加,有些節(jié)點(diǎn)失效網(wǎng)絡(luò)的能控性保持不變,有些節(jié)點(diǎn)失效網(wǎng)絡(luò)能控性會(huì)降低.哪些節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性有何影響,至今未有明確結(jié)論.因此,本文為了研究此問(wèn)題將網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類,并從理論層面給出不同類型的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)能控性影響的確切結(jié)論.首先根據(jù)邊的方向和匹配關(guān)系提出一種網(wǎng)絡(luò)節(jié)點(diǎn)的分類方式,將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成九種類型,并給出了辨識(shí)節(jié)點(diǎn)類型的算法,然后研究了復(fù)雜網(wǎng)絡(luò)中某類節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性有何影響,給出了節(jié)點(diǎn)失效后網(wǎng)絡(luò)能控性的變化規(guī)律,最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證上述規(guī)律的有效性.

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

考慮一個(gè)具有N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),其動(dòng)力學(xué)方程表示為

其中x(t)=[x1,x2,···,xN]T表示網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài),xj(t) 表示第j個(gè)節(jié)點(diǎn)在t時(shí)刻時(shí)的狀態(tài);A=[aij]∈RN×N為網(wǎng)絡(luò)鄰接矩陣,其中aij代表節(jié)點(diǎn)j影響節(jié)點(diǎn)i的強(qiáng)度,aij ＞0 表示這種影響是積極,aij ＜0 表示這種影響是消極的,若aij=0 表示從節(jié)點(diǎn)j到節(jié)點(diǎn)i沒(méi)有連接關(guān)系,即節(jié)點(diǎn)j不影響節(jié)點(diǎn)i;u(t)=[u1,u2,···,uM] 表示M個(gè)輸入控制信號(hào)在t時(shí)刻的輸入量;B∈RN×M稱為輸入矩陣,表示外部輸入節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)的耦合關(guān)系,bij表示輸入信號(hào)uj(t) 與節(jié)點(diǎn)i之間的耦合連接.

對(duì)于復(fù)雜網(wǎng)絡(luò)系統(tǒng)(1),若存在一個(gè)分段連續(xù)的u(t),可在有限的時(shí)間內(nèi) [t0,tf] 從任意初始狀態(tài)x(t0) 驅(qū)動(dòng)到任意期望的終端狀態(tài)x(tf),則稱此系統(tǒng)的狀態(tài)是完全能控.在控制理論中,判斷系統(tǒng)是否完全能控可通過(guò)卡爾曼判據(jù),對(duì)于系統(tǒng)(1)完全能控當(dāng)且僅當(dāng)能控性矩陣C=[B,AB,···,AN-1B]是滿秩的,即

因此要使一個(gè)給定網(wǎng)絡(luò)能控需要尋找一個(gè)輸入矩陣B使得能控性矩陣C滿秩.

當(dāng)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間不考慮連接強(qiáng)度時(shí),即不考慮矩陣A與B具體數(shù)值,僅考慮矩陣中的元素是零或?yàn)楠?dú)立自由參數(shù),這時(shí)矩陣A與B稱為結(jié)構(gòu)矩陣.如果存在A與B中一組非零取值,使得網(wǎng)絡(luò)是能控的,則稱系統(tǒng)(1) 為結(jié)構(gòu)能控,也可記為(A,B)結(jié)構(gòu)能控.

對(duì)于有向復(fù)雜網(wǎng)絡(luò)G=(V,E),其中V為網(wǎng)絡(luò)的節(jié)點(diǎn)集,E為網(wǎng)絡(luò)的邊集.如果網(wǎng)絡(luò)邊集E的一個(gè)子集M中沒(méi)有兩條邊共享一個(gè)公共的起始節(jié)點(diǎn)或結(jié)束節(jié)點(diǎn),則M稱為G的一個(gè)匹配.G中邊數(shù)最多的匹配稱為G的最大匹配.最大匹配一般是非唯一的.如果一個(gè)節(jié)點(diǎn)是匹配中某條邊的結(jié)束節(jié)點(diǎn),則該節(jié)點(diǎn)為匹配節(jié)點(diǎn),否則,它為非匹配節(jié)點(diǎn).

Liu 等[21]通過(guò)將圖的匹配理論與結(jié)構(gòu)可控性相結(jié)合,提出了一種基于最大匹配算法求解最小驅(qū)動(dòng)節(jié)點(diǎn)集的分析復(fù)雜網(wǎng)絡(luò)能控性的理論框架,并給出最小輸入定理,證明了實(shí)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)可控所需獨(dú)立控制的節(jié)點(diǎn)集合等于非最大匹配的節(jié)點(diǎn)集合,其中需要被外部輸入施加控制的節(jié)點(diǎn)稱為網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn),驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)用ND表示,通過(guò)對(duì)這些驅(qū)動(dòng)節(jié)點(diǎn)施加外部輸入控制信號(hào)可使控制信息傳達(dá)到網(wǎng)絡(luò)中每一個(gè)普通節(jié)點(diǎn),可實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的完全能控.

引理 1.最小輸入定理[21]:網(wǎng)絡(luò)的最小輸入集等價(jià)于最小驅(qū)動(dòng)節(jié)點(diǎn)集(ND).如果網(wǎng)絡(luò)是完美匹配,最小輸入集是網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn);否則,它等于網(wǎng)絡(luò)最大匹配后未被匹配的節(jié)點(diǎn)集.用公式表示:

其中,N為有向網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù),|M|為網(wǎng)中最大匹配節(jié)點(diǎn)個(gè)數(shù).

網(wǎng)絡(luò)能控性大小可由控制網(wǎng)絡(luò)所需要的最小驅(qū)動(dòng)節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例來(lái)衡量,即網(wǎng)絡(luò)中的驅(qū)動(dòng)節(jié)點(diǎn)密度,記為

其大小反映該網(wǎng)絡(luò)能被控制的難易程度,控制網(wǎng)絡(luò)所需的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例越小,即nD越小,表明網(wǎng)絡(luò)越容易實(shí)現(xiàn)完全能控,反之,控制網(wǎng)絡(luò)所需的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例越大,即nD越大,表明網(wǎng)絡(luò)越難實(shí)現(xiàn)完全能控.

2 節(jié)點(diǎn)分類辨識(shí)及能控性分析

復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)失效會(huì)使網(wǎng)絡(luò)驅(qū)動(dòng)節(jié)點(diǎn)數(shù)發(fā)生變化,從而影響網(wǎng)絡(luò)的能控性.然而,不同的節(jié)點(diǎn)失效,對(duì)網(wǎng)絡(luò)的能控性的影響也不同.當(dāng)哪些節(jié)點(diǎn)失效,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)會(huì)增加? 哪些節(jié)點(diǎn)失效驅(qū)動(dòng)節(jié)點(diǎn)數(shù)會(huì)減少? 針對(duì)這個(gè)問(wèn)題,本節(jié)將網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類,研究不同類型節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)結(jié)構(gòu)可控性有何影響.

2.1 節(jié)點(diǎn)分類方式

在有向網(wǎng)絡(luò)中,節(jié)點(diǎn)與節(jié)點(diǎn)之間通過(guò)有向邊相連.節(jié)點(diǎn)與邊的連接存在以下四種關(guān)系:

A:只存在輸出邊,不存在輸入邊的節(jié)點(diǎn).如圖2中節(jié)點(diǎn)A所示,將這類節(jié)點(diǎn)構(gòu)成的集合記為VO.

圖2 節(jié)點(diǎn)與邊的四種關(guān)系Fig.2 Four relations between nodes and edges

B:只存在輸入邊,不存在輸出邊的節(jié)點(diǎn).如圖2中節(jié)點(diǎn)B所示,將這類節(jié)點(diǎn)構(gòu)成的集合記為VI.

C:既存在輸出邊又存在輸入邊的節(jié)點(diǎn).如圖2中節(jié)點(diǎn)C所示,將這類節(jié)點(diǎn)構(gòu)成的集合記為VIO.

D:既不存在輸出邊又不存在輸入邊的節(jié)點(diǎn).如圖2 中節(jié)點(diǎn)D所示,將這類節(jié)點(diǎn)構(gòu)成的集合記為VD.

對(duì)于任意網(wǎng)絡(luò)而言,最大匹配一般是非唯一.因此網(wǎng)絡(luò)中節(jié)點(diǎn)參與最大匹配的可能性也不相同,可根據(jù)匹配關(guān)系對(duì)原始的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類.

對(duì)于屬于VO的節(jié)點(diǎn)而言,即節(jié)點(diǎn)只包含輸出邊,則該類節(jié)點(diǎn)一定為最大匹配的起始節(jié)點(diǎn).可以將其分為以下兩種類型:

類型 1.輸出完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)在所有組的最大匹配中一定是最大匹配邊集的起始點(diǎn),則這個(gè)節(jié)點(diǎn)稱為輸出完全匹配節(jié)點(diǎn)(Output matching node,OM),將這類節(jié)點(diǎn)的集合記為VOM.

類型 2.輸出不完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)不是所有組最大匹配邊集的起始點(diǎn),則這個(gè)節(jié)點(diǎn)稱為輸出不完全匹配節(jié)點(diǎn)(Output non matching node,ONM),將這類節(jié)點(diǎn)的集合記為VONM.

例如圖1 中,節(jié)點(diǎn)v1,v2,v3只含輸出邊不含輸入邊,屬于VO.在四組最大匹配中,節(jié)點(diǎn)v3為所有組最大匹配集中匹配邊的起始節(jié)點(diǎn),屬于類型1 為OM 節(jié)點(diǎn).節(jié)點(diǎn)v1和v2屬于某些組最大匹配,不是所有組最大匹配邊集的起始點(diǎn)節(jié)點(diǎn),所以屬于類型2為ONM 節(jié)點(diǎn).這兩類節(jié)點(diǎn)集存在如下關(guān)系,

圖1 有向圖和二分圖的匹配Fig.1 Matching of directed graph and bipartite graph

對(duì)于屬于VI的節(jié)點(diǎn),即節(jié)點(diǎn)只存在輸入邊,則該類節(jié)點(diǎn)一定為最大匹配的終止節(jié)點(diǎn),可以分成以下兩種類型:

類型 3.輸入完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)在所有組的最大匹配中一定是最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)為輸入完全匹配節(jié)點(diǎn)(Input matching node,IM).將這類節(jié)點(diǎn)的集合記為VIM.

類型 4.輸入不完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)不是所有組最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)稱為輸入不完全匹配節(jié)點(diǎn)(Input non matching node,INM).將這類節(jié)點(diǎn)的集合記為VINM.

例如圖1 中,節(jié)點(diǎn)v4,v5,v6都屬于VI.四組最大匹配中,節(jié)點(diǎn)v4是所有組最大匹配邊集的終點(diǎn),所以其類型為IM 節(jié)點(diǎn),屬于VIM.節(jié)點(diǎn)v5和v6只存在于某些最大匹配中,不是所有組最大匹配邊集的終止節(jié)點(diǎn),所以其類型為INM,屬于VINM.這兩類節(jié)點(diǎn)集存在如下關(guān)系,

對(duì)于屬于VIO的節(jié)點(diǎn),即當(dāng)節(jié)點(diǎn)既包含輸出邊又包含輸入邊時(shí),根據(jù)節(jié)點(diǎn)匹配與被匹配的關(guān)系,可分為以下四種類型:

類型 5.輸入完全匹配和輸出完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)在所有組的最大匹配中一定是最大匹配邊集的起點(diǎn)也一定是最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)為輸入完全匹配和輸出完全匹配節(jié)點(diǎn)(Input matching and output matching node,IM&OM).將這類節(jié)點(diǎn)的集合記為VIM&OM.

類型 6.輸入不完全匹配和輸出完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)在所有組的最大匹配中一定是最大匹配邊集的起點(diǎn),但不是所有組最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)為輸入不完全匹配和輸出完全匹配節(jié)點(diǎn)(Input non matching and output matching node,INM&OM).將這類節(jié)點(diǎn)的集合記為VINM&OM.

類型 7.輸入完全匹配和輸出不完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)不是所有組最大匹配邊集的起點(diǎn),但在所有組的最大匹配中一定是最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)為輸入完全匹配和輸出不完全匹配節(jié)點(diǎn)(Input matching and output non matching node,IM&ONM).將這類節(jié)點(diǎn)的集合記為VIM&ONM.

類型 8.輸入不完全匹配和輸出不完全匹配節(jié)點(diǎn):如果該節(jié)點(diǎn)不是所有組最大匹配邊集的起點(diǎn),也不是所有組最大匹配邊集的終點(diǎn),則這個(gè)節(jié)點(diǎn)為輸入不完全匹配和輸出不完全匹配節(jié)點(diǎn)(Input non matching and output non matching node,INM&ONM),將這類節(jié)點(diǎn)的集合記為VINM&ONM.

圖3 節(jié)點(diǎn)分類Fig.3 Node classification

對(duì)于節(jié)點(diǎn)v6而言,和都只存在部分最大匹配情況中,所以節(jié)點(diǎn)v6既不是所有組最大匹配邊集的起點(diǎn),也不是所有組最大匹配邊集的終點(diǎn),因此節(jié)點(diǎn)v6類型為INM&ONM.

對(duì)于節(jié)點(diǎn)v8而言,只存在部分最大匹配中,而出現(xiàn)在所有最大匹配情況中,所以節(jié)點(diǎn)v8

不是所有組最大匹配邊集的起點(diǎn),但在所有組的最大匹配中一定是最大匹配邊集的終點(diǎn),因此節(jié)點(diǎn)v8類型為IM&ONM.

類型 9.孤立節(jié)點(diǎn):當(dāng)節(jié)點(diǎn)既不包含輸出邊也不包含輸入邊時(shí),該節(jié)點(diǎn)稱為孤立節(jié)點(diǎn)(記為VD,見(jiàn)圖2).這類節(jié)點(diǎn)在原始中一定既不是最大匹配的起始節(jié)點(diǎn)也不是最大匹配的終止節(jié)點(diǎn),因此如果要實(shí)現(xiàn)網(wǎng)絡(luò)完全能控,這類節(jié)點(diǎn)一定為驅(qū)動(dòng)節(jié)點(diǎn).

2.2 節(jié)點(diǎn)辨識(shí)算法

為了分析不同類型節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)可控性的影響,需要識(shí)別網(wǎng)絡(luò)中節(jié)點(diǎn)屬于哪一類型.因此,本節(jié)給出識(shí)別出網(wǎng)絡(luò)中節(jié)點(diǎn)類型的算法,算法流程如圖4所示.具體步驟如下:

圖4 算法流程圖Fig.4 Algorithm flow chart

步驟 1.通過(guò)Hopcroft-Karp 算法[32]識(shí)別二分圖網(wǎng)絡(luò)中的最大匹配組.

步驟 2.選擇節(jié)點(diǎn)集合中一個(gè)節(jié)點(diǎn),記為vi(i=1,2,···,N).N為集合中節(jié)點(diǎn)個(gè)數(shù).

步驟 3.判斷節(jié)點(diǎn)vi是否存在輸入邊和輸入邊.

步驟 4.若只存在輸入邊,則跳轉(zhuǎn)步驟5.若只存在輸出邊,則跳轉(zhuǎn)步驟6.若既存在輸出邊,又存在輸入邊,則跳轉(zhuǎn)步驟7.若既不存在輸出邊又不存在輸入邊,則節(jié)點(diǎn)類型為孤立節(jié)點(diǎn),跳轉(zhuǎn)步驟8.

步驟 5.節(jié)點(diǎn)輸入邊相連的節(jié)點(diǎn)為ui.去掉節(jié)點(diǎn)vi輸入邊,以深度優(yōu)先搜索算法觀察是否存在以節(jié)點(diǎn)ui為起點(diǎn)的增廣路徑,若存在,則節(jié)點(diǎn)vi為INM,若不存在,則節(jié)點(diǎn)vi為IM.

步驟 6.節(jié)點(diǎn)輸出邊相連的節(jié)點(diǎn)為wi.去掉節(jié)點(diǎn)vi輸出邊,以深度優(yōu)先搜索算法觀察是否存在以節(jié)點(diǎn)wi為終點(diǎn)的增廣路徑.若存在,則節(jié)點(diǎn)vi為ONM,若不存在,則節(jié)點(diǎn)vi為OM.

步驟 7.節(jié)點(diǎn)輸入邊相連的節(jié)點(diǎn)為xi.節(jié)點(diǎn)輸出邊相連的節(jié)點(diǎn)為yi.去掉節(jié)點(diǎn)vi輸入邊和輸出邊,以深度優(yōu)先搜索算法觀察是否存在以節(jié)點(diǎn)xi為起點(diǎn)和以節(jié)點(diǎn)yi為終點(diǎn)的增廣路徑.

若同時(shí)存在以節(jié)點(diǎn)xi為起點(diǎn)和以節(jié)點(diǎn)yi為終點(diǎn)的增廣路徑,則節(jié)點(diǎn)vi為INM&ONM.

若只存在以節(jié)點(diǎn)為起點(diǎn)xi的增廣路徑,不存在以節(jié)點(diǎn)yi為終點(diǎn)的增廣路徑.則節(jié)點(diǎn)vi為INM&OM.

若只存在以節(jié)點(diǎn)yi為終點(diǎn)的增廣路徑,不存在以節(jié)點(diǎn)xi為起點(diǎn)的增廣路徑.則節(jié)點(diǎn)vi為IM&ONM.

若同時(shí)不存在以節(jié)點(diǎn)xi為起點(diǎn)和以節(jié)點(diǎn)yi為終點(diǎn)的增廣路徑,則節(jié)點(diǎn)vi為IM&OM.

步驟 8.若i＜N,i=i+1,返回步驟2.反之結(jié)束操作.

算法偽代碼如下:

注 1.假設(shè)網(wǎng)絡(luò)中含有N個(gè)節(jié)點(diǎn)和L條邊.算法時(shí)間復(fù)雜度由以下兩個(gè)部分組成,第一部分是識(shí)別網(wǎng)絡(luò)二分圖的最大匹配;第二部分是通過(guò)深度優(yōu)先搜索算法尋找增廣路徑.由文獻(xiàn)[29]可知識(shí)別網(wǎng)絡(luò)二分圖最大匹配的時(shí)間復(fù)雜度為 O (N0.5L).通過(guò)深度優(yōu)先搜索算法尋找增廣路徑可能存在以下四種情況:

1)當(dāng)vi只含有輸入邊時(shí),與vi輸入邊相連的節(jié)點(diǎn)記為ui.去掉vi輸入邊,以深度優(yōu)先搜索算法識(shí)別是否存在以u(píng)i為起點(diǎn)的增廣路徑.使用一次深度優(yōu)先搜索算法,復(fù)雜度為 O (L).

2)當(dāng)vi只含有輸出邊時(shí),與vi輸出邊相連的節(jié)點(diǎn)記為wi.去掉vi輸出邊,以深度優(yōu)先搜索算法識(shí)別是否存在以wi為終點(diǎn)的增廣路徑.使用一次深度優(yōu)先搜索算法,復(fù)雜度為 O (L).

3)當(dāng)vi既含有輸入邊又含有輸出邊時(shí),與vi輸入邊相連節(jié)點(diǎn)記為xi,與vi輸出邊相連節(jié)點(diǎn)記為yi.去掉vi輸入邊與輸出邊,以深度優(yōu)先搜索算法識(shí)別是否存在以xi為起點(diǎn)或yi為終點(diǎn)的增廣路徑.使用一次深度優(yōu)先搜索算法,復(fù)雜度為 O (L).

4)當(dāng)vi既不含有輸入邊又不含有輸出邊時(shí),該節(jié)點(diǎn)類型為孤立節(jié)點(diǎn).無(wú)需深度搜索.

綜上可知,節(jié)點(diǎn)vi為上述這四種情況中之一,網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為N,尋找增廣路徑的復(fù)雜度最大為O(L).因最大匹配和尋找增廣路徑為并列關(guān)系,故該算法的最大復(fù)雜度為 O (N0.5L)+O(NL).

2.3 節(jié)點(diǎn)失效對(duì)能控性的影響

現(xiàn)實(shí)的復(fù)雜網(wǎng)絡(luò)在遭受攻擊或意外時(shí),網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)被破壞或故障失去原有功能,造成節(jié)點(diǎn)失效.不同類型的節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性有何影響?本節(jié)根據(jù)第2.1 節(jié)點(diǎn)分類的方式,給出了網(wǎng)絡(luò)節(jié)點(diǎn)失效時(shí),對(duì)網(wǎng)絡(luò)能控性和驅(qū)動(dòng)節(jié)點(diǎn)的影響情況.

定理 1.對(duì)于一個(gè)含有N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),當(dāng)某一個(gè)節(jié)點(diǎn)遭受攻擊失效時(shí),若失效節(jié)點(diǎn)為輸入完全匹配節(jié)點(diǎn)(IM)時(shí),網(wǎng)絡(luò)中驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持不變.若失效節(jié)點(diǎn)為輸入不完全匹配節(jié)點(diǎn)(INM)時(shí),網(wǎng)絡(luò)中驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).

證明.假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為N.網(wǎng)絡(luò)二分圖最大匹配中被匹配的節(jié)點(diǎn)個(gè)數(shù)為H個(gè).由式(3)可知驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)ND=N-H.當(dāng)網(wǎng)絡(luò)中輸入完全匹配節(jié)點(diǎn)失效時(shí),節(jié)點(diǎn)個(gè)數(shù)為N-1.由輸入完全匹配節(jié)點(diǎn)的定義可知,該節(jié)點(diǎn)在原始網(wǎng)絡(luò)中一定被其他節(jié)點(diǎn)的匹配.因此該節(jié)點(diǎn)失效后,網(wǎng)絡(luò)中被匹配節(jié)點(diǎn)個(gè)數(shù)變成H-1.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)=(N-1)-(H-1)=N-H=ND.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持不變.當(dāng)網(wǎng)絡(luò)中輸入不完全節(jié)點(diǎn)失效時(shí),節(jié)點(diǎn)個(gè)數(shù)為N-1.由輸入不完全匹配節(jié)點(diǎn)定義可以知,該節(jié)點(diǎn)在最大匹配中不一定被其他節(jié)點(diǎn)所匹配.因此該節(jié)點(diǎn)失效后,網(wǎng)絡(luò)最大匹配中被匹配節(jié)點(diǎn)個(gè)數(shù)保持不變?yōu)镠.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)=(N-1)-H=ND-1.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).□

定理 2.對(duì)于一個(gè)含有N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),當(dāng)一個(gè)節(jié)點(diǎn)遭受攻擊失效時(shí),若失效節(jié)點(diǎn)為輸出完全匹配節(jié)點(diǎn)(OM)時(shí),網(wǎng)絡(luò)中驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持不變.若失效節(jié)點(diǎn)為輸出不完全匹配節(jié)點(diǎn)(ONM)時(shí),驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).

證明.假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為N個(gè),被匹配節(jié)點(diǎn)個(gè)數(shù)為H個(gè).驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)ND=N-H.當(dāng)輸出完全匹配節(jié)點(diǎn)失效時(shí),節(jié)點(diǎn)個(gè)數(shù)為N-1.由輸出完全匹配節(jié)點(diǎn)定義可以該節(jié)點(diǎn)一定參與其他節(jié)點(diǎn)的匹配,因此當(dāng)該節(jié)點(diǎn)失效后,一定會(huì)造成某個(gè)與之連的節(jié)點(diǎn)變成未匹配節(jié)點(diǎn),因此失效后網(wǎng)絡(luò)中被匹配節(jié)點(diǎn)個(gè)數(shù)減少一個(gè),變成H-1.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)=(N-1)-(H-1)=N-H=ND.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持不變.當(dāng)輸出不完全匹配節(jié)點(diǎn)失效時(shí),節(jié)點(diǎn)個(gè)數(shù)為N-1.由輸出不完全匹配節(jié)點(diǎn)定義可知,該節(jié)點(diǎn)在最大匹配中不一定參與其他節(jié)點(diǎn)的匹配,因此當(dāng)該節(jié)點(diǎn)失效時(shí),網(wǎng)絡(luò)最大匹配中被匹配的節(jié)點(diǎn)個(gè)數(shù)保持不變?yōu)镠.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)=(N-1)-H=ND-1.驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).□

定理 3.對(duì)于一個(gè)含有N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),當(dāng)一個(gè)節(jié)點(diǎn)遭受攻擊失效時(shí),若失效的節(jié)點(diǎn)類型為IM&OM,網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)增加一個(gè).當(dāng)失效的節(jié)點(diǎn)類型為IM&ONM 或者INM&OM 時(shí),網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持不變.當(dāng)失效的節(jié)點(diǎn)類型為INM&ONM 時(shí),網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).

證明.網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為N,假設(shè)匹配節(jié)點(diǎn)個(gè)數(shù)為H.將包含輸出邊又包含輸入邊的節(jié)點(diǎn)分解為兩個(gè)節(jié)點(diǎn),一個(gè)只含有輸出邊,另一個(gè)只含有輸入邊.此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為N+1,這樣失效某個(gè)既包含輸出邊又包含輸入邊的節(jié)點(diǎn)等效為失效一個(gè)只包含輸出邊的節(jié)點(diǎn)和一個(gè)只包含輸入邊的節(jié)點(diǎn).將IM&OM 節(jié)點(diǎn)分解為IM 節(jié)點(diǎn)和OM 節(jié)點(diǎn),此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為N+1.失效IM&OM 節(jié)點(diǎn)等效為IM 節(jié)點(diǎn)和OM 節(jié)點(diǎn)失效,失效一個(gè)匹配起始節(jié)點(diǎn)和一個(gè)匹配終點(diǎn),匹配節(jié)點(diǎn)數(shù)少2.引理1可知=(N+1-2)-(H-2)=N-H+1=ND+1即驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)增加一個(gè);同理將IM&ONM 節(jié)點(diǎn)等效為IM 節(jié)點(diǎn)和ONM 節(jié)點(diǎn),INM&OM 節(jié)點(diǎn)等效為INM節(jié)點(diǎn)和OM節(jié)點(diǎn),失效一個(gè)匹配起點(diǎn)或一個(gè)匹配終點(diǎn),匹配節(jié)點(diǎn)數(shù)少1=(N+1-2)-(H-1)=N-H=ND;INM&ONM 節(jié)點(diǎn)等效為INM 節(jié)點(diǎn)和ONM 節(jié)點(diǎn),匹配節(jié)點(diǎn)數(shù)保持不變,=(N+1-2)-H=N-H-1=ND-1.即驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少一個(gè).□

注 2.由定理1,2,3 可以看出,當(dāng)失效節(jié)點(diǎn)為IM,OM,INM&OM,IM&ONM 節(jié)點(diǎn)時(shí),網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)不變,但網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)減少1,由式(4) 可知由nD=ND/(N-1)衡量能控性大小,所以網(wǎng)絡(luò)能控性略有減弱;當(dāng)失效節(jié)點(diǎn)為IM&OM 類型時(shí),網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)增加1,網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)減少1,由式(4)可知能控性nD=(ND+1)/(N-1),所以nD明顯變大,能控性有明顯減弱;當(dāng)失效節(jié)點(diǎn)為INM或ONM 或INM&ONM 類型時(shí),網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)減少1,網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)減少1,由式(4)可知能控性nD=(ND-1)/(N-1),所以nD明顯減小,能控性明顯增強(qiáng).

3 仿真實(shí)驗(yàn)

3.1 模型網(wǎng)絡(luò)

首先生成三種典型的網(wǎng)絡(luò)模型,即ER 隨機(jī)網(wǎng)絡(luò)模型[33],BA 無(wú)標(biāo)度網(wǎng)絡(luò)模型[34],WS 小世界網(wǎng)絡(luò)模型[35],其中生成ER 網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)N為500 個(gè),節(jié)點(diǎn)間連接概率為p=0.02;BA 網(wǎng)絡(luò)從初始點(diǎn)數(shù)是10 個(gè),邊數(shù)是8 的網(wǎng)絡(luò),每次引入一個(gè)新節(jié)點(diǎn)和4 條邊,按照度大的節(jié)點(diǎn)優(yōu)先連接的原則,生成節(jié)點(diǎn)數(shù)為500 的無(wú)標(biāo)度網(wǎng)絡(luò);WS 小世界網(wǎng)絡(luò),從500個(gè)節(jié)點(diǎn)近鄰邊數(shù)為4 的近鄰耦合網(wǎng)絡(luò),重連的概率為0.3,生成的小世界網(wǎng)絡(luò).采用2.2 節(jié)所述節(jié)點(diǎn)類型識(shí)別算法,得出三種網(wǎng)絡(luò)每種節(jié)點(diǎn)類型數(shù)量,如表1所示.由于該分類方式針對(duì)有向網(wǎng)絡(luò),因此在生成網(wǎng)絡(luò)模型時(shí),將節(jié)點(diǎn)之間無(wú)向連接關(guān)系變成單向有向連接,然后進(jìn)行仿真.

表1 模型網(wǎng)絡(luò)不同類型節(jié)點(diǎn)占比表Table 1 Proportion of different types of nodes in the model network

從表1 中可以看出,INM&ONM 類型的節(jié)點(diǎn)數(shù)量在BA 網(wǎng)絡(luò)和WS 網(wǎng)絡(luò)中較多,而IM&OM 節(jié)點(diǎn)在BA 網(wǎng)絡(luò)和WS 網(wǎng)絡(luò)中較少.因?yàn)锽A 網(wǎng)絡(luò)中新添加的節(jié)點(diǎn)傾向于連接節(jié)點(diǎn)度高的節(jié)點(diǎn),而WS 網(wǎng)絡(luò)具有較高的聚類系數(shù),因此這兩類網(wǎng)絡(luò)中大部分節(jié)點(diǎn)不一定是所有匹配邊集的起點(diǎn)和終點(diǎn),即不是固定與某個(gè)節(jié)點(diǎn)完成匹配.

為了驗(yàn)證每種類型節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)可控性的影響,對(duì)網(wǎng)絡(luò)中的每類節(jié)點(diǎn)進(jìn)行逐個(gè)隨機(jī)選則并刪除,然后計(jì)算網(wǎng)絡(luò)中驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)占比nD.由于網(wǎng)絡(luò)失效一個(gè)節(jié)點(diǎn)后,網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化,失效節(jié)點(diǎn)的鄰近節(jié)點(diǎn)類型也會(huì)變化,需要重新對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類,再隨機(jī)選取該類節(jié)點(diǎn)失效,計(jì)算nD.需要注意是網(wǎng)絡(luò)中不同類型節(jié)點(diǎn)個(gè)數(shù)不同,為了能夠有效對(duì)比,失效節(jié)點(diǎn)個(gè)數(shù)保持一致,失效節(jié)點(diǎn)的數(shù)量以數(shù)量最少的類型節(jié)點(diǎn)數(shù)量為準(zhǔn).

按照上述方法,在ER 網(wǎng)絡(luò)、BA 網(wǎng)絡(luò)和WS 網(wǎng)絡(luò)中逐個(gè)失效INM 節(jié)點(diǎn)、IM 節(jié)點(diǎn)、ONM 節(jié)點(diǎn)和OM 節(jié)點(diǎn)后網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)占總節(jié)點(diǎn)數(shù)的比例nD與失效節(jié)點(diǎn)數(shù)量占總節(jié)點(diǎn)數(shù)的比例f的關(guān)系如圖5、圖6 和圖7 所示.圖中可以看出INM 節(jié)點(diǎn)和ONM 節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少,nD值降低,隨著INM 節(jié)點(diǎn)和ONM 節(jié)點(diǎn)失效,網(wǎng)絡(luò)可控性增加,網(wǎng)絡(luò)的控制更加容易.相反IM 節(jié)點(diǎn)和OM 節(jié)點(diǎn)失效后,nD值略有增加.實(shí)際上,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)ND不變,但由于節(jié)點(diǎn)失效,節(jié)點(diǎn)總數(shù)減少,所以nD值呈現(xiàn)出略有增加的現(xiàn)象.對(duì)于一個(gè)大規(guī)模網(wǎng)絡(luò),節(jié)點(diǎn)數(shù)N很大時(shí),失效少量節(jié)點(diǎn)時(shí),驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)ND不變時(shí),可以近似認(rèn)為能控性nD不變.

圖6 BA 網(wǎng)絡(luò) VI 和 VO 失效可控性變化Fig.6 Controllability changes of VI and VO failure in BA networks

圖7 WS 網(wǎng)絡(luò) VI 和 VO 失效可控性變化Fig.7 Controllability changes of VI and VO failure in WS networks

ER 隨機(jī)網(wǎng)絡(luò)模型、BA 無(wú)標(biāo)度網(wǎng)絡(luò)模型和WS小世界網(wǎng)絡(luò)模型中INM&ONM 節(jié)點(diǎn)、INM&OM節(jié)點(diǎn)、IM&ONM 節(jié)點(diǎn)和IM&OM 節(jié)點(diǎn)失效后,網(wǎng)絡(luò)可控性nD隨失效節(jié)點(diǎn)個(gè)數(shù)占節(jié)點(diǎn)總數(shù)比例f變化情況如圖8、圖9 和圖10 所示.圖中可以看出,當(dāng)INM&ONM 節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少,nD值降低,網(wǎng)絡(luò)可控性增強(qiáng).當(dāng)INM&OM 節(jié)點(diǎn)和IM&ONM 節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)不變,但網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)減少,nD值略有增大,網(wǎng)絡(luò)可控性降低.當(dāng)IM&OM節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)增多,nD值增大明顯,網(wǎng)絡(luò)可控性顯著降低,網(wǎng)絡(luò)變得更難控制.

圖8 ER 網(wǎng)絡(luò) VIO 失效可控性變化Fig.8 Controllability changes of VIO f ailure in ER networks

圖9 BA 網(wǎng)絡(luò) VIO 失效可控性變化Fig.9 Controllability changes of VIO failure in BA networks

圖10 WS 網(wǎng)絡(luò) VIO 失效可控性變化Fig.10 Controllability changes of VIO failure in WS networks

3.2 真實(shí)網(wǎng)絡(luò)

下面應(yīng)用真實(shí)網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)類型及每種類型的分布情況進(jìn)行分析.選取了多種社交網(wǎng)絡(luò)[36],包括某公司經(jīng)理之間社交網(wǎng)絡(luò),某律所律師社交網(wǎng)絡(luò),某銀行員工間社交網(wǎng)絡(luò)和某學(xué)校學(xué)生間社交網(wǎng)絡(luò)等共7 個(gè)網(wǎng)絡(luò).在社交網(wǎng)絡(luò)中節(jié)點(diǎn)代表網(wǎng)絡(luò)中的個(gè)體(某個(gè)人),網(wǎng)絡(luò)的邊代表不同個(gè)體之間社交關(guān)系(交流或溝通).根據(jù)每個(gè)網(wǎng)絡(luò)的基本數(shù)據(jù)[36],采用本文第2.2 節(jié)點(diǎn)類型識(shí)別算法,得出每個(gè)網(wǎng)絡(luò)每種節(jié)點(diǎn)類型數(shù)量,如表2 所示.

在實(shí)際的社交網(wǎng)絡(luò)中INM 節(jié)點(diǎn)和IM 節(jié)點(diǎn)為存在輸入邊的節(jié)點(diǎn),可理解為從不主動(dòng)與他人交流溝通,被動(dòng)的接受他人的交流邀請(qǐng)的人;ONM 節(jié)點(diǎn)和OM 節(jié)點(diǎn)為存在輸出邊的節(jié)點(diǎn)在實(shí)際的社交網(wǎng)絡(luò)中可理解為能主動(dòng)的與他人交流溝通,從不被動(dòng)的接受他人的交流邀請(qǐng)的人.同理,INM&ONM、INM&OM、IM&ONM 和IM&OM 節(jié)點(diǎn)在實(shí)際社交網(wǎng)絡(luò)中可理解為即能主動(dòng)的與他人交流溝通又能被動(dòng)的接受他人的交流邀請(qǐng)的人;VD節(jié)點(diǎn)是即不能主動(dòng)的與他人交流溝通又不被動(dòng)的接受他人的交流邀請(qǐng)的人.表2 的數(shù)據(jù)表明,在社交網(wǎng)絡(luò)中,INM&ONM 節(jié)點(diǎn)占比較多,這類節(jié)點(diǎn)在節(jié)點(diǎn)最大匹配中特性為不是所有最大匹配邊集的起點(diǎn)和終點(diǎn),即不是一定參與其他節(jié)點(diǎn)的匹配,也不是一定被其他節(jié)點(diǎn)所匹配.這一現(xiàn)象對(duì)應(yīng)人在社交網(wǎng)絡(luò)中的交流與溝通不是固定不變的,即每個(gè)人會(huì)與多人產(chǎn)生交流和溝通.與實(shí)際中人際社交關(guān)系相符合.而INM 節(jié)點(diǎn)、IM 節(jié)點(diǎn)、ONM 節(jié)點(diǎn)和OM 節(jié)點(diǎn)等占比較少,這是由于這類節(jié)點(diǎn)在網(wǎng)絡(luò)最大匹配中是最大匹配邊集的起點(diǎn)或者終點(diǎn),即只參與其他節(jié)點(diǎn)匹配或者被匹配.這種現(xiàn)象對(duì)應(yīng)實(shí)際社交網(wǎng)絡(luò)中交流與溝通是單向的,這類情況在社交網(wǎng)絡(luò)中出現(xiàn)概率較少.

表2 實(shí)際網(wǎng)絡(luò)不同類型節(jié)點(diǎn)占比表Table 2 Proportion of different types of nodes in the actual network

考慮到網(wǎng)絡(luò)中節(jié)點(diǎn)類型的全面性,本文選取節(jié)點(diǎn)數(shù)量相對(duì)較多的學(xué)生社交網(wǎng)絡(luò)(1)和學(xué)生社交網(wǎng)絡(luò)(2)分析節(jié)點(diǎn)失效后對(duì)網(wǎng)絡(luò)能控性的影響.為了有效對(duì)比,選取節(jié)點(diǎn)數(shù)量較多的INM&ONM 類型節(jié)點(diǎn)、INM&OM 類型節(jié)點(diǎn),且每種類型失效節(jié)點(diǎn)數(shù)量保持相同.節(jié)點(diǎn)失效后網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)占比nD與失效節(jié)點(diǎn)個(gè)數(shù)占比f(wàn)的關(guān)系如圖11 所示.

圖11 社交網(wǎng)絡(luò)節(jié)點(diǎn)失效能控性變化Fig.11 Controllability changes of node failure in social networks

圖中可以看出,當(dāng)INM&ONM 節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)減少,nD值降低,網(wǎng)絡(luò)可控性增強(qiáng).當(dāng)INM&OM 節(jié)點(diǎn)失效后,驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)不變,但網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)減少,nD值略有增大,網(wǎng)絡(luò)可控性降低.能控性的變化規(guī)律與仿真效果與模型網(wǎng)絡(luò)一致.

4 結(jié)論

本文針對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)失效問(wèn)題,根據(jù)節(jié)點(diǎn)相連邊的方向和最大匹配關(guān)系,將網(wǎng)絡(luò)節(jié)點(diǎn)分成九種類型,并給出辨識(shí)節(jié)點(diǎn)類型的算法.分析了不同類型節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性的影響,得出不同類型節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)的不同影響,當(dāng)INM、ONM 和INM&ONM 類型節(jié)點(diǎn)失效時(shí),驅(qū)動(dòng)節(jié)點(diǎn)數(shù)減少1,網(wǎng)絡(luò)能控性增強(qiáng);當(dāng)IM、OM、INM&OM和IM&ONM 類型節(jié)點(diǎn)失效時(shí),驅(qū)動(dòng)節(jié)點(diǎn)數(shù)不變,網(wǎng)絡(luò)可控性略有降低,此類型節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)能控性的影響較小,當(dāng)網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)N較大時(shí),能控性基本不變;當(dāng)IM&OM 類型節(jié)點(diǎn)失效時(shí),驅(qū)動(dòng)節(jié)點(diǎn)個(gè)數(shù)增加1,網(wǎng)絡(luò)能控性明顯降低,此類型節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)能控性的影響較大.