基于0/-1特征值的網(wǎng)絡(luò)可控性優(yōu)化研究

陳興凱，盧昱，王凱，楊文兵

（1. 陸軍工程大學(xué) 裝備指揮與管理系，河北 石家莊 050003; 2. 陸軍工程大學(xué) 裝備模擬訓(xùn)練中心，河北 石家莊050003; 3. 9804廠軍代室，云南 曲靖 655000）

在當(dāng)前學(xué)科融合的大背景下，網(wǎng)絡(luò)可控性[1-3]逐漸受到了人們的廣泛關(guān)注，它是網(wǎng)絡(luò)科學(xué)借鑒了控制科學(xué)的思想，將網(wǎng)絡(luò)看作是一個系統(tǒng)，從整體的角度去研究如何去控制網(wǎng)絡(luò)，使網(wǎng)絡(luò)達(dá)到預(yù)期狀態(tài)。在目前的研究中，影響可控性的因素是什么、如何提高可控性一直以來都是網(wǎng)絡(luò)可控性研究中的熱點問題。

近年來，網(wǎng)絡(luò)可控性的研究基本上都是圍繞文獻(xiàn)[1-2]展開的。文獻(xiàn)[1]將Lin的結(jié)構(gòu)可控性定理[4]運用于有向、無權(quán)的復(fù)雜網(wǎng)絡(luò)中，基于二部圖給出了最小控制輸入節(jié)點(也稱為最小驅(qū)動節(jié)點)的求解方法，提出了網(wǎng)絡(luò)可控性的最大匹配理論和最小輸入定理。文獻(xiàn)[2]則是將研究對象擴(kuò)充到無向、同權(quán)的復(fù)雜網(wǎng)絡(luò)，提出了基于PBH可控性判定的嚴(yán)格可控性理論，具有更廣泛的適用性。上述兩篇文獻(xiàn)奠定了近年來網(wǎng)絡(luò)可控性研究的基礎(chǔ)，為后續(xù)諸多研究提供了理論支撐。對于影響可控性因素的探索，從文獻(xiàn)[1]就開始了，作者探討了網(wǎng)絡(luò)可控性與度分布的關(guān)系，并且結(jié)合實際網(wǎng)絡(luò)，發(fā)現(xiàn)稀疏異構(gòu)網(wǎng)絡(luò)比稠密同構(gòu)網(wǎng)絡(luò)更加難以控制。在隨后的研究中，文獻(xiàn)[5]研究了影響可控性的各種網(wǎng)絡(luò)特性，發(fā)現(xiàn)模塊性和聚集系數(shù)沒有明顯的影響，而出度與入度的對稱性對網(wǎng)絡(luò)可控性有一定的影響。文獻(xiàn)[6]則主要針對無向網(wǎng)絡(luò)的可控性，利用模擬退火算法改變網(wǎng)絡(luò)的度相關(guān)性，發(fā)現(xiàn)在度分布不變的情況下，網(wǎng)絡(luò)可控性會隨著度相關(guān)系數(shù)的增大而單調(diào)減小。上述文獻(xiàn)雖然給出了影響網(wǎng)絡(luò)可控性的某些因素，但并沒有給出具體的可控性優(yōu)化方法。對于如何提高網(wǎng)絡(luò)可控性，目前已經(jīng)開展了諸多研究，如文獻(xiàn)[7]通過添邊來輕微改動網(wǎng)絡(luò)結(jié)構(gòu)，從而提高網(wǎng)絡(luò)的可控性，并且在同構(gòu)、異構(gòu)隨機(jī)網(wǎng)絡(luò)和不同類型的真實網(wǎng)絡(luò)中進(jìn)行了驗證。文獻(xiàn)[8]針對當(dāng)前復(fù)雜網(wǎng)絡(luò)中的可控性優(yōu)化問題，從網(wǎng)絡(luò)中邊的方向性入手，將EOOC問題轉(zhuǎn)換為交換網(wǎng)絡(luò)的最大獨立集問題，最終通過實驗表明了網(wǎng)絡(luò)結(jié)構(gòu)可以決定可控性和優(yōu)化效果。文獻(xiàn)[9]提出了一種提高網(wǎng)絡(luò)可控性的新算法，通過重新連接網(wǎng)絡(luò)的邊來改變網(wǎng)絡(luò)結(jié)構(gòu)，從而提高可控性，最后在ER和無標(biāo)度網(wǎng)絡(luò)模型中驗證了算法的有效性。文獻(xiàn)[10]提出了一種提高有向網(wǎng)絡(luò)可控性的方法，該方法是在保持鏈路總數(shù)不變的情況下，通過改變一小部分鏈路的方向來實現(xiàn)的，通過數(shù)值模擬驗證了方法的有效性，并且說明了該方法適用于一些僅知道局部結(jié)構(gòu)信息的網(wǎng)絡(luò)。從上述文獻(xiàn)可以看出，網(wǎng)絡(luò)可控性的優(yōu)化研究實質(zhì)是根據(jù)某一特征因素進(jìn)行的網(wǎng)絡(luò)結(jié)構(gòu)調(diào)整。對于一些具有明顯規(guī)律的網(wǎng)絡(luò)結(jié)構(gòu)，目前也已展開了可控性方面的研究，如文獻(xiàn)[11]中的分形網(wǎng)絡(luò)、文獻(xiàn)[12]中的確定無標(biāo)度網(wǎng)絡(luò)和凱萊樹，均通過特征值0來確定最小控制輸入的節(jié)點個數(shù)，進(jìn)而獲取網(wǎng)絡(luò)的可控性。文獻(xiàn)[13]中的星型網(wǎng)絡(luò)則是通過特征多項式給出了最小控制輸入節(jié)點個數(shù)的計算表達(dá)式；文獻(xiàn)[14]針對路形拓?fù)浣Y(jié)構(gòu)，提出了不可控特征值的概念并給出了具體表達(dá)式。從上述文獻(xiàn)可以看出，某些關(guān)鍵特征值與某些具有特征規(guī)律的網(wǎng)絡(luò)結(jié)構(gòu)之間存在著必然聯(lián)系，這些特征值對應(yīng)的特征結(jié)構(gòu)從某種程度上決定了網(wǎng)絡(luò)的可控性，如果能夠找到關(guān)鍵的特征值，調(diào)整特征值對應(yīng)的特征結(jié)構(gòu)，則可以為網(wǎng)絡(luò)可控性的優(yōu)化提供新的思路。

綜上所述，本文將從具有規(guī)律性特征結(jié)構(gòu)的特征值入手，探究0和-1這兩個特殊特征值與網(wǎng)絡(luò)可控性之間的關(guān)系。通過消除網(wǎng)絡(luò)中0/-1對應(yīng)的規(guī)律性特征結(jié)構(gòu)，實現(xiàn)網(wǎng)絡(luò)可控性的提高，為網(wǎng)絡(luò)可控性的優(yōu)化提供新的方法和思路。

1 網(wǎng)絡(luò)可控性

從定性分析的角度來看，網(wǎng)絡(luò)可控性是指在某種拓?fù)浣Y(jié)構(gòu)和控制輸入下，網(wǎng)絡(luò)是否可以達(dá)到預(yù)期狀態(tài)。這里的控制輸入是指對網(wǎng)絡(luò)中所有節(jié)點的控制實施情況，即對網(wǎng)絡(luò)中的哪些節(jié)點進(jìn)行了控制實施，哪些節(jié)點沒有進(jìn)行控制實施。

從定量分析的角度來看，網(wǎng)絡(luò)可控性是指在某種拓?fù)浣Y(jié)構(gòu)下，網(wǎng)絡(luò)運行狀態(tài)達(dá)到預(yù)期狀態(tài)的難易程度，其強(qiáng)弱通常是由量化指標(biāo)nd[1]表示，即最小控制輸入的節(jié)點個數(shù)Nd與網(wǎng)絡(luò)節(jié)點總數(shù)N的比值：

這個指標(biāo)是以網(wǎng)絡(luò)可控性的定性判定為基礎(chǔ)，求解網(wǎng)絡(luò)可控下對應(yīng)的最小控制輸入，以最小控制輸入的節(jié)點個數(shù)作為可控性量化指標(biāo)的主要因素，進(jìn)而對網(wǎng)絡(luò)可控性進(jìn)行量化評估。

1.1 定性分析

網(wǎng)絡(luò)可控性的定性分析其實是對網(wǎng)絡(luò)可控與否的判定，它借鑒了控制科學(xué)中可控性[15]的思想，將網(wǎng)絡(luò)看作是一個系統(tǒng)，以鄰接矩陣作為系統(tǒng)矩陣，控制輸入矩陣作為輸入矩陣，根據(jù)可控性的判定條件對網(wǎng)絡(luò)系統(tǒng)進(jìn)行可控性判定。具體而言，對于有N個節(jié)點、M個控制輸入(M≤N)的網(wǎng)絡(luò)系統(tǒng)，其狀態(tài)方程可表述為

為N維網(wǎng)絡(luò)狀態(tài)變量；u=[u1u2··· uM]T為M維輸入變量；A為N×N維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鄰接矩陣，A中的元素對應(yīng)了網(wǎng)絡(luò)中兩點的連接情況，即aij=0表示i點和j點之間沒有連接，aij=1表示i點和j點之間有連接，本文研究的網(wǎng)絡(luò)為更具一般性的無自環(huán)、無向網(wǎng)絡(luò)，因此有aii=0且aij=aji；B為N×M維控制輸入矩陣，B中的元素對應(yīng)了網(wǎng)絡(luò)中的控制實施情況，每一列和每一行最多僅有一個1元素，其他均為0元素，若第i行存在1元素則表示對i點有控制實施。

針對式(2)的網(wǎng)絡(luò)系統(tǒng)，常用的網(wǎng)絡(luò)可控性判定方法有2種：基本秩判據(jù)[1]和PBH秩判據(jù)[2]。

基本秩判據(jù)是根據(jù)式(3)進(jìn)行可控性判據(jù)：

若網(wǎng)絡(luò)系統(tǒng)滿足式(3)，則網(wǎng)絡(luò)系統(tǒng)是可控的，否則不可控。

PBH秩判據(jù)是根據(jù)式(4)進(jìn)行可控性判據(jù)：

式中：λk為鄰接矩陣A所對應(yīng)的所有特征值。若網(wǎng)絡(luò)系統(tǒng)滿足式(4)，則網(wǎng)絡(luò)系統(tǒng)是可控的，否則不可控。

從上述2種判定方法不難看出，網(wǎng)絡(luò)可控性的定性分析取決于鄰接矩陣A和控制輸入矩陣B，即網(wǎng)絡(luò)可控與否是由網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和控制輸入共同決定的。

1.2 定量分析

從網(wǎng)絡(luò)可控性的定性分析不難看出，在某種拓?fù)浣Y(jié)構(gòu)下，對網(wǎng)絡(luò)所有節(jié)點實施控制(即M=N)，則網(wǎng)絡(luò)必定可以達(dá)到可控狀態(tài)。然而，此時所實施的控制不一定是最優(yōu)的，因為對于任何一種網(wǎng)絡(luò)拓?fù)涠?，最?yōu)的控制輸入應(yīng)該是使得網(wǎng)絡(luò)達(dá)到可控狀態(tài)時，對網(wǎng)絡(luò)中最少的節(jié)點實施控制。這種針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最優(yōu)控制即最小控制輸入。最小控制輸入的節(jié)點個數(shù)直接反映了在某種拓?fù)浣Y(jié)構(gòu)下網(wǎng)絡(luò)達(dá)到可控性的難易程度，即可用于可控性的定量分析。因此，對網(wǎng)絡(luò)可控性進(jìn)行定量分析的關(guān)鍵是求解出最小控制輸入的節(jié)點個數(shù)。

根據(jù)式(3)或式(4)的可控性判據(jù)，可以為最小控制輸入的求解提供基本思路：針對鄰接矩陣A，求出滿足式(3)或式(4)的最簡矩陣B。最直接的方法是代入法，即針對網(wǎng)絡(luò)中的所有節(jié)點，將可能的控制輸入由少至多進(jìn)行遍歷組合，生成所有可能情況下的輸入矩陣B，由簡至繁逐一代入式(3)或式(4)進(jìn)行驗證，一旦出現(xiàn)判定為可控，則可將此時的矩陣B確定最小控制輸入。然而，對于n個節(jié)點的網(wǎng)絡(luò)而言，求出所有矩陣B的計算復(fù)雜程度為顯然，代入法在n較大的情況下是不適用的。如果不通過代入法求最小控制輸入，式(3)由于涉及矩陣相乘，求出矩陣B是十分困難的。因此，較為可行的代數(shù)方法是基于式(4)的PBH秩判據(jù)。

式(4)中的PBH判定矩陣[λkI-A B](以下簡稱PBH矩陣)可以寫成以下模式：

不難看出，PBH矩陣在滿秩的情況下，上式中的矩陣應(yīng)該滿足所有行向量線性不相關(guān)，而虛線右邊的矩陣B可以消除虛線左邊λkI-A中行向量組的相關(guān)性，這就為求出矩陣B提供了實現(xiàn)方法：首先計算出λkI-A，再將其進(jìn)行初等列變換，不改變行相關(guān)特性；根據(jù)行相關(guān)情況，通過設(shè)置最少的bi消除λkI-A的行相關(guān)性，使得PBH矩陣中的所有行向量均不相關(guān)；最后將所有λk對應(yīng)的bi設(shè)置情況進(jìn)行整合，使得bi可以消除所有λk對應(yīng)的PBH矩陣中行向量的相關(guān)性，即滿足式(4)。此時，所對應(yīng)的bi即組成最小控制輸入對應(yīng)的矩陣B，最小控制輸入的節(jié)點個數(shù)Nd=rank(B)。

求出Nd后，則可根據(jù)式(1)得到網(wǎng)絡(luò)可控性的度量指標(biāo)nd，完成定量分析。

2 0/-1特征值

從最小控制輸入的求解可以看出，影響網(wǎng)絡(luò)可控性的直接因素是PBH矩陣中λkI-A矩陣的行相關(guān)性。而行相關(guān)性不僅受到鄰接矩陣A的影響，還受到特征值λk的影響。雖然對于大部分特征值而言，它們與行相關(guān)之間的聯(lián)系并沒有明顯的規(guī)律性，但0和-1這兩個特征值卻比較特殊，它們不僅與行相關(guān)之間存在著一定聯(lián)系，更是極大地影響著網(wǎng)絡(luò)可控性。

2.1 行相關(guān)類型

對于λkI-A矩陣的行相關(guān)性可以分為3類：零向量相關(guān)、重復(fù)相關(guān)和非重復(fù)相關(guān)。

1)零向量相關(guān)即存在全0行的行向量。以Ax表示A的第x行，則零向量相關(guān)表現(xiàn)為

2)重復(fù)相關(guān)即存在完全相同的相關(guān)行向量。以Ax表示A的第x行，則重復(fù)相關(guān)表現(xiàn)為

2.2 0/-1特征值與行相關(guān)性的關(guān)系

在上述3種相關(guān)情況中，非重復(fù)相關(guān)與特征值之間的聯(lián)系很難找到；而零向量相關(guān)與0特征值、重復(fù)相關(guān)與0/-1特征值之間存在著明顯的聯(lián)系，具體聯(lián)系可由下述兩個定理描述：

定理1 如果矩陣λkI-A中存在著零向量相關(guān)，則對應(yīng)特征值λk一定為0。

定理2 如果矩陣λkI-A中存在著行重復(fù)相關(guān)，則對應(yīng)特征值λk一定為0或 -1。

證明 設(shè)矩陣λkI-A中重復(fù)相關(guān)的行為第i行和第 j行，即

因為A中的元素僅有0或1，即aij=0或aij=1，所以 λk=0 或 λk=-1。證畢

由定理1和定理2可知，在λkI-A矩陣的所有行相關(guān)中，如果存在零向量相關(guān)，那么一定是0特征值決定的；如果存在重復(fù)相關(guān)，那么一定是0/-1特征值決定的。其他非0/-1特征值所對應(yīng)的λkI-A矩陣不可能出現(xiàn)零向量相關(guān)和重復(fù)相關(guān)。

對于零向量相關(guān)、重復(fù)相關(guān)和非重復(fù)相關(guān)這3種λkI-A矩陣的行相關(guān)性而言，形成零向量相關(guān)至少需要有一行為全零行，形成重復(fù)相關(guān)至少需要有兩行完全相同，形成非重復(fù)相關(guān)至少需要有三行并且通過合適的系數(shù)組成相關(guān)組。而且由于λkI-A矩陣為對角線均為λk的實對稱矩陣，且其中的元素僅有0和 -1兩種，因此從形成的難易程度上來看，在λkI-A矩陣中形成零向量相關(guān)、重復(fù)相關(guān)比非重復(fù)相關(guān)要容易很多，即所有λkI-A矩陣的行相關(guān)中絕大部分都是零向量相關(guān)和重復(fù)相關(guān)。由定理1和定理2可知，零相關(guān)均由特征值0決定，重復(fù)相關(guān)均由特征值0/-1決定，不難得出，相對于其他特征值，特征值0/-1極大地影響著λkI-A矩陣的相關(guān)性，即網(wǎng)絡(luò)中絕大部分的最小控制輸入節(jié)點是由特征值0/-1所決定的。

3 可控性優(yōu)化

相對于0/-1特征值而言，非0/-1特征值對可控性的影響相對較小，并且難以找到具有明顯規(guī)律性的特征結(jié)構(gòu)。而0/-1特征值對可控性的影響相對較大，并且具有明顯的對應(yīng)特征結(jié)構(gòu)。因此，可以通過消除0/-1的特征結(jié)構(gòu)，從而減小0/-1對應(yīng)λkI-A矩陣中的行相關(guān)性，最終達(dá)到提高網(wǎng)絡(luò)可控性的目的，實現(xiàn)網(wǎng)絡(luò)的可控性優(yōu)化。

3.1 0特征結(jié)構(gòu)

在特征值0對應(yīng)的特征結(jié)構(gòu)中，存在著一種具有明顯規(guī)律性的特征結(jié)構(gòu)，其具體定義如下：

定義1 獨立共連結(jié)構(gòu)。獨立共連結(jié)構(gòu)是指網(wǎng)絡(luò)中存在若干節(jié)點(稱為對象節(jié)點)，這些節(jié)點之間是獨立不相連的，且它們與網(wǎng)絡(luò)中其他節(jié)點的連接狀況完全相同。如圖1中的對象節(jié)點1、2、3構(gòu)成了獨立共連結(jié)構(gòu)。

圖 1 獨立共連結(jié)構(gòu)Fig. 1 The isolated link structure

對于上述的獨立共連結(jié)構(gòu)，存在著一種特殊情況：當(dāng)對象節(jié)點與網(wǎng)絡(luò)中其他節(jié)點的連接情況均為不相連時，對象節(jié)點均為孤立節(jié)點。

獨立共連結(jié)構(gòu)與特征0的關(guān)系可由下述定理描述：

定理3 如果一個網(wǎng)絡(luò)中存在獨立共連結(jié)構(gòu)，則該網(wǎng)絡(luò)的鄰接矩陣A具有特征值0。

證明 鄰接矩陣A的特征值λk滿足：

當(dāng)網(wǎng)絡(luò)中存在孤立節(jié)點時，不妨設(shè)節(jié)點1為孤立節(jié)點，則 d et(λI-A)為

顯然，當(dāng) λk=0 時，det(λkI-A)中存在全 0 行，使得 d et(λkI-A)=0，因此 φ (0)=0，即 0 為 A 的 特征值。

當(dāng)網(wǎng)絡(luò)中存在不含孤立節(jié)點的獨立共連結(jié)構(gòu)時，不妨設(shè)1到i點為獨立共連結(jié)構(gòu)，則det(λ I-A)為

顯然，當(dāng) λk=0 時，det(λkI-A)中的 1 到 i行完全相同，使得 det(λkI-A)=0，因此 φ(0)=0，即 0為 A 的特征值。證畢。

3.2 -1特征結(jié)構(gòu)

在特征值 -1對應(yīng)的特征結(jié)構(gòu)中，存在著一種具有明顯規(guī)律性的特征結(jié)構(gòu)，其具體定義如下：

定義2 互連共連結(jié)構(gòu)?；ミB共連結(jié)構(gòu)是指網(wǎng)絡(luò)中存在若干節(jié)點(稱為對象節(jié)點)，這些節(jié)點之間是互相連接的，且它們與網(wǎng)絡(luò)中其他節(jié)點的連接狀況完全相同。如圖2中的對象節(jié)點1、2、3構(gòu)成了互連共連結(jié)構(gòu)。

圖 2 互連共連結(jié)構(gòu)Fig. 2 The connected link structure

互連共連結(jié)構(gòu)與特征 -1的關(guān)系可由下述定理描述：

定理4 如果一個網(wǎng)絡(luò)中存在互連共連結(jié)構(gòu)，則該網(wǎng)絡(luò)的鄰接矩陣A具有特征值 -1。

證明 鄰接矩陣A的特征值λk滿足式(5)，不妨設(shè)1到i點為互連共連結(jié)構(gòu)，則det(λkI-A)為

顯然，當(dāng) λk=-1 時，det(λkI-A)中的 1 到 i行完全相同，使得 det(λkI-A)=0，因此 φ(-1)=0，即-1 為A的特征值。證畢。

3.3 結(jié)構(gòu)優(yōu)化

獨立共連結(jié)構(gòu)和互連共連結(jié)構(gòu)是0/-1特征結(jié)構(gòu)中具有明顯規(guī)律性的結(jié)構(gòu)，為了提高網(wǎng)絡(luò)的可控性，則可以通過消除網(wǎng)絡(luò)中的這2種結(jié)構(gòu)，減少0/-1特征值對應(yīng)λkI-A矩陣的行相關(guān)性，即減少最小控制輸入的節(jié)點個數(shù)，從而實現(xiàn)可控性的優(yōu)化。

本文中的優(yōu)化方法主要是基于鄰接矩陣A來找到兩種典型的0/-1特征結(jié)構(gòu)，通過對矩陣A中對應(yīng)元素的改變來實現(xiàn)節(jié)點之間的增邊或減邊，從而實現(xiàn)結(jié)構(gòu)優(yōu)化操作。由0·I-A=-A可知，消除獨立共連結(jié)構(gòu)的處理對象為矩陣-A(或A)，消除全0行則可消除孤立節(jié)點，消除相同行則可消除不含孤立節(jié)點的獨立共連結(jié)構(gòu)；由-1·I-A=-I-A可知，消除互連共連結(jié)構(gòu)的處理對象為矩陣-I-A(或A+I)，消除相同行則可消除互連共連結(jié)構(gòu)。在整個結(jié)構(gòu)優(yōu)化過程中，設(shè)置每個步長只允許對一條邊進(jìn)行一次增邊或減邊操作，則優(yōu)化的主要步驟如下：

1）逐行判斷矩陣A是否存在全0行。如果存在且第i行為全0行，則隨機(jī)生成一個整數(shù)j，有j∈(1,N)且 j≠i，令 aij=1，aji=1，跳轉(zhuǎn) 1）繼續(xù)運行；如果不存在全0行，則跳轉(zhuǎn)2）。

2）逐行對比矩陣A中的其他行是否存在相同行。如果存在相同行，則獲取對象點集CP、共連點集 SP，隨機(jī)生成 2個整數(shù) i和 j，有 i∈CP，j∈SP，令 aij=0，aji=0，跳轉(zhuǎn) 1）；如果不存在相同行，則跳轉(zhuǎn)3）。

3）逐行對比矩陣A+I中的其他行是否存在相同行。如果存在相同行，則獲取對象點集CP、共連點集SP，隨機(jī)生成兩個整數(shù)i和j，有i∈CP，j∈SP，令 aij=0，aji=0，跳轉(zhuǎn) 1）；如果不存在相同行，則完成網(wǎng)絡(luò)可控性的優(yōu)化。

上述主要步驟中，為了減小網(wǎng)絡(luò)的復(fù)雜程度，2）和3）均為減邊操作，這個過程可能會出現(xiàn)孤立節(jié)點，因此2）和3）中進(jìn)行減邊操作后均跳轉(zhuǎn)1），且對特征結(jié)構(gòu)的判斷順序按照上述步驟進(jìn)行。當(dāng)經(jīng)過3）完成優(yōu)化時，則說明此時的網(wǎng)絡(luò)中不存在獨立共連結(jié)構(gòu)和互連共連結(jié)構(gòu)這兩種特征結(jié)構(gòu)，0/-1特征值對應(yīng)λkI-A矩陣的行相關(guān)性極大地減小，最小控制輸入也隨之減小，整個網(wǎng)絡(luò)的可控性將得到提高。在優(yōu)化過程中，由于會消除獨立共連結(jié)構(gòu)，優(yōu)化結(jié)果可以保證網(wǎng)絡(luò)中不存在孤立節(jié)點這一特殊的獨立共連結(jié)構(gòu)，因此可以使網(wǎng)絡(luò)結(jié)構(gòu)具有一定的連通性，維持網(wǎng)絡(luò)的基本通信功能。

4 驗證分析

為了說明0/-1特征值與網(wǎng)絡(luò)可控性的關(guān)系以及本文可控性優(yōu)化的有效性，進(jìn)行3組驗證實驗。

4.1 0/-1特征值的驗證

本組實驗通過對比0/-1特征值的幾何重數(shù)和基于PBH求解的最小控制輸入個數(shù)Nd，來說明0/-1特征值對網(wǎng)絡(luò)可控性的影響。

特征值0所對應(yīng)0·I-A矩陣的行相關(guān)性可由特征值0的幾何重數(shù)c(0)量化求得：

特征值-1所對應(yīng)-1·I-A矩陣的行相關(guān)性可由特征值-1的幾何重數(shù)c(-1)量化求得：

實驗中的網(wǎng)絡(luò)對象為ER、NW、BA 3種典型的復(fù)雜網(wǎng)絡(luò)，且均為無向網(wǎng)絡(luò)。由于本文旨在研究優(yōu)化步驟對網(wǎng)絡(luò)可控性的影響，暫不考慮網(wǎng)絡(luò)規(guī)模，因此為了提高計算速度，所有網(wǎng)絡(luò)均為100個節(jié)點，即N=100。生成不同參數(shù)下的ER、NW、BA 3種典型復(fù)雜網(wǎng)絡(luò)，其中，ER網(wǎng)絡(luò)、NW網(wǎng)絡(luò)的變化參數(shù)為連接概率p，BA網(wǎng)絡(luò)的變化參數(shù)為平均度的半值/2，每個參數(shù)均獨立生成了20個網(wǎng)絡(luò)，求出的實驗數(shù)值均為20個網(wǎng)絡(luò)的平均值。實驗結(jié)果如圖3所示。

從圖3可以看出，0/-1特征值的幾何重數(shù)之和，基于PBH求得的最小控制輸入個數(shù)，二者幾乎是一致的。這就說明了在所有λkI-A矩陣的行相關(guān)情況中，即便有非重復(fù)相關(guān)也是占極少數(shù)，而0/-1特征值對應(yīng)的相關(guān)情況基本決定了網(wǎng)絡(luò)的最小控制輸入，極大地影響著網(wǎng)絡(luò)可控性。

圖 3 3種復(fù)雜網(wǎng)絡(luò)的幾何重數(shù)和最小控制輸入Fig. 3 Geometric multiplicity and minimum control input of three kinds of complex networks

4.2 可控性優(yōu)化的驗證

本組實驗從4.1節(jié)生成的網(wǎng)絡(luò)中，挑選ER、NW、BA 3個不同類型的網(wǎng)絡(luò)，挑選網(wǎng)絡(luò)的最小控制輸入個數(shù)分別為50、51、50。對3個網(wǎng)絡(luò)分別實施3.3節(jié)的優(yōu)化步驟，計算每個步長下經(jīng)過結(jié)構(gòu)控制后網(wǎng)絡(luò)的可控性。網(wǎng)絡(luò)可控性的度量指標(biāo)為根據(jù)式(1)計算的nd，實驗結(jié)果如圖4所示。

從圖4可以看出，雖然在經(jīng)過某些步長后，nd沒有發(fā)生變化或者升高，但從整體來看3個網(wǎng)絡(luò)的可控性指標(biāo)nd均呈現(xiàn)了降低趨勢。nd沒有發(fā)生變化或者升高是由于在消除兩種典型結(jié)構(gòu)的過程中，可能會產(chǎn)生新的結(jié)構(gòu)，出現(xiàn)新的行相關(guān)情況，尤其是在消除互連共連結(jié)構(gòu)時，其實很容易就轉(zhuǎn)換成了獨立共連結(jié)構(gòu)。但隨著2種典型結(jié)構(gòu)的逐漸消除，nd逐漸降低，最小控制輸入節(jié)點的個數(shù)逐漸減小，即網(wǎng)絡(luò)的可控性逐漸增強(qiáng)。說明經(jīng)過本文的優(yōu)化操作后，網(wǎng)絡(luò)的可控性得到了提高。

圖 4 3個網(wǎng)絡(luò)的網(wǎng)絡(luò)可控性Fig. 4 Network controllability of three networks

4.3 實際網(wǎng)絡(luò)的驗證

本組實驗主要對2個實際的無線網(wǎng)絡(luò)進(jìn)行可控性優(yōu)化。其中，網(wǎng)絡(luò)Ⅰ為無線傳感器網(wǎng)絡(luò)，受傳感器功耗的限制，其特點是網(wǎng)絡(luò)連邊較少，屬于稀疏網(wǎng)絡(luò)。網(wǎng)絡(luò)Ⅱ為無線通信網(wǎng)絡(luò)，為滿足通信鏈路需求，其特點是網(wǎng)絡(luò)連邊較多，屬于稠密網(wǎng)絡(luò)。兩個網(wǎng)絡(luò)的節(jié)點數(shù)量N和連邊數(shù)量L、優(yōu)化過程中增邊數(shù)量Ladd和減邊數(shù)量Ldel、優(yōu)化前可控性度量指標(biāo)nd和優(yōu)化后指標(biāo)如 表1所示。

表 1 兩個無線網(wǎng)絡(luò)的信息統(tǒng)計Table 1 The information of two kinds of wireless networks

從表1中優(yōu)化前后的可控性度量指標(biāo)可以看出，經(jīng)過可控性優(yōu)化后，2個網(wǎng)絡(luò)的可控性度量指標(biāo)均降低，說明了網(wǎng)絡(luò)可控性得到了提高。同時，通過2個網(wǎng)絡(luò)的對比可以看出，對于連邊較少的稀疏網(wǎng)絡(luò)，優(yōu)化過程中實施增邊操作較多，這是由于減邊操作極易造成孤立節(jié)點，需要通過增邊進(jìn)行彌補消除；而對于連邊較多的稠密網(wǎng)絡(luò)，優(yōu)化過程中實施減邊操作較多，這是由于減邊操作不易造成孤立節(jié)點，出現(xiàn)增邊的情況就相對較少。

5 結(jié)束語

本文為了確定網(wǎng)絡(luò)可控性度量指標(biāo)，闡述了基于PBH的最小控制輸入求解方法；通過分析研究0/-1特征值與矩陣λkI-A中行相關(guān)性的關(guān)系，明確了0/-1特征值對網(wǎng)絡(luò)可控性的影響，提出了針對0/-1特征結(jié)構(gòu)的可控性優(yōu)化方法；通過驗證分析，證明了0/-1特征值極大地影響著網(wǎng)絡(luò)可控性，并且經(jīng)過本文的可控性優(yōu)化，網(wǎng)絡(luò)可控性能夠得到有效地提高。在下一步的研究中，一方面將對非0/-1特征值，尤其是整數(shù)特征值，對應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行分析研究，探究減小非重復(fù)相關(guān)的可控性優(yōu)化方法；另一方面，將考慮網(wǎng)絡(luò)結(jié)構(gòu)對通信傳輸?shù)挠绊?，以通信延遲、傳輸帶寬等網(wǎng)絡(luò)性能指標(biāo)為約束條件，對可控性優(yōu)化方法中的增邊或減邊操作進(jìn)一步完善，形成不同的結(jié)構(gòu)調(diào)整策略，提高實際中的應(yīng)用價值。