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

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建漳州363000；2.數(shù)據(jù)科學(xué)與統(tǒng)計(jì)福建省高校重點(diǎn)實(shí)驗(yàn)室，福建漳州363000；3.河北師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，河北石家莊050024）

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

2011年，Liu等[15]首次從線性系統(tǒng)的角度研究復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)可控問(wèn)題，利用Kalman可控理論[16]證明了網(wǎng)絡(luò)最大匹配中的未匹配節(jié)點(diǎn)是使網(wǎng)絡(luò)可控的驅(qū)動(dòng)節(jié)點(diǎn).但該理論只適用于邊權(quán)可獨(dú)立選取的有向網(wǎng)絡(luò)，在無(wú)向復(fù)雜網(wǎng)絡(luò)或給定權(quán)重的網(wǎng)絡(luò)下不適用.隨后，Yuan等[17]從鄰接矩陣特征值的角度提出了嚴(yán)格可控理論，指出驅(qū)動(dòng)節(jié)點(diǎn)數(shù)等于對(duì)應(yīng)系統(tǒng)的鄰接矩陣特征值的最大幾何重?cái)?shù)，并且通過(guò)對(duì)矩陣進(jìn)行初等變換可以得到具體的驅(qū)動(dòng)節(jié)點(diǎn).特別地，對(duì)于稀疏網(wǎng)絡(luò)，網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)由鄰接矩陣的秩決定.然而，復(fù)雜網(wǎng)絡(luò)系統(tǒng)包含成千上萬(wàn)的節(jié)點(diǎn)，直接用初等變換的方法尋找控制網(wǎng)絡(luò)的驅(qū)動(dòng)節(jié)點(diǎn)無(wú)疑是困難的.

因此，研究者們開(kāi)始嘗試通過(guò)節(jié)點(diǎn)較少的網(wǎng)絡(luò)核心去控制整個(gè)網(wǎng)絡(luò)[18-19].特別地，文獻(xiàn)[19]利用葉子刪除法獲得復(fù)雜網(wǎng)絡(luò)的控制核心體，基于PΒH 可控條件證明了對(duì)于大部分的網(wǎng)絡(luò)，控制網(wǎng)絡(luò)核心體即可完成對(duì)整個(gè)網(wǎng)絡(luò)的控制.然而，對(duì)于一些網(wǎng)絡(luò)，僅通過(guò)對(duì)其核心體實(shí)施控制，不能完成對(duì)整個(gè)網(wǎng)絡(luò)的控制.

本文基于PΒH 可控理論，針對(duì)上述復(fù)雜網(wǎng)絡(luò)實(shí)際控制中核心體可控但網(wǎng)絡(luò)本身不可控的問(wèn)題，提出兩種復(fù)雜網(wǎng)絡(luò)可控方案.一是嘗試其它使核心體可控的驅(qū)動(dòng)節(jié)點(diǎn)組；二是增加新的驅(qū)動(dòng)節(jié)點(diǎn).推廣到一般情形，提出并論證在控制核心體的基礎(chǔ)上，對(duì)每次刪除葉子中度為1 的節(jié)點(diǎn)增加控制可以使原始網(wǎng)絡(luò)可控.最后，重點(diǎn)分析了核心體加鏈路的網(wǎng)絡(luò)，證明增加對(duì)該鏈中度為1 的節(jié)點(diǎn)的控制可以使整個(gè)網(wǎng)絡(luò)可控.

1 復(fù)雜網(wǎng)絡(luò)可控的基本概念

復(fù)雜網(wǎng)絡(luò)可控是指系統(tǒng)在一定的時(shí)間內(nèi)，經(jīng)過(guò)適當(dāng)?shù)耐饨巛斎胱饔?，從任意初始狀態(tài)變成最終狀態(tài)的性質(zhì).考慮以下含有N個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)動(dòng)力學(xué)系統(tǒng)[15,17]：

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

其中λ為矩陣A對(duì)應(yīng)的特征值，IN為N階單位矩陣.

對(duì)于含有葉子的稀疏無(wú)向復(fù)雜網(wǎng)絡(luò)，持續(xù)地刪除網(wǎng)絡(luò)葉子及其連邊并保留孤立節(jié)點(diǎn)，直至整個(gè)網(wǎng)絡(luò)不再包含度為1 的節(jié)點(diǎn)，最終得到的所有連通集團(tuán)和孤立節(jié)點(diǎn)共同構(gòu)成網(wǎng)絡(luò)的控制核心體[19].其中，葉子是指由一度節(jié)點(diǎn)、鄰居和它們之間的連接構(gòu)成的結(jié)構(gòu).

2 主要結(jié)果

對(duì)于大部分的復(fù)雜網(wǎng)絡(luò)，僅對(duì)其核心體實(shí)施控制即可實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的控制，我們稱為可由核心體控制的網(wǎng)絡(luò).反之，核心體可控而整個(gè)網(wǎng)絡(luò)不可控，稱為不可由核心體控制的網(wǎng)絡(luò).下面，我們將針對(duì)3 種不可由核心體控制的網(wǎng)絡(luò)展開(kāi)討論.

2.1 一種不可由核心體控制的網(wǎng)絡(luò)

對(duì)于含有N個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)，如圖1a)所示，前N-2 個(gè)節(jié)點(diǎn)圍成一個(gè)環(huán)，且節(jié)點(diǎn)1 分別與節(jié)點(diǎn)2、…、節(jié)點(diǎn)N-2 相連，節(jié)點(diǎn)N-4 連接一個(gè)葉子，經(jīng)過(guò)葉子刪除后得到核心體A0(虛線圈起部分).對(duì)節(jié)點(diǎn)1、2 施加控制，利用PΒH可控條件可知，此時(shí)核心體可控(見(jiàn)圖1b)).

圖1 不可由核心體控制的網(wǎng)絡(luò)的控制情況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

下面分析在該控制輸入下，整個(gè)網(wǎng)絡(luò)的可控性.此時(shí)的控制輸入矩陣記為B.

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

可見(jiàn)，在最后一個(gè)矩陣中，除第N-1行之外其余行的非零元素均在不同行不同列.因此，這些行向量是線性無(wú)關(guān)的.又因?yàn)锳滿足因此-1 是矩陣A的一個(gè)特征值.此時(shí)，矩陣(-IN-A,B)第N- 1 行的非零元素均可經(jīng)過(guò)一些初等行變換化為零元素.說(shuō)明rank(-IN-A,B) =N- 1 ＜N恒成立，由PΒH 可控條件可知，在控制節(jié)點(diǎn)1，2 的情況下，原始網(wǎng)絡(luò)不可控.

對(duì)于這種不可由核心體控制的網(wǎng)絡(luò)，可以使用如下兩種替代控制方案：

1)更換驅(qū)動(dòng)節(jié)點(diǎn)的組合

由于控制核心體的驅(qū)動(dòng)節(jié)點(diǎn)不止一組，可以尋找其它驅(qū)動(dòng)節(jié)點(diǎn)的組合并驗(yàn)證其可控性.否則，考慮方法二.對(duì)于圖1a)所示的網(wǎng)絡(luò)，分別在節(jié)點(diǎn)N- 4的兩側(cè)各取一個(gè)節(jié)點(diǎn)，如選取節(jié)點(diǎn)2 和節(jié)點(diǎn)N- 2，此時(shí)新的控制輸入矩陣記為B1，通過(guò)計(jì)算驗(yàn)證可知rank(λIN-A,B1)=N，說(shuō)明原始網(wǎng)絡(luò)可控(見(jiàn)圖1c)).

這種方法通常適用于節(jié)點(diǎn)較少的網(wǎng)絡(luò).對(duì)于節(jié)點(diǎn)比較多、連接復(fù)雜的網(wǎng)絡(luò)，尋找其它驅(qū)動(dòng)節(jié)點(diǎn)的組合并不容易，即使可以找到所有驅(qū)動(dòng)節(jié)點(diǎn)的組合，但數(shù)量過(guò)多，驗(yàn)證可控條件的計(jì)算量也相應(yīng)增加.

2）在原有的使核心體可控的控制輸入下增加新的驅(qū)動(dòng)節(jié)點(diǎn).對(duì)于圖1b)所示的網(wǎng)絡(luò)，在原有兩個(gè)驅(qū)動(dòng)節(jié)點(diǎn)的情況下增加一個(gè)新的驅(qū)動(dòng)節(jié)點(diǎn).這里可增加節(jié)點(diǎn)N- 3、節(jié)點(diǎn)N- 2、節(jié)點(diǎn)N- 1或節(jié)點(diǎn)N，更新的控制輸入矩陣B分別如下：

2.2 一般不可由核心體控制的網(wǎng)絡(luò)

定理1對(duì)于任意不可由核心體控制的網(wǎng)絡(luò)，在核心體可控的基礎(chǔ)上，對(duì)每次刪除中度為1 的節(jié)點(diǎn)增加控制，則原始網(wǎng)絡(luò)完全可控.

證明不妨以一次刪除為例，設(shè)包含一個(gè)度為1的節(jié)點(diǎn)的網(wǎng)絡(luò)為：

其中，1表示一度節(jié)點(diǎn)與其鄰居的連接，向量α表示刪去的葉子與其余節(jié)點(diǎn)的連接情況.矩陣A0表示刪除一個(gè)葉子后得到的網(wǎng)絡(luò).假設(shè)A0可以由B0控制，由PΒH可控條件滿足：

在核心體可控的基礎(chǔ)上，再增加對(duì)度為1的節(jié)點(diǎn)的控制，得到新的輸入矩陣B如下：

因此

由PΒH 可控條件可知整個(gè)網(wǎng)絡(luò)可控.于是，在核心體可控的前提下，對(duì)每次刪除時(shí)度為1的節(jié)點(diǎn)增加控制，原始網(wǎng)絡(luò)完全可控.

在圖2 所示的網(wǎng)絡(luò)中，節(jié)點(diǎn)1、2、3、8 和它們之間的連邊構(gòu)成核心體（虛線部分）.可以驗(yàn)證，控制節(jié)點(diǎn)1、2 和8 后，核心體可控，但整個(gè)網(wǎng)絡(luò)不可控.根據(jù)定理1，增加控制每次刪除中度為1 的節(jié)點(diǎn)12，10，7 和5（箭頭表示），整個(gè)網(wǎng)絡(luò)可控.

圖2 增加對(duì)每次刪除中度為1的節(jié)點(diǎn)的控制使網(wǎng)絡(luò)可控Fig.2 Add control to the once-deleted node every time,the network is controllable

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

2.3 一類特殊的不可由核心體控制的網(wǎng)絡(luò)

定理2對(duì)于任意的由核心體和一條連接核心體的鏈路構(gòu)成的網(wǎng)絡(luò)，若僅控制核心體不能控制整個(gè)網(wǎng)絡(luò).那么，在核心體可控的基礎(chǔ)上，僅增加對(duì)鏈路的控制，則原始網(wǎng)絡(luò)完全可控.

證明不妨設(shè)由核心體和一條鏈路構(gòu)成的網(wǎng)絡(luò)A有如下形式，且增加對(duì)度為1的節(jié)點(diǎn)的控制，則

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

對(duì)于原始網(wǎng)絡(luò)A有

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

上述分析說(shuō)明在核心體可控的基礎(chǔ)上，對(duì)鏈路中度為1 的節(jié)點(diǎn)增加控制，整個(gè)網(wǎng)絡(luò)完全可控.該思路可以不必控制每次刪除中度為1 的節(jié)點(diǎn)，一定程度上減少了控制輸入成本.進(jìn)一步地，該理論同樣適用于核心體加多條鏈路的情形.

定理3對(duì)于任意由核心體和多條獨(dú)立鏈路構(gòu)成的網(wǎng)絡(luò)，若控制核心體不能控制整個(gè)網(wǎng)絡(luò).那么，在核心體可控的基礎(chǔ)上，增加對(duì)每條鏈路中度為1的節(jié)點(diǎn)的控制，則原始網(wǎng)絡(luò)可控.

證明同定理2.

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

圖3 增加對(duì)每條鏈路中度為1的節(jié)點(diǎn)的控制使網(wǎng)絡(luò)可控Fig.3 Add control to the one-degree nodes in each link,and the network is controllable

3 結(jié)束語(yǔ)

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