基于網(wǎng)絡(luò)核心體的復(fù)雜網(wǎng)絡(luò)控制分析*

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

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

引言

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

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

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

1 基礎(chǔ)知識(shí)

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

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

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

對(duì)于含有葉子結(jié)構(gòu)的稀疏無向復(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ò)的核心體.不失一般性，可以將含有葉子結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)鄰接矩陣A表示為如下形式：

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

2 主要工作

2.1 控制理論

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

注：定理僅證明一次刪除的情形.在實(shí)際使用中，我們需記錄每次刪除時(shí)的向量α，利用最終的控制核心對(duì)應(yīng)的B0逐步回溯驗(yàn)證定理?xiàng)l件.

2.2 實(shí)例分析

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

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

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

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

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

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

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

3 結(jié)論

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

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