基于大規模網絡的結構能控性指數算法*

東華大學信息科學與技術學院 曾濤 李曉麗

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

現代網絡科學中最具挑戰性的問題之一是對復雜網絡的控制。由于復雜網絡具有高維度、非線性等特征，許多研究人員致力于了解復雜網絡的結構以及節點間的相互作用，但是目前還有特定的框架來解決網絡拓撲結構和非線性動力學之間的極其復雜的相互作用問題，因此復雜網絡的控制依舊是一個復雜的問題。

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

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

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

1 理論基礎

1.1 能控性指數K

(A,B)

是一個擁有N個狀態節點和M個控制輸入的時不變網絡系統：

其中

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

表示t時間下的狀態向量，A是N×N維系統矩陣，用來描述各個節點之間的連接關系和連接強度。B是N×M維輸入矩陣，用于描述N個狀態節點和M個控制輸入之間的連接關系。若忽略網絡邊的權值，用“×”代表非零向量，此時的矩陣稱為該系統的結構矩陣。引理:（

Kalman

秩判據）：系統（

1

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

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

滿足：

rank(C)=N

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

C

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

C

在

(K+1)M

列時就已經滿秩了。因此我們可以得到一個

N×(K+1)M

矩陣

Q

，并且

Q

滿足：

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

。

由此我們可以推導出能控性指數的概念。

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

K

稱為該系統的能控性指數。

1.2 結構能控性指數K

顯然，這里的K≤N，表示結構能控性指數K不超過N。結構能控性指數K的物理意義表示從網絡系統的控制節點出發通過K次的信息傳遞可以影響到所有節點，即網絡達到可控狀態。

2 基于控制鏈的結構能控性指數

如圖1所示的結構我們稱為控制鏈，也稱之為路徑，控制鏈是可控的，且從控制鏈的結構很容易看出控制鏈的結構能控性指數K為控制鏈總節點的數量減1。如圖1所示的控制鏈有4個狀態節點，所以其結構能控性指數為3。

圖1 控制鏈Fig.1 Control chain

若一個有N個節點的系統(A,B)對應的結構為控制鏈且控制鏈可控，那么該控制鏈的系統矩陣A和控制矩陣B可以表示為：

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

3 Knode算法

由上文可知控制鏈是可控的且結構能控性指數為N-1，同時，稀疏網絡和稀疏的節點是容易控制的，對于一個密集網絡或者復雜網絡，可以考慮將其不斷的簡化。因此該算法的最終目的是將復雜的有向網絡分解成若干條控制鏈，網絡的驅動節點集為所有控制鏈根節點的集合，整個網絡的結構能控性指數為最長控制鏈的能控性指數。

對控制鏈結構來說，根節點的入度為0，出度為1，我們將所有入度為0的節點作為驅動節點；控制鏈末端的節點入度為1，出度為0，所以，出度為0的節點當做末端節點；其余節點的入度和出度都為1，且控制鏈所有節點的入度和出度都不超過1。因此，對復雜網絡進行分解時可以參考這個規律，對入度或者出度大于1的節點進行邊刪除，在此基礎上通過尋找最短路徑來限制控制鏈的長短，使得網絡的結構能控性指數不至于過大。本文提出基于節點度的網絡分解算法步驟如下：

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

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

步驟3：將步驟2中找出的最短鏈路L進行保留，刪除其他一步可達L的鏈路和L（除節點v外）可達其他節點的鏈路。

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

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

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

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

4 仿真結果分析

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

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

表1 ER隨機網絡仿真結果Tab.1 Simulation results for ER random networks

表2 真實網絡數據集仿真結果Tab.2 Simulation results for real networks

5 結論

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