劉慧 王炳珺 陸君安 李增揚(yáng)

1) (華中科技大學(xué)人工智能與自動(dòng)化學(xué)院, 武漢 430074)

2) (武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 武漢 430072)

3) (華中師范大學(xué)計(jì)算機(jī)學(xué)院, 武漢 430079)

本文研究復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的無向網(wǎng)絡(luò)牽制控制的優(yōu)化選點(diǎn)及節(jié)點(diǎn)組重要性排序問題.根據(jù)牽制控制的同步準(zhǔn)則, 網(wǎng)絡(luò)的牽制控制同步取決于網(wǎng)絡(luò)的Laplacian 刪后矩陣的最小特征值.因此, 通過合理選擇受控節(jié)點(diǎn)集得到一個(gè)較大的Laplacian 刪后矩陣最小特征值, 是牽制控制優(yōu)化選點(diǎn)問題的核心所在.基于Laplacian刪后矩陣最小特征值的圖譜性質(zhì), 本文提出了多個(gè)受控節(jié)點(diǎn)選取的遞歸迭代算法, 該算法適用于任意類型的網(wǎng)絡(luò).通過BA 無標(biāo)度網(wǎng)絡(luò)、NW 小世界網(wǎng)絡(luò)及一些實(shí)際網(wǎng)絡(luò)中的仿真實(shí)驗(yàn)表明: 該算法在控制節(jié)點(diǎn)數(shù)較少時(shí), 能有效找到最優(yōu)受控節(jié)點(diǎn)集.最后討論了在復(fù)雜網(wǎng)絡(luò)牽制控制背景下節(jié)點(diǎn)組重要性排序問題, 提出節(jié)點(diǎn)組的重要性排序與受控節(jié)點(diǎn)的數(shù)目有關(guān).

1 引 言

近年來, 復(fù)雜網(wǎng)絡(luò)上的控制與優(yōu)化引起各研究領(lǐng)域的興趣[1?4].在許多現(xiàn)實(shí)場景中, 控制一個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)幾乎是不現(xiàn)實(shí)的, 特別在節(jié)點(diǎn)數(shù)多、連接復(fù)雜的大規(guī)模網(wǎng)絡(luò)中.為了節(jié)約控制成本, 可以通過只控制網(wǎng)絡(luò)的部分節(jié)點(diǎn)并利用網(wǎng)絡(luò)的連通性來達(dá)到控制整個(gè)網(wǎng)絡(luò)的目的, 即牽制控制.該研究方向受到廣泛關(guān)注, 并取得了許多代表性的進(jìn)展.文獻(xiàn)[5,6]提出可以通過對網(wǎng)絡(luò)的部分節(jié)點(diǎn)施加控制器來實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的同步, 并研究了無標(biāo)度網(wǎng)絡(luò)的牽制控制, 發(fā)現(xiàn)牽制控制度大的節(jié)點(diǎn)比隨機(jī)選點(diǎn)控制所需要的節(jié)點(diǎn)少.文獻(xiàn)[7]提出了自適應(yīng)牽制控制同步判據(jù), 給出了網(wǎng)絡(luò)中牽制節(jié)點(diǎn)的數(shù)量和耦合強(qiáng)度的關(guān)系式.文獻(xiàn)[8]發(fā)現(xiàn)了網(wǎng)絡(luò)在線性反饋的牽制控制下, 可以通過自適應(yīng)調(diào)整耦合強(qiáng)度使網(wǎng)絡(luò)達(dá)到同步.文獻(xiàn)[9,10]從網(wǎng)絡(luò)的圖譜性質(zhì)出發(fā), 研究了復(fù)雜網(wǎng)絡(luò)的牽制控制的能控性.其他擴(kuò)展性工作還有許多, 這里不再一一贅述.上述工作主要集中在提出牽制控制同步的準(zhǔn)則上, 沒有深入研究如何選擇控制節(jié)點(diǎn)達(dá)到網(wǎng)絡(luò)的優(yōu)化控制.至今, 牽制控制如何選擇受控節(jié)點(diǎn)仍然是沒有充分解決的問題, 需進(jìn)一步理解牽制控制策略與網(wǎng)絡(luò)結(jié)構(gòu)特征的關(guān)系[11].

目前, 有一些工作從網(wǎng)絡(luò)的拓?fù)涠攘砍霭l(fā)給出網(wǎng)絡(luò)牽制控制選點(diǎn)的策略.比如, 文獻(xiàn)[1]提出,當(dāng)網(wǎng)絡(luò)受控節(jié)點(diǎn)較少時(shí), 應(yīng)當(dāng)優(yōu)先控制度大的節(jié)點(diǎn), 當(dāng)受控節(jié)點(diǎn)較多時(shí), 應(yīng)當(dāng)優(yōu)先控制度較小的節(jié)點(diǎn).Wang 和Chen[5], Song 和Cao[12], 以及Ali 和Soleyman[13]研究了基于度指標(biāo)的選點(diǎn)方案, 傾向于控制度最大的節(jié)點(diǎn); Rong 等[14]、Jia 和Li[15]討論基于介性中心度(betweenness centrality, BC)的牽制控制方案.文獻(xiàn)[16]提出了一種基于數(shù)據(jù)流的牽制控制策略, 該策略在實(shí)際網(wǎng)絡(luò)中可以獲得與基于BC 的牽制方案相似的效果, 但計(jì)算量更小.文獻(xiàn)[17]使用K-shell 分解法來尋找處于網(wǎng)絡(luò)中心位置的節(jié)點(diǎn), 發(fā)現(xiàn)K-core 值更大的節(jié)點(diǎn)能更有利于網(wǎng)絡(luò)傳播.文獻(xiàn)[18]提出根據(jù)節(jié)點(diǎn)的森林距離大小來選擇網(wǎng)絡(luò)的控制節(jié)點(diǎn), 優(yōu)先選擇森林距離較小的節(jié)點(diǎn), 且該策略可以應(yīng)用在有向網(wǎng)絡(luò)及非連通網(wǎng)絡(luò)中.文獻(xiàn)[19]依據(jù)矩陣擾動(dòng)理論得出推論, 可以根據(jù)Laplacian 矩陣的最大特征值對應(yīng)特征向量的最大分量選擇控制節(jié)點(diǎn), 所得節(jié)點(diǎn)對網(wǎng)絡(luò)Laplacian矩陣的特征值影響最大.但是, 這些工作都只能從某個(gè)或某些拓?fù)涠攘砍霭l(fā)指導(dǎo)性地建議牽制選點(diǎn)方案, 或者對某類特性的網(wǎng)絡(luò)提供針對性的建議,很難給出一個(gè)精準(zhǔn)的方案, 在實(shí)際應(yīng)用時(shí)效果不好把握.本文在我們前期工作[1]的基礎(chǔ)上, 結(jié)合Laplacian 刪后矩陣最小特征值的圖譜性質(zhì), 提出了牽制控制多個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)組篩選算法, 能精準(zhǔn)地找出最優(yōu)的受控節(jié)點(diǎn)集合.該方法不局限于特定屬性的復(fù)雜網(wǎng)絡(luò), 對任何類型的網(wǎng)絡(luò)都適用.

2 模型介紹及問題提出

先介紹復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型, 并給出牽制控制同步準(zhǔn)則.考慮如下具有N 個(gè)節(jié)點(diǎn)的連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)模型[20], 其中網(wǎng)絡(luò)的所有節(jié)點(diǎn)的自身動(dòng)力學(xué)一致, 網(wǎng)絡(luò)的狀態(tài)方程描述如下:

其中i=1, 2, ···, N.在上述方程中, xi∈Rn表示節(jié)點(diǎn)i 的狀態(tài), f (·) 描述節(jié)點(diǎn)的自身動(dòng)力學(xué), 正常數(shù)c 表示網(wǎng)絡(luò)的全局耦合強(qiáng)度, ui是施加在節(jié)點(diǎn)i 上的控制器, P ∈Rn×n是內(nèi)連耦合矩陣, 它是正定或者半正定的.LN=[lij]N×N為網(wǎng)絡(luò)的Laplacian 矩陣.本文僅考慮無向網(wǎng)絡(luò)的情況, 即Laplacian 矩陣對角線上的元素為節(jié)點(diǎn)的度, 非對角線元素分別根據(jù)節(jié)點(diǎn)i, j 之間是否存在連邊而為–1 或0.

假設(shè)網(wǎng)絡(luò)的目標(biāo)狀態(tài)s(t)滿足:

對復(fù)雜網(wǎng)絡(luò)進(jìn)行牽制控制的目的是: 通過控制網(wǎng)絡(luò)中的部分節(jié)點(diǎn), 使得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的狀態(tài)都趨近于目標(biāo)狀態(tài)s(t).由文獻(xiàn)[1]可知, 對于一個(gè)無向網(wǎng)絡(luò), 當(dāng)選定其受控節(jié)點(diǎn)集時(shí), 可以通過如下代數(shù)不等式來判別網(wǎng)絡(luò)能否通過牽制控制達(dá)到同步,

其中, l 表示受控節(jié)點(diǎn)個(gè)數(shù); LN?l是網(wǎng)絡(luò)拉普拉斯矩陣 LN刪去受控節(jié)點(diǎn)對應(yīng)行和列所得到的矩陣,即拉普拉斯矩陣的刪后子矩陣, 也稱為Grounded-Laplacian 矩陣[21], N–l 表示刪后子矩陣的維數(shù);λ1(LN?l)表示該刪后子矩陣的最小特征值.此外,式中α 是由節(jié)點(diǎn)自身動(dòng)力學(xué)函數(shù) f (·) 和內(nèi)連耦合矩陣P 決定的, 與網(wǎng)絡(luò)全局耦合強(qiáng)度c 及網(wǎng)絡(luò)結(jié)構(gòu)無關(guān).

接下來, 提出本文要研究的問題, 即優(yōu)化(2)式左端項(xiàng).當(dāng)網(wǎng)絡(luò)的受控節(jié)點(diǎn)數(shù) l 給定時(shí), 如何確定受控節(jié)點(diǎn)或者受控節(jié)點(diǎn)集, 使得被牽制控制的網(wǎng)絡(luò)的 λ1(LN?l) 最大, 這就是牽制控制優(yōu)化選點(diǎn)問題.然而, 尋找網(wǎng)絡(luò)合適的受控節(jié)點(diǎn)集使得λ1(LN?l)最大化, 這個(gè)問題的計(jì)算量是龐大的.計(jì)算量主要來自兩部分, 第一部分是計(jì)算矩陣特征值的復(fù)雜度, 第二部分是受控節(jié)點(diǎn)的組合數(shù)量龐大而造成的復(fù)雜度.特別是牽制控制多個(gè)節(jié)點(diǎn)的情況, 從所有節(jié)點(diǎn)中選擇最優(yōu)的受控節(jié)點(diǎn)集S ={s1,s2,··· ,sl},從而得到最大的 λ1(LN?l) , 這是一個(gè)計(jì)算量巨大的NP-hard 問題.現(xiàn)有的研究對于給定的受控節(jié)點(diǎn)數(shù)l, 僅能對可能的優(yōu)化控制節(jié)點(diǎn)集給出寬泛建議[1].例如當(dāng)受控節(jié)點(diǎn)數(shù)較少時(shí), 應(yīng)當(dāng)優(yōu)先牽制度大的節(jié)點(diǎn), 當(dāng)受控節(jié)點(diǎn)數(shù)較多時(shí), 優(yōu)先控制度小的節(jié)點(diǎn); 或者僅能給出 λ1(LN?l) 的上界及下界拓?fù)涮卣鞴烙?jì), 并不能得到精確的最優(yōu)受控節(jié)點(diǎn)集.本文結(jié)合刪后矩陣 λ1(LN?l) 的幾個(gè)特征估計(jì)式,推導(dǎo)出網(wǎng)絡(luò)節(jié)點(diǎn)的篩選條件, 提出控制多個(gè)節(jié)點(diǎn)的牽制控制優(yōu)化選點(diǎn)算法, 能夠在控制節(jié)點(diǎn)數(shù)較少時(shí)準(zhǔn)確找出最大 λ1(LN?l) , 并減少 λ1(LN?l) 的計(jì)算次數(shù).

3 牽制控制優(yōu)化選點(diǎn)算法

先介紹本文算法的理論基礎(chǔ)及推導(dǎo)過程.該算法旨在篩除低價(jià)值受控節(jié)點(diǎn)及受控節(jié)點(diǎn)組合, 減少受控節(jié)點(diǎn)集 λ1(LN?l) 的計(jì)算, 從而以較少的計(jì)算量得出最優(yōu)受控節(jié)點(diǎn)集.

定理1[1]假設(shè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)用圖G 表示.圖G 的節(jié)點(diǎn)集為 V (G)={1,··· ,N}, 受控節(jié)點(diǎn)集S ?V , 受控節(jié)點(diǎn)數(shù)為l, 其中 s1,··· ,sl表示受控節(jié)點(diǎn), 令 p1,··· ,pN?l表示未受控的節(jié)點(diǎn), 未受控節(jié)點(diǎn)集表示為V/S, 并用符號 ωpj表示受控節(jié)點(diǎn)集S 到未受控節(jié)點(diǎn) pj的連邊數(shù), 則有

下面對(3)式進(jìn)行變形, 用符號e 表示受控節(jié)點(diǎn)集內(nèi)部連邊數(shù)(即受控節(jié)點(diǎn)與受控節(jié)點(diǎn)之間的連邊數(shù)), ksi表示受控節(jié)點(diǎn) si的度.注意到, 有如下關(guān)系式成立:

根據(jù)(3)式和(4)式可得

由此得到能減少最優(yōu) λ1(LN?l) 的計(jì)算次數(shù)的一個(gè)過濾條件.(5)式基于節(jié)點(diǎn)度進(jìn)行篩選, 即尋找一個(gè)節(jié)點(diǎn)集, 使節(jié)點(diǎn)總度滿足該式.而在實(shí)際網(wǎng)絡(luò)中,對于某些度較小的節(jié)點(diǎn), 即使將其搭配度最大的前l(fā) - 1 個(gè)節(jié)點(diǎn), 所組成的節(jié)點(diǎn)集可能也無法滿足條件, 因此這種度小的節(jié)點(diǎn)無需考慮, 這就是節(jié)點(diǎn)初步篩選的依據(jù), 即節(jié)點(diǎn)度不滿足下式的節(jié)點(diǎn)將直接被排除:

其次, 假設(shè)通過初步篩選之后剩余了n 個(gè)節(jié)點(diǎn), 在這n 個(gè)節(jié)點(diǎn)中滿足不等式(5)的節(jié)點(diǎn)組合,理論上有種, 從這些組合中尋找最優(yōu)組合仍然計(jì)算量較大.但往往在剩余n 個(gè)節(jié)點(diǎn)中有大部分都是度較小的節(jié)點(diǎn), 它們基本只能和度最大的節(jié)點(diǎn)組成滿足條件(5)式的組合.根據(jù)排列組合可知,在剩余n 個(gè)節(jié)點(diǎn)中找到l 個(gè)滿足度篩選條件的節(jié)點(diǎn)組合可以分為兩部分: 第一部分是包含度最小節(jié)點(diǎn)的組合, 組合數(shù)有種, 其中w =min(l, m), m 表示當(dāng)前最小度節(jié)點(diǎn)的個(gè)數(shù); 第二部分是不包含度最小的節(jié)點(diǎn)的組合, 組合數(shù)有種.這兩部分的組合數(shù)用公式表示如下:

牽制控制多個(gè)節(jié)點(diǎn)算法最優(yōu) λ1(LN?l) 的計(jì)算算法具體實(shí)現(xiàn)如下: 在節(jié)點(diǎn)組合篩選過程中, 首先選擇l 個(gè)節(jié)點(diǎn)作為初始受控節(jié)點(diǎn), 通常選擇度排序中的前l(fā) 個(gè)節(jié)點(diǎn).計(jì)算控制這l 個(gè)節(jié)點(diǎn)的λ1(LN?l)作為篩選標(biāo)準(zhǔn) λ?, 根據(jù)(3)式有

如果控制節(jié)點(diǎn)集 { s1,s2,··· ,sl} 要得到一個(gè)更大的 λ1(LN?l) , 即

則必須有

(10)式和(11)式即是篩選控制節(jié)點(diǎn)集的依據(jù).只要在后續(xù)節(jié)點(diǎn)集 λ1(LN?l) 計(jì)算中得到一個(gè)更大的 λ1(LN?l) , 則將這個(gè) λ1(LN?l) 當(dāng)作新的 λ?來篩選剩余節(jié)點(diǎn)集.最終對所有剩余組合計(jì)算篩選后得到的 λ?即為最優(yōu) λ1(LN?l).

需要說明的是, 篩選條件(11)式計(jì)算簡單, 僅需要知道節(jié)點(diǎn)的度即可.而篩選條件(10)式計(jì)算量相對大些, 還需要計(jì)算受控節(jié)點(diǎn)集的內(nèi)部連邊數(shù), 比篩選條件(11)式準(zhǔn)確程度更高.所以在實(shí)際仿真中, 可以結(jié)合兩者實(shí)現(xiàn)計(jì)算復(fù)雜度和精準(zhǔn)程度上的平衡, 也可以只采用其中的一個(gè)式子.基于以上實(shí)現(xiàn)過程, 現(xiàn)將選取多個(gè)牽制節(jié)點(diǎn)的算法列出如下.

算法1

步驟1選擇度排名前l(fā) 的節(jié)點(diǎn)當(dāng)作初始控制節(jié)點(diǎn), 然后計(jì)算其特征值 λ1(LN?l) 作為 λ?;

步驟2將 λ?代入(6)式, 通過節(jié)點(diǎn)的度篩除不能滿足(6)式的節(jié)點(diǎn);

步驟3遞歸計(jì)算剩余節(jié)點(diǎn)中的滿足條件(11)的節(jié)點(diǎn)組合;

步驟4在第3 步的基礎(chǔ)上, 計(jì)算剩余節(jié)點(diǎn)中的滿足條件(10)的節(jié)點(diǎn)組合;

步驟5逐個(gè)計(jì)算剩余節(jié)點(diǎn)組合對應(yīng)的刪后矩陣的 λ1, 如果計(jì)算出更大的 λ1(λ1>λ?) , 則將其當(dāng)作新的篩選標(biāo)準(zhǔn), 返回第2 步繼續(xù)迭代;如果未找到更大的 λ1, 則當(dāng)前 λ?即是最優(yōu) λ1(LN?l) , 當(dāng)前控制節(jié)點(diǎn)集即是最優(yōu)控制節(jié)點(diǎn)集.

4 實(shí)驗(yàn)仿真及算法有效性分析

本節(jié)將上述選點(diǎn)算法分別運(yùn)用到生成網(wǎng)絡(luò)如無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò), 以及真實(shí)數(shù)據(jù)網(wǎng)絡(luò)如Email 網(wǎng)絡(luò)、Dolphin 網(wǎng)絡(luò).通過數(shù)值仿真說明所提算法減少計(jì)算量的有效性, 通過與其他選點(diǎn)算法的對比說明算法1 相較于其他選點(diǎn)策略在選擇λ1(LN?l)較大的節(jié)點(diǎn)集時(shí)更優(yōu).

4.1 算法初步應(yīng)用和最優(yōu)控制節(jié)點(diǎn)集的討論

例1考慮參數(shù)設(shè)置為N = 1000, q = 5 的一個(gè)BA 無標(biāo)度網(wǎng)絡(luò), 該網(wǎng)絡(luò)以5 個(gè)節(jié)點(diǎn)的環(huán)狀圖作為初始網(wǎng)絡(luò), 每次增加一個(gè)新的節(jié)點(diǎn), 且依照度優(yōu)先連接策略連接到網(wǎng)絡(luò)中已有的q 個(gè)節(jié)點(diǎn)上.生成的BA 網(wǎng)絡(luò)見圖1.根據(jù)本文的算法, 將受控節(jié)點(diǎn)數(shù)l 從2 增加到4, 來觀察最優(yōu)受控節(jié)點(diǎn)集的情況.節(jié)點(diǎn)的度排序情況見表1.

牽制控制兩個(gè)節(jié)點(diǎn), 即l = 2 的情況.如果枚舉法需計(jì)算499500 次998 階矩陣的最小特征值.根據(jù)算法1, 首先選擇節(jié)點(diǎn)集合{2, 11}控節(jié)點(diǎn)集,計(jì)算此時(shí)的 λ1(LN?l) , 以此 λ?=0.1986 作為初始的篩選標(biāo)準(zhǔn), 可以得到節(jié)點(diǎn){2, 11, 3, 18, 1,9, 4}滿足條件(6)式, 然后依次計(jì)算節(jié)點(diǎn)組合的λ1(LN?l), 發(fā)現(xiàn)遍歷所有的組合也沒有得到更大的λ1(LN?l) , 則最初的 λ?=0.1986 為最優(yōu)的 λ1(LN?l) ,節(jié)點(diǎn)集合{2, 11}為牽制控制兩個(gè)節(jié)點(diǎn)時(shí)的最優(yōu)受控節(jié)點(diǎn)集合.

圖1 生成 的BA 網(wǎng) 絡(luò).不同顏色代表節(jié)點(diǎn)的度的大小,紅色表示度大的節(jié)點(diǎn), 藍(lán)色表示度小的節(jié)點(diǎn)Fig.1.A generated BA network.Different colors represent different node-degrees in the network; nodes in red have relative large degrees, and nodes in blue have small degrees.

牽制控制三個(gè)節(jié)點(diǎn), 即l = 3 情況.如果采用枚舉法需計(jì)算166167000 次997 階矩陣的最小特征值.根據(jù)算法1, 首先選擇節(jié)點(diǎn)集合{2, 11, 3}作為初始的受控節(jié)點(diǎn)集合, 計(jì)算此時(shí)的 λ?=0.3046 ,以此 λ?作為初始的篩選標(biāo)準(zhǔn), 可以得到節(jié)點(diǎn){2, 11,3, 18, 1, 9, 4, 8, 14, 31}滿足條件(6)式, 然后依次計(jì)算節(jié)點(diǎn)組合的 λ1(LN?l) , 發(fā)現(xiàn)節(jié)點(diǎn)組合{2, 3,18}的 λ1(LN?l)= 0.3155 更大, 然后將此λ1(LN?l)作為新的 λ?再進(jìn)行篩選節(jié)點(diǎn), 最終未能發(fā)現(xiàn)更大的 λ1(LN?l) , 即此時(shí)的節(jié)點(diǎn)集合{2, 3, 18}即為牽制控制三個(gè)節(jié)點(diǎn)時(shí)的最優(yōu)受控節(jié)點(diǎn)集合.

牽制控制四個(gè)節(jié)點(diǎn), 即l=4 情況.根據(jù)算法1,首先選擇節(jié)點(diǎn)集合{2, 11, 3, 18}作為初始的受控制節(jié)點(diǎn)集, 計(jì)算此時(shí)的 λ?=0.3894 , 以此 λ?作為初始的篩選標(biāo)準(zhǔn), 發(fā)現(xiàn)節(jié)點(diǎn)的度排序前17 的節(jié)點(diǎn)都滿足篩選條件(6), 依次計(jì)算節(jié)點(diǎn)組合的 λ1(LN?l) ,發(fā)現(xiàn)節(jié)點(diǎn)集合{2, 11, 18, 9}的λ1(LN?l)=0.3963更大, 且將其作為新的篩選標(biāo)準(zhǔn)后, 沒有發(fā)現(xiàn)更大的 λ1(LN?l) , 即此時(shí)的節(jié)點(diǎn)集合{2, 11, 18, 9}即為牽制控制四個(gè)節(jié)點(diǎn)時(shí)的最優(yōu)受控節(jié)點(diǎn)集合.

表1 節(jié)點(diǎn)度排序及節(jié)點(diǎn)編號(BA 網(wǎng)絡(luò), N = 1000, q = 5)Table 1.Degree ordering and node numbering in a BA network with N = 1000 and q = 5.

從上面的實(shí)驗(yàn)結(jié)果可以看出, 當(dāng)受控節(jié)點(diǎn)數(shù)由少變多時(shí), 比如從控制3 個(gè)節(jié)點(diǎn)增加到控制4 個(gè)節(jié)點(diǎn)時(shí), 最優(yōu)受控節(jié)點(diǎn)組合分別是{2, 3, 18}、{2, 11,18, 9}, 優(yōu)化的受控節(jié)點(diǎn)集合不是在控制3 個(gè)節(jié)點(diǎn)的優(yōu)化組合上加上一個(gè)節(jié)點(diǎn), 而是在原有的基礎(chǔ)上有所刪減、有所變化的節(jié)點(diǎn)集合.這就說明, 當(dāng)受控節(jié)點(diǎn)數(shù)目l 增加時(shí), 最優(yōu)受控節(jié)點(diǎn)集不能通過貪心選點(diǎn)策略得出.

4.2 算法1 減少優(yōu)化 λ 1(LN?l) 的計(jì)算量的有效性分析

為了客觀評價(jià)本文算法減少計(jì)算量的效果, 這里給出兩個(gè)指標(biāo):首次篩選剩余節(jié)點(diǎn)n(算法1 第二步), 度篩選后剩余節(jié)點(diǎn)組合R(算法1 第三步).這兩個(gè)指標(biāo)能體現(xiàn)算法1 在篩選中的效果.這兩個(gè)指標(biāo)的計(jì)算結(jié)果均為10 次重復(fù)實(shí)驗(yàn)取平均.

1) 首次篩選剩余節(jié)點(diǎn)數(shù)n 相關(guān)仿真結(jié)果及分析

用n 表示首次篩選（算法1 第二步）后剩余的節(jié)點(diǎn)數(shù), 實(shí)驗(yàn)結(jié)果在表2 中列出.n 是一個(gè)重要的指標(biāo), 它很大程度決定了本文算法的計(jì)算復(fù)雜度,因?yàn)?λ1(LN?l) 理論計(jì)算次數(shù)與剩余節(jié)點(diǎn)n 關(guān)系很大.如果首次篩選不能將n 縮減到100 個(gè)節(jié)點(diǎn)左右的范圍, 則待考慮的節(jié)點(diǎn)組合仍然會非常多, 后續(xù)的計(jì)算量比較大.簡而言之, n 越小算法效果越好.由表2 可見, 隨著受控節(jié)點(diǎn)數(shù)l 從2 增加到6,剩余節(jié)點(diǎn)數(shù)n 增加; 隨著連邊數(shù)q 減少或者連接概率P 減少, 剩余節(jié)點(diǎn)數(shù)n 隨之增加.但實(shí)際上, 通過步驟3 計(jì)算后的剩余節(jié)點(diǎn)組合遠(yuǎn)小于.因?yàn)榧词故峭ㄟ^首次篩選后的節(jié)點(diǎn), 它們當(dāng)中度較小的節(jié)點(diǎn)也占相當(dāng)大的比例, 它們往往只能搭配極少數(shù)度大的節(jié)點(diǎn).因此在種組合中, 絕大部分組合都不滿足條件, 詳細(xì)見后文剩余節(jié)點(diǎn)組合R 對應(yīng)的實(shí)驗(yàn)數(shù)據(jù).

2) 剩余節(jié)點(diǎn)的組合數(shù)量R 相關(guān)仿真結(jié)果及分析

用R 表示通過算法1 第三步篩選后的節(jié)點(diǎn)組合數(shù)量.指標(biāo)R 是 λ1(LN?l) 的實(shí)際計(jì)算次數(shù)的上限, 因?yàn)榧词购罄m(xù)組合沒有計(jì)算出更大的λ1(LN?l)來實(shí)現(xiàn)又一輪的節(jié)點(diǎn)組合篩選, 也僅需將剩余組合全部計(jì)算.如果后續(xù)計(jì)算中得到了更大的 λ1(LN?l) ,并依據(jù)算法1 第二、三步再篩選掉一部分節(jié)點(diǎn)組合, 則計(jì)算次數(shù)將更少.從表3 中可以看到滿足條件的組合數(shù)R 遠(yuǎn)小于這也說明了相比于窮舉法, 本文的遞歸算法是有效的, 篩除了大量低價(jià)值節(jié)點(diǎn)組合.

表2 通過步驟2 篩選后的剩余節(jié)點(diǎn)數(shù)nTable 2.Number of remaining nodes n after Step 2 in Algorithm 1.

表3 通過步驟3 篩選后剩余節(jié)點(diǎn)的組合數(shù)量RTable 3.Number of combinations R of remaining nodes after Step 3 in Algorithm 1.

4.3 本文算法與其他選點(diǎn)策略的對比

本節(jié)將對當(dāng)前常用牽制控制選點(diǎn)策略與本文算法運(yùn)用在實(shí)際網(wǎng)絡(luò)中, 進(jìn)行算法選點(diǎn)效果的對比.首先介紹當(dāng)前常用選點(diǎn)策略.1)度選點(diǎn)算法.依據(jù)節(jié)點(diǎn)度排序來選擇受控節(jié)點(diǎn), 該算法無需額外計(jì)算量, 故通常在控制多個(gè)節(jié)點(diǎn)時(shí), 采用度選點(diǎn)算法比較方便.2) BC (betweenness centrality[14])選點(diǎn)策略.該策略基于介數(shù)中心度選點(diǎn), 旨在找出位于網(wǎng)絡(luò)的重要路徑上的節(jié)點(diǎn).3) K-shell 算法[22], 選取K-core 值大的節(jié)點(diǎn).4)最近提出的基于ESI 指標(biāo)的算法[19].5)本文算法, 篩選計(jì)算出最優(yōu)λ1(LN?l)及受控節(jié)點(diǎn).

將以上5 種策略運(yùn)用在實(shí)際網(wǎng)絡(luò)Dolphin 網(wǎng)絡(luò)及Email 網(wǎng)絡(luò)[23]中, 不同策略所得的選點(diǎn)及相應(yīng)的 λ1(LN?l) 見表4 和表5 所示.表4 和表5 的實(shí)驗(yàn)結(jié)果表明: 本文算法得到的 λ1(LN?l) 保持最優(yōu).這驗(yàn)證了本文算法相比于其他算法更優(yōu).另外,把受控節(jié)點(diǎn)分布情況進(jìn)行了可視化展示, 見圖2 和圖3.圖中藍(lán)色節(jié)點(diǎn)為未受控節(jié)點(diǎn), 黃色節(jié)點(diǎn)(Dolphin網(wǎng)絡(luò)中）及紅色節(jié)點(diǎn)（Email 網(wǎng)絡(luò)中)為受控節(jié)點(diǎn),節(jié)點(diǎn)尺寸越大, 表示節(jié)點(diǎn)度越大.圖2 為Dolphin網(wǎng)絡(luò)的情況, 4 個(gè)子圖(圖2(a)—圖2(d))給出了當(dāng)受控節(jié)點(diǎn)數(shù)l = 5, 分別運(yùn)用度算法、BC 算法、K-shell 算法、本文算法得到的受控節(jié)點(diǎn)分布情況.圖3 給出Email 網(wǎng)絡(luò)的情況.從上述網(wǎng)絡(luò)選點(diǎn)情況可見, 度選點(diǎn)策略通常難以分辨節(jié)點(diǎn)的相對位置,而不能準(zhǔn)確地找到最優(yōu)牽制控制節(jié)點(diǎn)集.BC 選點(diǎn)策略擅長尋找到關(guān)鍵路徑上的節(jié)點(diǎn), 而這樣的節(jié)點(diǎn)容易在一條關(guān)鍵路徑上前后成群出現(xiàn), 也不夠準(zhǔn)確找到最優(yōu)牽制控制的節(jié)點(diǎn)集.K-shell 選點(diǎn)策略擅長尋找在網(wǎng)絡(luò)中的相對中心位置的節(jié)點(diǎn), 集中性強(qiáng), 當(dāng)節(jié)點(diǎn)數(shù)較多時(shí), 對網(wǎng)絡(luò)邊緣節(jié)點(diǎn)控制較差.ESI 算法是根據(jù)網(wǎng)絡(luò)Laplacian 矩陣的某個(gè)特征向量來選點(diǎn), 故而其選點(diǎn)策略在節(jié)點(diǎn)的拓?fù)涮卣魃喜缓梅治? 但從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)該算法的效果不太穩(wěn)定.本文所提算法能夠準(zhǔn)確計(jì)算出控制節(jié)點(diǎn)數(shù)量較少時(shí)的最優(yōu)受控節(jié)點(diǎn), 這樣的節(jié)點(diǎn)往往度較大, 在網(wǎng)絡(luò)中的位置也相對分散, 是牽制控制的最優(yōu)節(jié)點(diǎn)集.

表4 不同算法在Dolphin 網(wǎng)絡(luò)中的選點(diǎn)及 λ 1(LN?l) 對比Table 4.Node-selections and the corresponding λ 1(LN?l) under different algorithms on the dolphin network.

表5 不同算法在Email 網(wǎng)絡(luò)中的選點(diǎn)及 λ 1(LN?l) 對比Table 5.Node-selections and the corresponding λ 1(LN?l) under different algorithms on the email network.

圖2 在4 種不同算法下Dolphin 網(wǎng)絡(luò)的選點(diǎn)情況 (a)度算法選點(diǎn)情況; (b) BC 算法選點(diǎn)情況; (c) ESI 算法選點(diǎn)情況; (d)本文算法選點(diǎn)情況Fig.2.Visualization of nodes selections on the Dolphin network underfour strategies ( l =5 ): (a) Using the degree-based pinning scheme; (b) using the BC-based pinning scheme; (c) using the ESI-based pinning scheme; (d) using our proposed algorithm.

圖3 在4 種不同算法下Email 網(wǎng)絡(luò)的選點(diǎn)情況 (a) 度算法選點(diǎn)情況; (b) BC 算法選點(diǎn)情況; (c) ESI 算法選點(diǎn)情況; (d) 本文算法選點(diǎn)情況Fig.3.Visualization of nodes selections on the Email network under four strategies: (a) Using the degree-based pinning scheme;(b) using the BC-based pinning scheme; (c) using the ESI-based pinning scheme; (d) using our proposed algorithm.

在上述仿真中可見, 本文算法相較于其他算法, 能計(jì)算出控制節(jié)點(diǎn)數(shù)較少情況下（l ≤ 6）的最優(yōu)控制節(jié)點(diǎn)集, 一定程度上填補(bǔ)了準(zhǔn)確找出最優(yōu)受控節(jié)點(diǎn)算法的空缺.但本文算法針對控制節(jié)點(diǎn)較多情況, 盡管能夠一定程度上縮減計(jì)算量, 但剩余計(jì)算量仍然較大, 難以直接計(jì)算.

5 節(jié)點(diǎn)組重要性排序

如何確定網(wǎng)絡(luò)的重要節(jié)點(diǎn)組, 這在現(xiàn)實(shí)應(yīng)用場景中廣泛存在.前面研究的確定網(wǎng)絡(luò)重要節(jié)點(diǎn)組,實(shí)際上就是提出了一種網(wǎng)絡(luò)節(jié)點(diǎn)組重要性排序方法.文獻(xiàn)[1]提出對于無向網(wǎng)絡(luò)確定重要節(jié)點(diǎn)組由網(wǎng)絡(luò)Laplacian 刪后主子矩陣的最小特征值決定;并且導(dǎo)出其上下界的精細(xì)估計(jì), 指出按度大小牽制控制并不是最優(yōu)方法, 牽制控制度大還是度小的節(jié)點(diǎn)取決于控制節(jié)點(diǎn)的數(shù)目; 本文給出了一定條件下刪后主子矩陣最小特征值一個(gè)優(yōu)化算法.

圖4 兩個(gè)網(wǎng)絡(luò)A 與B 結(jié)構(gòu)不同, 但刪去節(jié)點(diǎn)4 后網(wǎng)絡(luò)相同 (a) 網(wǎng)絡(luò)A 及其Laplacian 矩陣; (b) 網(wǎng)絡(luò)A 刪除節(jié)點(diǎn)4 及其Laplacian 矩陣; (c) 網(wǎng)絡(luò)B 及其Laplacian 矩陣; (d)網(wǎng)絡(luò)B 刪除節(jié)點(diǎn)4 及其Laplacian 矩陣Fig.4.The structures of networks A and B are different, but the remaining structures are the same after deleting node 4.(a) network A and its Laplacian matrix; (b) network A deleting node 4 and its Laplacian matrix; (c) network B and its Laplacian matrix;(d) network B deleting node 4 and its Laplacian matrix.

通過下面的例1 說明刪后主子矩陣及其特征值蘊(yùn)含了原矩陣的隱藏信息.

例1見圖4, 原網(wǎng)絡(luò)A, B 不同, 刪去節(jié)點(diǎn)4后的網(wǎng)絡(luò)相同, 但是刪后子矩陣不同, 其特征值也不同.網(wǎng)絡(luò)A 的刪后矩陣最小特征值為1, 網(wǎng)絡(luò)B 的刪后矩陣最小特征值為0.4679.這說明了節(jié)點(diǎn)4 在網(wǎng)絡(luò)A 中比在網(wǎng)絡(luò)B 中更重要.在這個(gè)簡單的例子中, 雖然刪后網(wǎng)絡(luò)相同, 但是刪后主子矩陣特征值保留了原網(wǎng)絡(luò)的隱藏信息.

下面給出一些例子說明刪后矩陣最小特征值方法應(yīng)用在節(jié)點(diǎn)組重要性排序上的有效性.

例2一個(gè)簡單鏈狀網(wǎng)絡(luò)上的分析.見圖5 所列5 個(gè)節(jié)點(diǎn)的鏈狀網(wǎng)絡(luò).

圖5 鏈狀網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N = 5 及其拉普拉斯矩陣Fig.5.Chain graph with N = 5 and its Laplacian matrix.

在該網(wǎng)絡(luò)中, 對于一個(gè)節(jié)點(diǎn)的重要性排序, 節(jié)點(diǎn)1, 2, 3 的 λ1(LN?l) 分 別 為 0.1206, 0.1981,0.3820, 所以單個(gè)節(jié)點(diǎn)排序中節(jié)點(diǎn)3 最重要, 節(jié)點(diǎn)2 和4 其次, 節(jié)點(diǎn)1 和5 最差.對于兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)組重要性排序: 節(jié)點(diǎn)組(2, 4), (1, 4), (2, 5)的λ1(LN?l)=1(最重要), (1, 5)為0.5858 (其次重要), (2, 3), (1, 3), (3, 4), (3, 5)為0.3820 (較不重要), (1, 2), (4, 5)為0.1981(最不重要).這一簡單例子也說明, 單個(gè)節(jié)點(diǎn)排序最重要的節(jié)點(diǎn)不一定包含在兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)組的第一位.

例3一根水平樑如何選擇兩個(gè)基點(diǎn)(l=2)將它吊起呢？假設(shè)樑長度為1, 然后作細(xì)等分（只要細(xì)分足夠密, 離散網(wǎng)絡(luò)的節(jié)點(diǎn)組排序可以逼近連續(xù)問題的基點(diǎn)選擇）, 分點(diǎn)視為節(jié)點(diǎn), 便成為N 個(gè)節(jié)點(diǎn)的鏈.設(shè)N=82, 根據(jù)對稱性, 第一個(gè)基點(diǎn)節(jié)點(diǎn)從節(jié)點(diǎn)1—41 中選, 另一個(gè)從82—42 中選.圖6 刻畫了 λ1(LN?2) 與所選節(jié)點(diǎn)位置的關(guān)系.從圖6 可以看出, 當(dāng)兩個(gè)節(jié)點(diǎn)選取(21, 62)時(shí)特征值取得最大值.當(dāng)兩個(gè)節(jié)點(diǎn)都取兩端(1, 82)或中間(41, 42)時(shí), 特征值達(dá)最小值.也就是說對于鏈狀圖最優(yōu)節(jié)點(diǎn)接近在1/4 和3/4 的位置.例如取N = 302的鏈, 經(jīng)計(jì)算最優(yōu)節(jié)點(diǎn)為(76, 227), 也符合上述1/4 和3/4 的規(guī)律.

圖6 λ 1(LN?2) 與左節(jié)點(diǎn)位置(兩節(jié)點(diǎn)對稱選取)的關(guān)系圖, 這里N = 82Fig.6.The relationship of λ 1(LN?2) and the left node’s position, where N = 82 and the two nodes are selected symmetrically.

圖7 在正方形網(wǎng)格中選兩個(gè)最重要的節(jié)點(diǎn), 見圖中紅色的點(diǎn) (a) 24 × 24 的正方形網(wǎng)格; (b) 31 × 31 的正方形網(wǎng)格; (c) 40 ×40 的正方形網(wǎng)格; (d) 45 × 45 的正方形網(wǎng)格Fig.7.Pinning two nodes in a square lattice.The optimal options are shown by red nodes: (a) The square with 24 × 24 nodes;(b) the square with 31 × 31 nodes; (c) the square with 40 × 40 nodes; (d) the square with 45 × 45 nodes.

圖8 正方形網(wǎng)絡(luò)選4 個(gè)最重要的節(jié)點(diǎn), 見圖中紅色的點(diǎn) (a) 24 × 24 正方形網(wǎng)格; (b) 27 × 27 正方形網(wǎng)格; (c) 32 × 32 正方形網(wǎng)格Fig.8.Pinning four nodes in a square lattice.The optimal options are shown by red nodes: (a) The square with 24 × 24 nodes;(b) the square with 27 × 27 nodes; (c) the square with 32 × 32 nodes.

例4尋找正方形網(wǎng)絡(luò)中最重要的2 個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)組.在正方形網(wǎng)格中選兩個(gè)最重要的節(jié)點(diǎn)使得 λ1(LN?2) 最大.圖7 中紅色的點(diǎn)是計(jì)算得到的最優(yōu)位置.從圖7 發(fā)現(xiàn), 控制節(jié)點(diǎn)處于對稱位置, 卻并不一定處于對角線上.

接著, 在正方形網(wǎng)絡(luò)中尋找最重要的4 個(gè)節(jié)點(diǎn), 發(fā)現(xiàn)找到的最優(yōu)節(jié)點(diǎn)組也處于對稱位置, 但多數(shù)情況都不是位于對角線上, 大正方形網(wǎng)絡(luò)分成4 個(gè)小正方形網(wǎng)絡(luò), 最優(yōu)控制節(jié)點(diǎn)在4 個(gè)小正方形找中心節(jié)點(diǎn)偏移一格的位置上, 見圖8(a)和圖8(c)所示情形; 也有落在對角線上的情形, 見圖8(b).

例5社團(tuán)的重要性.比較三個(gè)社團(tuán)在網(wǎng)絡(luò)中的重要性, 見圖9, 其中紅色8 個(gè)節(jié)點(diǎn), 藍(lán)色7 個(gè)節(jié)點(diǎn), 綠色6 個(gè)節(jié)點(diǎn).它們的Laplacian 矩陣的刪后主子矩陣最小特征值分別為0.1905, 0.1792, 0.1597,說明紅色組最重要, 其次為藍(lán)色, 最后為綠色.

圖9 比較三個(gè)社團(tuán)在網(wǎng)絡(luò)中的重要性, 圖中紅藍(lán)綠色標(biāo)識了三個(gè)社團(tuán), 該圖取自文獻(xiàn)[24]Fig.9.Compare the importance of three communities in a network, in which red, blue, and green colors implicit three different communities.This network is taken from Ref.[24].

6 結(jié) 論

復(fù)雜網(wǎng)絡(luò)的牽制控制優(yōu)化是一個(gè)十分有意義的研究方向.但是由于控制多個(gè)節(jié)點(diǎn)時(shí)的最優(yōu)受控節(jié)點(diǎn)集的選擇是一個(gè)NP-hard 問題, 如何找出最優(yōu)受控節(jié)點(diǎn)集是一個(gè)富有挑戰(zhàn)性的問題, 本文正是基于此開展工作.基于Laplacian 刪后矩陣的圖譜性質(zhì), 提出了選擇最優(yōu)受控節(jié)點(diǎn)集的算法, 該算法在受控節(jié)點(diǎn)數(shù)較少(小于等于6)時(shí), 能夠準(zhǔn)確地找到最優(yōu)的受控節(jié)點(diǎn)集合.進(jìn)一步, 本文提出復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)組重要性的問題, 這與以往定義網(wǎng)絡(luò)節(jié)點(diǎn)重要性不同: 本文所提出的節(jié)點(diǎn)組重要性, 節(jié)點(diǎn)的選取依賴于節(jié)點(diǎn)組所包含節(jié)點(diǎn)的數(shù)目;節(jié)點(diǎn)組包含節(jié)點(diǎn)的數(shù)目不同, 會有不同的重要節(jié)點(diǎn)選擇方案及排序.在以后的研究中, 我們將分析牽制控制策略及節(jié)點(diǎn)組重要性在多層網(wǎng)絡(luò)[25]中的情況, 并希望進(jìn)一步挖掘節(jié)點(diǎn)組重要性在實(shí)際網(wǎng)絡(luò)中的應(yīng)用.