基于復雜網絡核心體的控制方法

王媛媛，袁正中,2，趙 琛

（1.閩南師范大學數學與統計學院，福建漳州363000；2.數據科學與統計福建省高校重點實驗室，福建漳州363000；3.河北師范大學計算機與網絡空間安全學院，河北石家莊050024）

生活中隨處可見的生物網絡[1]、交通網絡[2]、社會網絡[3]、信息網絡[4]等都稱為復雜網絡.它們不僅擁有超大的網絡規模，而且包含豐富的結構特性[5]和動力學特性，如同步、涌現等[6-8].目前，研究人員在復雜網絡的傳播[9]、搜索[10]、同步[11-12]、控制[13]等方面已經取得了非常重要的成果.然而，網絡的復雜性仍然給這些領域的研究工作帶來了諸多挑戰[14].其中，復雜網絡乃至各種復雜系統是否可控、如何精確控制等問題已成為非常關鍵且擁有廣泛應用價值的問題.

2011年，Liu等[15]首次從線性系統的角度研究復雜網絡的結構可控問題，利用Kalman可控理論[16]證明了網絡最大匹配中的未匹配節點是使網絡可控的驅動節點.但該理論只適用于邊權可獨立選取的有向網絡，在無向復雜網絡或給定權重的網絡下不適用.隨后，Yuan等[17]從鄰接矩陣特征值的角度提出了嚴格可控理論，指出驅動節點數等于對應系統的鄰接矩陣特征值的最大幾何重數，并且通過對矩陣進行初等變換可以得到具體的驅動節點.特別地，對于稀疏網絡，網絡的驅動節點數由鄰接矩陣的秩決定.然而，復雜網絡系統包含成千上萬的節點，直接用初等變換的方法尋找控制網絡的驅動節點無疑是困難的.

因此，研究者們開始嘗試通過節點較少的網絡核心去控制整個網絡[18-19].特別地，文獻[19]利用葉子刪除法獲得復雜網絡的控制核心體，基于PΒH 可控條件證明了對于大部分的網絡，控制網絡核心體即可完成對整個網絡的控制.然而，對于一些網絡，僅通過對其核心體實施控制，不能完成對整個網絡的控制.

本文基于PΒH 可控理論，針對上述復雜網絡實際控制中核心體可控但網絡本身不可控的問題，提出兩種復雜網絡可控方案.一是嘗試其它使核心體可控的驅動節點組；二是增加新的驅動節點.推廣到一般情形，提出并論證在控制核心體的基礎上，對每次刪除葉子中度為1 的節點增加控制可以使原始網絡可控.最后，重點分析了核心體加鏈路的網絡，證明增加對該鏈中度為1 的節點的控制可以使整個網絡可控.

1 復雜網絡可控的基本概念

復雜網絡可控是指系統在一定的時間內，經過適當的外界輸入作用，從任意初始狀態變成最終狀態的性質.考慮以下含有N個節點的無向網絡動力學系統[15,17]：

其中x=(x1,x2,…,xN)T表示N個節點的狀態.A=(aij)∈R N× N為系統的鄰接矩陣，其中，aij=aji=1 (i≠j)表示節點i、j之間存在連接；否則aij=0 (包括i=j).B∈R N×M為列滿秩的輸入矩陣，其中B的列數表示需要獨立控制的節點個數.若B不是列滿秩矩陣，則說明整個控制系統有多余的控制輸入，可以進一步簡化[17].向量u=(u1,u2,…,uM)T為M個獨立的控制輸入.式(1)可控的充要條件為以下PΒH 可控條件成立[20]：

其中λ為矩陣A對應的特征值，IN為N階單位矩陣.

對于含有葉子的稀疏無向復雜網絡，持續地刪除網絡葉子及其連邊并保留孤立節點，直至整個網絡不再包含度為1 的節點，最終得到的所有連通集團和孤立節點共同構成網絡的控制核心體[19].其中，葉子是指由一度節點、鄰居和它們之間的連接構成的結構.

2 主要結果

對于大部分的復雜網絡，僅對其核心體實施控制即可實現對整個網絡的控制，我們稱為可由核心體控制的網絡.反之，核心體可控而整個網絡不可控，稱為不可由核心體控制的網絡.下面，我們將針對3 種不可由核心體控制的網絡展開討論.

2.1 一種不可由核心體控制的網絡

對于含有N個節點的無向網絡，如圖1a)所示，前N-2 個節點圍成一個環，且節點1 分別與節點2、…、節點N-2 相連，節點N-4 連接一個葉子，經過葉子刪除后得到核心體A0(虛線圈起部分).對節點1、2 施加控制，利用PΒH可控條件可知，此時核心體可控(見圖1b)).

圖1 不可由核心體控制的網絡的控制情況Fig.1 The control situation of the network that cannot be controlled by the core

于是

其中

Wind-Solar Complementary Energy Supply Platform Based on Intelligent Beacon

下面分析在該控制輸入下，整個網絡的可控性.此時的控制輸入矩陣記為B.

將矩陣(λIN-A,B)進行一系列的初等變換化為階梯矩陣如下：

可見，在最后一個矩陣中，除第N-1行之外其余行的非零元素均在不同行不同列.因此，這些行向量是線性無關的.又因為A滿足因此-1 是矩陣A的一個特征值.此時，矩陣(-IN-A,B)第N- 1 行的非零元素均可經過一些初等行變換化為零元素.說明rank(-IN-A,B) =N- 1 ＜N恒成立，由PΒH 可控條件可知，在控制節點1，2 的情況下，原始網絡不可控.

對于這種不可由核心體控制的網絡，可以使用如下兩種替代控制方案：

1)更換驅動節點的組合

由于控制核心體的驅動節點不止一組，可以尋找其它驅動節點的組合并驗證其可控性.否則，考慮方法二.對于圖1a)所示的網絡，分別在節點N- 4的兩側各取一個節點，如選取節點2 和節點N- 2，此時新的控制輸入矩陣記為B1，通過計算驗證可知rank(λIN-A,B1)=N，說明原始網絡可控(見圖1c)).

這種方法通常適用于節點較少的網絡.對于節點比較多、連接復雜的網絡，尋找其它驅動節點的組合并不容易，即使可以找到所有驅動節點的組合，但數量過多，驗證可控條件的計算量也相應增加.

2）在原有的使核心體可控的控制輸入下增加新的驅動節點.對于圖1b)所示的網絡，在原有兩個驅動節點的情況下增加一個新的驅動節點.這里可增加節點N- 3、節點N- 2、節點N- 1或節點N，更新的控制輸入矩陣B分別如下：

2.2 一般不可由核心體控制的網絡

定理1對于任意不可由核心體控制的網絡，在核心體可控的基礎上，對每次刪除中度為1 的節點增加控制，則原始網絡完全可控.

證明不妨以一次刪除為例，設包含一個度為1的節點的網絡為：

其中，1表示一度節點與其鄰居的連接，向量α表示刪去的葉子與其余節點的連接情況.矩陣A0表示刪除一個葉子后得到的網絡.假設A0可以由B0控制，由PΒH可控條件滿足：

在核心體可控的基礎上，再增加對度為1的節點的控制，得到新的輸入矩陣B如下：

因此

由PΒH 可控條件可知整個網絡可控.于是，在核心體可控的前提下，對每次刪除時度為1的節點增加控制，原始網絡完全可控.

在圖2 所示的網絡中，節點1、2、3、8 和它們之間的連邊構成核心體（虛線部分）.可以驗證，控制節點1、2 和8 后，核心體可控，但整個網絡不可控.根據定理1，增加控制每次刪除中度為1 的節點12，10，7 和5（箭頭表示），整個網絡可控.

圖2 增加對每次刪除中度為1的節點的控制使網絡可控Fig.2 Add control to the once-deleted node every time,the network is controllable

在已有的控制方法[19]中，需要依次驗證每次刪除后的鄰接矩陣的相關條件是否滿足.而定理1免去了大量的計算過程，提供了基于核心體控制網絡的一般思路.在實際應用時，每次刪除都要增加相應的控制.但在節點較多的網絡中，控制輸入成本就比較高.因此，對于一類特殊的不可控網絡——由核心體和鏈路組成的無向復雜網絡，可以在定理1 的基礎上進行推廣，將對每次刪除中度為1的節點的控制進一步縮減為對整條鏈路中度為1的節點的控制，從而大大減少控制輸入成本.

2.3 一類特殊的不可由核心體控制的網絡

定理2對于任意的由核心體和一條連接核心體的鏈路構成的網絡，若僅控制核心體不能控制整個網絡.那么，在核心體可控的基礎上，僅增加對鏈路的控制，則原始網絡完全可控.

證明不妨設由核心體和一條鏈路構成的網絡A有如下形式，且增加對度為1的節點的控制，則

其中，設鏈路含m個節點，核心體仍記為A0，設A0有n 個節點且可以由輸入矩陣B0控制.則由PΒH 可控條件滿足：

對于原始網絡A有

顯然，rank(λIN-A,B)=n+m=N，由PΒH可控條件，原始網絡完全可控.

上述分析說明在核心體可控的基礎上，對鏈路中度為1 的節點增加控制，整個網絡完全可控.該思路可以不必控制每次刪除中度為1 的節點，一定程度上減少了控制輸入成本.進一步地，該理論同樣適用于核心體加多條鏈路的情形.

定理3對于任意由核心體和多條獨立鏈路構成的網絡，若控制核心體不能控制整個網絡.那么，在核心體可控的基礎上，增加對每條鏈路中度為1的節點的控制，則原始網絡可控.

證明同定理2.

圖3a)所示的網絡包含核心體（虛線圈起部分）和一條鏈路.在核心體可控的基礎上，僅對該鏈中度為

圖3 增加對每條鏈路中度為1的節點的控制使網絡可控Fig.3 Add control to the one-degree nodes in each link,and the network is controllable

3 結束語

本文研究了核心體可控，但整體不可控的網絡控制問題.首先，得到了控制一類特殊網絡的方法：更換驅動節點組合或者增加適當驅動節點使網絡可控.其次，提出更一般化控制方法：除了原有的對核心體的控制，對網絡中每次刪除中度為1 的節點增加控制可以使整個網絡達到可控狀態.最后，重點分析了核心體加鏈路的網絡的控制方法.除了原有的對核心體的控制，對鏈路中度為1的節點增加控制即可使整個網絡可控.這一發現極大地減少了需要增加的驅動節點，提高了控制效率.該研究對于那些由可控網絡擴充得到的新網絡的控制有著重要意義.1的節點增加控制（灰色箭頭表示），此時整個網絡可控.圖3b)所示的網絡包含了核心體和多條鏈路.在核心體可控的基礎上，對每一條鏈路中度為1的節點增加控制（灰色箭頭表示），此時整個網絡可控.