王媛媛 袁正中 ，2，3? 趙琛

（1.閩南師范大學數(shù)學與統(tǒng)計學院，漳州 363000）（2.閩南師范大學數(shù)據(jù)科學與統(tǒng)計福建省高校重點實驗室，漳州 363000）（3.閩南師范大學數(shù)字福建氣象大數(shù)據(jù)研究所，漳州 363000）（4.河北師范大學計算機與網(wǎng)絡空間安全學院，石家莊 050024）（5.河北省網(wǎng)絡與信息安全重點實驗室，石家莊 050024）

引言

復雜網(wǎng)絡是將現(xiàn)實世界中各種大型復雜關聯(lián)系統(tǒng)抽象成網(wǎng)絡圖進行研究的一種理論工具.現(xiàn)實生活中存在著各種各樣的復雜網(wǎng)絡，如生物網(wǎng)絡[1]、交通網(wǎng)絡[2]、社會網(wǎng)絡[3]、信息網(wǎng)絡[4]等 .這些復雜網(wǎng)絡展現(xiàn)出豐富的動力學特性[5]，如同步、涌現(xiàn)等[6-8].認識復雜網(wǎng)絡是一個重要而漫長的過程，這一領域的研究工作面臨著諸多的挑戰(zhàn)[9].目前，研究人員對復雜網(wǎng)絡動力學的探索已經(jīng)取得了一些進展，主要集中在復雜網(wǎng)絡的傳播[10]、搜索[11]、同步[12，13]、控制[14]等問題 .其中網(wǎng)絡控制問題已經(jīng)成為網(wǎng)絡科學的一個重要研究方向.

復雜網(wǎng)絡可控是指網(wǎng)絡系統(tǒng)在適當?shù)妮斎胱饔孟?，在有限時間內(nèi)可以在任意兩個狀態(tài)之間傳遞的性質(zhì).其中，需要被獨立輸入作用的節(jié)點稱為驅(qū)動節(jié)點.近年來，關于網(wǎng)絡可控性的研究已經(jīng)有了一些突出成果.2011年，Liu等[15]在Nature首次基于線性系統(tǒng)思想研究了復雜網(wǎng)絡的結(jié)構(gòu)可控問題.該文獻利用Kalman可控條件從理論上證明了網(wǎng)絡結(jié)構(gòu)可控所需要的驅(qū)動節(jié)點為該網(wǎng)絡最大匹配中的未匹配節(jié)點.但該理論只適用于邊權(quán)可獨立選取的有向復雜網(wǎng)絡，在無向復雜網(wǎng)絡或給定權(quán)重的網(wǎng)絡中不適用.進而Yuan等[16]提出嚴格可控理論對結(jié)構(gòu)可控理論進行了優(yōu)化.嚴格可控理論將網(wǎng)絡可控性問題轉(zhuǎn)化為鄰接矩陣特征值的問題，說明復雜網(wǎng)絡驅(qū)動節(jié)點數(shù)等于該鄰接矩陣特征值的最大幾何重數(shù)[16，17]，并且通過對矩陣進行初等變換可以找到對應的驅(qū)動節(jié)點.特別地，對于稀疏網(wǎng)絡，網(wǎng)絡的驅(qū)動節(jié)點數(shù)由網(wǎng)絡鄰接矩陣的秩決定.然而，復雜網(wǎng)絡系統(tǒng)含有成千上萬的節(jié)點，直接運用上面的方法計算和尋找控制網(wǎng)絡的驅(qū)動節(jié)點是非常困難的.

本研究關注無向無權(quán)網(wǎng)絡的實際控制問題，設置完整的控制輸入矩陣滿足系統(tǒng)的嚴格可控條件.文中網(wǎng)絡中的一度節(jié)點、它的鄰居和連邊共同組成的結(jié)構(gòu)稱為網(wǎng)絡葉子.已有的研究表明，刪除葉子以及與葉子的連邊不會改變網(wǎng)絡的零度（nullity）[18].從網(wǎng)絡控制理論來說，這個結(jié)論表明對于無向的零特征值占優(yōu)網(wǎng)絡，刪除葉子以及與葉子的連邊不會改變網(wǎng)絡的可控性能.那么，這種刪除法是否也有利于控制輸入矩陣的設置呢？本文基于線性系統(tǒng)的PBH可控性條件，給出網(wǎng)絡核心體可控則整個網(wǎng)絡可控的充要條件.利用該結(jié)論，我們可以持續(xù)刪除網(wǎng)絡葉子，直到網(wǎng)絡中不存在葉子為止，得到一個子結(jié)構(gòu)——網(wǎng)絡核心體.其中，不同刪除順序得到的網(wǎng)絡控制核心體中的節(jié)點數(shù)以及節(jié)點之間的連接關系相同[18].再對該網(wǎng)絡核心體設置控制輸入矩陣.然后逐步回溯驗證網(wǎng)絡可控條件，從而實現(xiàn)對網(wǎng)絡控制核心體實施控制，即可完全控制原始網(wǎng)絡.該方法適用于大量稀疏的無向網(wǎng)絡，為網(wǎng)絡控制輸入矩陣的設置開辟了新的路徑.

1 基礎知識

考慮以下含有n個節(jié)點的無向網(wǎng)絡動力學系統(tǒng)[19，20]：

式中，x=（x1，x2，…，xn）T表示n個節(jié)點的狀態(tài)；A=（aij）∈Rn×n為系統(tǒng)的鄰接矩陣，其中，aij=0表示節(jié)點i、j之間沒有連接，aij=1表示節(jié)點i、j之間存在連接，aii=0；B∈Rn×m為列滿秩輸入矩陣，其中B的列數(shù)表示需要獨立控制的節(jié)點個數(shù).如果B不是列滿秩矩陣，則說明整個控制系統(tǒng)有多余的控制輸入，可以進一步簡化[16].u=（u1，u2，…，um）T為m個獨立的控制輸入.系統(tǒng)（1）可控的充要條件為下列條件之一成立[19，20]：

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

對于含有葉子結(jié)構(gòu)的稀疏無向復雜網(wǎng)絡，持續(xù)地刪除網(wǎng)絡葉子及其連邊并保留孤立節(jié)點，直至整個網(wǎng)絡不再包含度為1的節(jié)點，最終得到的所有連通集團和孤立節(jié)點共同構(gòu)成了網(wǎng)絡的核心體.不失一般性，可以將含有葉子結(jié)構(gòu)的復雜網(wǎng)絡鄰接矩陣A表示為如下形式：

其中第一個節(jié)點的度為1，其鄰居為第二個節(jié)點，它們及其之間的連邊被稱為網(wǎng)絡的葉子.向量α表示葉子與其余節(jié)點的連接情況.矩陣A0是（n?2）×（n?2）階方陣，表示刪除葉子及其連接后所有剩余節(jié)點之間的連接情況.

2 主要工作

2.1 控制理論

通過持續(xù)刪除網(wǎng)絡葉子并保留孤立節(jié)點，網(wǎng)絡的控制核心體中只包含孤立節(jié)點和一些規(guī)模較小的連通集團.顯然，孤立節(jié)點一定需要直接的獨立控制輸入，所以必然是驅(qū)動節(jié)點.網(wǎng)絡的其它驅(qū)動節(jié)點則包含在剩下的小規(guī)模的連通集團中，可以通過文獻[16]中提出的對鄰接矩陣進行初等變換的方法找到其對應的驅(qū)動節(jié)點，從而高效快速地完成對原始網(wǎng)絡驅(qū)動節(jié)點的尋找.通過這種處理之后，一個無向復雜網(wǎng)絡可控問題被拆分成多個小集團的可控問題，即網(wǎng)絡核心體的可控問題.驅(qū)動節(jié)點可以從網(wǎng)絡核心體中尋找，整個控制輸入矩陣是否也可以從網(wǎng)絡核心體中尋找呢？換句話說，如果完成了對網(wǎng)絡核心體的控制，是否就可以控制整個網(wǎng)絡？為此，我們通過以下定理回答了上述問題，該定理給出了對網(wǎng)絡核心體實施控制即可完全控制原始網(wǎng)絡的條件.

注：定理僅證明一次刪除的情形.在實際使用中，我們需記錄每次刪除時的向量α，利用最終的控制核心對應的B0逐步回溯驗證定理條件.

2.2 實例分析

考慮一個具有12個節(jié)點的無向稀疏網(wǎng)絡，網(wǎng)絡連接情況如圖1所示.對該無向復雜網(wǎng)絡，尋找網(wǎng)絡中的1度節(jié)點，刪除葉子并保留孤立節(jié)點，直至網(wǎng)絡中不存在1度節(jié)點為止.刪除過程為：第一次刪除節(jié)點11，12和對應連邊；第二次刪除節(jié)點9，10和對應連邊，產(chǎn)生孤立節(jié)點8；第三次刪除節(jié)點6，7和對應連邊，以及第四次刪除節(jié)點4，5和對應連邊，最終得到網(wǎng)絡控制核心體.在圖1中，空心節(jié)點表示將被刪去的節(jié)點，被虛線圈起的實心節(jié)點和它們之間的連邊構(gòu)成網(wǎng)絡的控制核心體.網(wǎng)絡控制核心體的鄰接矩陣為：

圖1 通過控制核心使原始網(wǎng)絡可控Fig.1 The original network is controlled by the control core

此時，對鄰接矩陣A0進行初等變換可以很容易地找到對應的一組驅(qū)動節(jié)點為1，2和8節(jié)點，并且對它們實施獨立的控制輸入可以滿足網(wǎng)絡控制核心體的可控性，即控制1，2和8節(jié)點可以使網(wǎng)絡控制核心體可控.接著，依次驗證刪除過程中網(wǎng)絡是否滿足控制條件（5）或條件（6）.

第四次刪除節(jié)點（4，5）時，α4=(1，0，1，0)Τ，，條件（5）滿足；第三次刪除節(jié)點（6，7）時，α3=（0，0，1，0，1，0）Τ，，條件（5）滿足；

第二次刪除節(jié)點（9，10）時 ，α2=(0，1，0，0，0，0，0，1)Τ，，條件（5）滿足；

第一次刪除節(jié)點（11，12）時 ，α1=(0，0，1，0，0，0，0，0，0，0)Τ，，條件（5）仍然滿足.

上面驗證表明，僅通過控制含有4個節(jié)點的網(wǎng)絡核心體即可控制整個原始網(wǎng)絡.可見，該方法可以有效地簡化對無向復雜網(wǎng)絡控制輸入的尋找過程，完成對大型復雜網(wǎng)絡的實際控制.

3 結(jié)論

本文針對無向復雜網(wǎng)絡尋找控制輸入困難的問題，基于PBH可控條件和葉子節(jié)點刪除法給出了對網(wǎng)絡核心體實施控制即可控制原始網(wǎng)絡的充要條件，得到了尋找無向網(wǎng)絡中控制輸入節(jié)點的方法：①持續(xù)刪除葉子結(jié)構(gòu)及其連邊并保留孤立節(jié)點得到網(wǎng)絡核心體；②利用可控條件尋找該核心體的一個控制輸入；③回推驗證每一次刪除中相關條件是否滿足并得出結(jié)論：若條件（5）或條件（6）滿足，表明僅利用該網(wǎng)絡核心體的控制輸入即可完全控制原始網(wǎng)絡.

由于條件（5）和條件（6）均為不等式，所以在大多數(shù)情況下該條件均可滿足.這是因為條件（5）和條件（6）的否定式均為等式，等式的解一定是有限點集或者空集，這些集合測度均為0，所以條件（5）和條件（6）的否定形式成立的參數(shù)選擇范圍小，被選擇的可能性不高.這樣就可以得到條件（5）和條件（6）在大多數(shù)情況下均可滿足.因此，對于絕大多數(shù)的無向復雜網(wǎng)絡，只要我們完成了對網(wǎng)絡控制核心體的控制，就能控制整個網(wǎng)絡.該結(jié)論對解決大型稀疏網(wǎng)絡的控制問題提供了非常簡單的思路和具體的方法.