基于大規(guī)模網(wǎng)絡(luò)的結(jié)構(gòu)能控性指數(shù)算法*

東華大學(xué)信息科學(xué)與技術(shù)學(xué)院 曾濤 李曉麗

傳統(tǒng)的網(wǎng)絡(luò)能控性是在給定輸入下通過能控性判據(jù)來判斷該網(wǎng)絡(luò)是否可控，或是尋找使有向網(wǎng)絡(luò)達(dá)到可控時的最少驅(qū)動節(jié)點集。為了研究網(wǎng)絡(luò)達(dá)到可控時的鏈路長度，對于一個沒有給定輸入的有向網(wǎng)絡(luò)，本文通過對節(jié)點度的研究和刪除邊等操作將有向網(wǎng)絡(luò)分解成多條控制鏈，將控制鏈的根節(jié)點作為整個網(wǎng)絡(luò)的驅(qū)動節(jié)點集。同時引入能控性指數(shù)的概念，對控制鏈長度進(jìn)行研究。最后基于節(jié)點的度提出了一個算法將有向網(wǎng)絡(luò)分解成獨立可控的控制鏈,得出網(wǎng)絡(luò)的驅(qū)動節(jié)點集和結(jié)構(gòu)能控性指數(shù)，通過對大規(guī)模隨機(jī)網(wǎng)絡(luò)和真實網(wǎng)絡(luò)的仿真，驗證了算法的有效性。

現(xiàn)代網(wǎng)絡(luò)科學(xué)中最具挑戰(zhàn)性的問題之一是對復(fù)雜網(wǎng)絡(luò)的控制。由于復(fù)雜網(wǎng)絡(luò)具有高維度、非線性等特征，許多研究人員致力于了解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)以及節(jié)點間的相互作用，但是目前還有特定的框架來解決網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和非線性動力學(xué)之間的極其復(fù)雜的相互作用問題，因此復(fù)雜網(wǎng)絡(luò)的控制依舊是一個復(fù)雜的問題。

Liu等人作出了開創(chuàng)性的貢獻(xiàn)。提出了最小輸入定理來有效地表征有向網(wǎng)絡(luò)的結(jié)構(gòu)可控性，通過識別最少驅(qū)動節(jié)點集以實現(xiàn)網(wǎng)絡(luò)的完全控制。在此基礎(chǔ)上將有向網(wǎng)絡(luò)的結(jié)構(gòu)可控性映射到最大匹配的問題上，通過給不匹配的控制節(jié)點施加控制使網(wǎng)絡(luò)可控。但是，最大匹配并不是唯一的，所以在最大匹配的基礎(chǔ)上提出了一個算法用于查找所有可能的輸入節(jié)點使復(fù)雜網(wǎng)絡(luò)可控。開發(fā)了一個精確的可控制性框架以替代結(jié)構(gòu)可控制性框架，它提供了一種通用工具來處理具有任意結(jié)構(gòu)和鏈接權(quán)重的復(fù)雜網(wǎng)絡(luò)的可控制性，包括有向，無向，加權(quán)和無權(quán)網(wǎng)絡(luò)自循環(huán)。結(jié)構(gòu)可控性可以通過精確的結(jié)構(gòu)矩陣框架來再現(xiàn)。通過為定向鏈接分配隨機(jī)權(quán)重來確保結(jié)構(gòu)可控性，證明了獨立的驅(qū)動節(jié)點或外部控制器的最小數(shù)量等于網(wǎng)絡(luò)矩陣所有特征值的最大幾何重數(shù)。

在復(fù)雜網(wǎng)絡(luò)中，節(jié)點也是至關(guān)重要的存在，很多研究表明驅(qū)動節(jié)點的選取與度的分布存在關(guān)系。發(fā)現(xiàn)驅(qū)動節(jié)點的數(shù)量主要由網(wǎng)絡(luò)的度分布決定，對于密集的網(wǎng)絡(luò)往往只需要幾個控制節(jié)點，相反最難控制的是稀疏的不均勻網(wǎng)絡(luò)，并且驅(qū)動節(jié)點的選取往往都避開高階節(jié)點。根據(jù)每個節(jié)點在網(wǎng)絡(luò)中的作用對節(jié)點進(jìn)行了分類，將節(jié)點分為了關(guān)鍵節(jié)點，間歇性節(jié)點和冗余節(jié)點并開發(fā)了一個分析框架來識別每個節(jié)點的類別，從而發(fā)現(xiàn)復(fù)雜系統(tǒng)中兩種不同的控制模式：集中控制與分布式控制。早在1974年，lin提出了“仙人掌”結(jié)構(gòu)模型，并且提出“擴(kuò)張”這一概念，指出節(jié)點和邊的擴(kuò)張會使網(wǎng)絡(luò)變得不可控。網(wǎng)絡(luò)中最重要的結(jié)構(gòu)是連接節(jié)點和邊的位置，它們確定系統(tǒng)的哪些部分在受到外部控制信號的影響時可以最終控制整個網(wǎng)絡(luò)的行為，擴(kuò)張是網(wǎng)絡(luò)中產(chǎn)生控制輸入需求的擴(kuò)展點，通過擴(kuò)張能夠清楚地了解哪些節(jié)點是替代選擇以及這些替代選擇如何在整個網(wǎng)絡(luò)中相互關(guān)聯(lián)。

研究復(fù)雜網(wǎng)絡(luò)時，對節(jié)點和邊的思考是非常重要的，本文研究的重點是，對于一個給定的有向網(wǎng)絡(luò)，由于密集網(wǎng)絡(luò)不容易控制，稀疏的網(wǎng)絡(luò)更容易控制。因此，通過對節(jié)點度的選取和邊的刪除將網(wǎng)絡(luò)分解成多條控制鏈，通過選取控制鏈的根節(jié)點得出驅(qū)動節(jié)點集。同時結(jié)合結(jié)構(gòu)能控性指數(shù)K的概念，對控制鏈的長度進(jìn)行研究。

1 理論基礎(chǔ)

1.1 能控性指數(shù)K

(A,B)

是一個擁有N個狀態(tài)節(jié)點和M個控制輸入的時不變網(wǎng)絡(luò)系統(tǒng)：

其中

x(t)=(x(t),x(t),...,x(t))

表示t時間下的狀態(tài)向量，A是N×N維系統(tǒng)矩陣，用來描述各個節(jié)點之間的連接關(guān)系和連接強度。B是N×M維輸入矩陣，用于描述N個狀態(tài)節(jié)點和M個控制輸入之間的連接關(guān)系。若忽略網(wǎng)絡(luò)邊的權(quán)值，用“×”代表非零向量，此時的矩陣稱為該系統(tǒng)的結(jié)構(gòu)矩陣。引理:（

Kalman

秩判據(jù)）：系統(tǒng)（

1

）完全可控的充分必要條件為系統(tǒng)的能控性判別矩陣：

C=[B,AB,...,AB,AB,...,AB]

滿足：

rank(C)=N

但是，由于能控性判別矩陣

C

不是每列都是線性無關(guān)的，可能存在某些列線性相關(guān)，使得能控性判別矩陣

C

在

(K+1)M

列時就已經(jīng)滿秩了。因此我們可以得到一個

N×(K+1)M

矩陣

Q

，并且

Q

滿足：

Q=[B,AB,...,AB]

。

由此我們可以推導(dǎo)出能控性指數(shù)的概念。

定義：若系統(tǒng)(1)滿足(2)和(3)這兩種情況時，這里的

K

稱為該系統(tǒng)的能控性指數(shù)。

1.2 結(jié)構(gòu)能控性指數(shù)K

顯然，這里的K≤N，表示結(jié)構(gòu)能控性指數(shù)K不超過N。結(jié)構(gòu)能控性指數(shù)K的物理意義表示從網(wǎng)絡(luò)系統(tǒng)的控制節(jié)點出發(fā)通過K次的信息傳遞可以影響到所有節(jié)點，即網(wǎng)絡(luò)達(dá)到可控狀態(tài)。

2 基于控制鏈的結(jié)構(gòu)能控性指數(shù)

如圖1所示的結(jié)構(gòu)我們稱為控制鏈，也稱之為路徑，控制鏈?zhǔn)强煽氐模覐目刂奇湹慕Y(jié)構(gòu)很容易看出控制鏈的結(jié)構(gòu)能控性指數(shù)K為控制鏈總節(jié)點的數(shù)量減1。如圖1所示的控制鏈有4個狀態(tài)節(jié)點，所以其結(jié)構(gòu)能控性指數(shù)為3。

圖1 控制鏈Fig.1 Control chain

若一個有N個節(jié)點的系統(tǒng)(A,B)對應(yīng)的結(jié)構(gòu)為控制鏈且控制鏈可控，那么該控制鏈的系統(tǒng)矩陣A和控制矩陣B可以表示為：

矩陣中非零元素“×”表示節(jié)點之間的連接關(guān)系和強度。顯然，系統(tǒng)(A,B)的能控性指數(shù)為N-1，且滿足式子：

3 Knode算法

由上文可知控制鏈?zhǔn)强煽氐那医Y(jié)構(gòu)能控性指數(shù)為N-1，同時，稀疏網(wǎng)絡(luò)和稀疏的節(jié)點是容易控制的，對于一個密集網(wǎng)絡(luò)或者復(fù)雜網(wǎng)絡(luò)，可以考慮將其不斷的簡化。因此該算法的最終目的是將復(fù)雜的有向網(wǎng)絡(luò)分解成若干條控制鏈，網(wǎng)絡(luò)的驅(qū)動節(jié)點集為所有控制鏈根節(jié)點的集合，整個網(wǎng)絡(luò)的結(jié)構(gòu)能控性指數(shù)為最長控制鏈的能控性指數(shù)。

對控制鏈結(jié)構(gòu)來說，根節(jié)點的入度為0，出度為1，我們將所有入度為0的節(jié)點作為驅(qū)動節(jié)點；控制鏈末端的節(jié)點入度為1，出度為0，所以，出度為0的節(jié)點當(dāng)做末端節(jié)點；其余節(jié)點的入度和出度都為1，且控制鏈所有節(jié)點的入度和出度都不超過1。因此，對復(fù)雜網(wǎng)絡(luò)進(jìn)行分解時可以參考這個規(guī)律，對入度或者出度大于1的節(jié)點進(jìn)行邊刪除，在此基礎(chǔ)上通過尋找最短路徑來限制控制鏈的長短，使得網(wǎng)絡(luò)的結(jié)構(gòu)能控性指數(shù)不至于過大。本文提出基于節(jié)點度的網(wǎng)絡(luò)分解算法步驟如下：

步驟1：初始化集合S={}，將網(wǎng)絡(luò)中節(jié)點入度大于等于2的節(jié)點記為v(0≤i≤N)，將v存入集合S。

步驟2：隨機(jī)選取S中節(jié)點v進(jìn)行回溯，回溯至入度為零的節(jié)點為止，選取其中路徑最短的一條鏈路，記為L。若最短的鏈路不止一條，則隨機(jī)選取一條。

步驟3：將步驟2中找出的最短鏈路L進(jìn)行保留，刪除其他一步可達(dá)L的鏈路和L（除節(jié)點v外）可達(dá)其他節(jié)點的鏈路。

步驟4：遍歷集合S中所有入度大于等于2的節(jié)點直到不存在入度大于2的節(jié)點為止。

步驟5：初始化集合S={}，將網(wǎng)絡(luò)中節(jié)點出度大于等于2的節(jié)點記為o(0≤i≤N)，將o存入集合S。

步驟6：隨機(jī)選取S中節(jié)點o向下尋找至出度為零的節(jié)點為止，選取其中路徑最短的一條鏈路同時刪除與該鏈路無關(guān)的其他鏈路。

步驟7：遍歷集合S中所有出度大于等于2的節(jié)點直到不存在出度大于2的節(jié)點為止。

4 仿真結(jié)果分析

利用本文提供的算法對大規(guī)模ER隨機(jī)網(wǎng)絡(luò)進(jìn)行仿真，表1為仿真結(jié)果。N為網(wǎng)絡(luò)節(jié)點的個數(shù)，L為網(wǎng)絡(luò)的邊的總數(shù)，為ER隨機(jī)網(wǎng)絡(luò)的平均度。令n=N/N來表示網(wǎng)絡(luò)系統(tǒng)的控制輸入情況，nm為最大匹配算法下得到的值，nn為文本提供的算法下得到的值。K是最大匹配算法下的結(jié)構(gòu)能控性指數(shù)K值（控制鏈路的最大長度），K為本文算法下的結(jié)構(gòu)能控性指數(shù)K值。真實網(wǎng)絡(luò)數(shù)據(jù)集仿真結(jié)果如表2所示。

通過表1可以看出，本文提供的算法和最大匹配算法擁有相同的最少驅(qū)動節(jié)點使得網(wǎng)絡(luò)的結(jié)構(gòu)能控性指數(shù)K，本文算法的優(yōu)勢在于，在相同網(wǎng)絡(luò)和相同的驅(qū)動節(jié)點下，本文提供的算法擁有更小的結(jié)構(gòu)能控性指數(shù)K值，即控制鏈路相對更短，控制速度更快。同時，針對不同規(guī)模的隨機(jī)網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)的平均度值相差不大時，n的值變化不大。說明最小控制輸入與網(wǎng)絡(luò)的平均度相關(guān)。表2針對不同的真實網(wǎng)絡(luò)進(jìn)行了仿真，所有的真實網(wǎng)絡(luò)數(shù)據(jù)集來源于文獻(xiàn)，對于表格中的網(wǎng)絡(luò)基本信息，其中Type表示網(wǎng)絡(luò)的類型，Name為網(wǎng)絡(luò)的名稱，其他數(shù)據(jù)與表1保持一致。從表2可以看出，對于真實網(wǎng)絡(luò)，算法擁有和最大匹配算法一樣的最少驅(qū)動節(jié)點，網(wǎng)絡(luò)可控時的結(jié)構(gòu)能控性指數(shù)K值更小。同時可以看出網(wǎng)絡(luò)平均度相差較大時n的值差距也較大，驗證了網(wǎng)絡(luò)的平均度影響網(wǎng)絡(luò)的最小控制輸入，通過仿真結(jié)果驗證了算法的可行性，為真實網(wǎng)絡(luò)驅(qū)動節(jié)點的選取和控制性能研究提供了一定的參考價值。

表1 ER隨機(jī)網(wǎng)絡(luò)仿真結(jié)果Tab.1 Simulation results for ER random networks

表2 真實網(wǎng)絡(luò)數(shù)據(jù)集仿真結(jié)果Tab.2 Simulation results for real networks

5 結(jié)論

本文通過對節(jié)點度以及結(jié)構(gòu)能控性指數(shù)的思考，將有向網(wǎng)絡(luò)分解為能控的控制鏈結(jié)構(gòu)，把分解后的控制鏈的根節(jié)點作為驅(qū)動節(jié)點，所以復(fù)雜網(wǎng)絡(luò)的驅(qū)動節(jié)點集就是分解后控制鏈根節(jié)點的集合，并且很容易看出可控時網(wǎng)絡(luò)內(nèi)部的連接情況。再結(jié)合結(jié)構(gòu)能控性指數(shù)K對控制鏈的長度進(jìn)行了討論，得出了最長控制鏈的能控性指數(shù)就是該網(wǎng)絡(luò)的結(jié)構(gòu)能控性指數(shù)。最后，提出了一個將網(wǎng)絡(luò)分解為控制鏈的算法，通過對大規(guī)模隨機(jī)網(wǎng)絡(luò)和真實網(wǎng)絡(luò)的仿真驗證了該算法的有效性，為實際網(wǎng)絡(luò)驅(qū)動節(jié)點的選取提供了參考。