復雜網(wǎng)絡牽制控制優(yōu)化選點算法及節(jié)點組重要性排序*

劉慧 王炳珺 陸君安 李增揚

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

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

3) (華中師范大學計算機學院, 武漢 430079)

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

1 引 言

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

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

2 模型介紹及問題提出

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

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

假設網(wǎng)絡的目標狀態(tài)s(t)滿足:

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

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

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

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

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

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

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

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

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

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

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

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

則必須有

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

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

算法1

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

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

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

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

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

4 實驗仿真及算法有效性分析

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

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

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

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

圖1 生成 的BA 網(wǎng) 絡.不同顏色代表節(jié)點的度的大小,紅色表示度大的節(jié)點, 藍色表示度小的節(jié)點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.

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

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

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

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

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

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

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

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

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

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

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

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

4.3 本文算法與其他選點策略的對比

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

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

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

表5 不同算法在Email 網(wǎng)絡中的選點及 λ 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)絡的選點情況 (a)度算法選點情況; (b) BC 算法選點情況; (c) ESI 算法選點情況; (d)本文算法選點情況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)絡的選點情況 (a) 度算法選點情況; (b) BC 算法選點情況; (c) ESI 算法選點情況; (d) 本文算法選點情況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.

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

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

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

圖4 兩個網(wǎng)絡A 與B 結構不同, 但刪去節(jié)點4 后網(wǎng)絡相同 (a) 網(wǎng)絡A 及其Laplacian 矩陣; (b) 網(wǎng)絡A 刪除節(jié)點4 及其Laplacian 矩陣; (c) 網(wǎng)絡B 及其Laplacian 矩陣; (d)網(wǎng)絡B 刪除節(jié)點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 說明刪后主子矩陣及其特征值蘊含了原矩陣的隱藏信息.

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

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

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

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

在該網(wǎng)絡中, 對于一個節(jié)點的重要性排序, 節(jié)點1, 2, 3 的 λ1(LN?l) 分 別 為 0.1206, 0.1981,0.3820, 所以單個節(jié)點排序中節(jié)點3 最重要, 節(jié)點2 和4 其次, 節(jié)點1 和5 最差.對于兩個節(jié)點的節(jié)點組重要性排序: 節(jié)點組(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(最不重要).這一簡單例子也說明, 單個節(jié)點排序最重要的節(jié)點不一定包含在兩個節(jié)點的節(jié)點組的第一位.

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

圖6 λ 1(LN?2) 與左節(jié)點位置(兩節(jié)點對稱選取)的關系圖, 這里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)格中選兩個最重要的節(jié)點, 見圖中紅色的點 (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)絡選4 個最重要的節(jié)點, 見圖中紅色的點 (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)絡中最重要的2 個節(jié)點組成的節(jié)點組.在正方形網(wǎng)格中選兩個最重要的節(jié)點使得 λ1(LN?2) 最大.圖7 中紅色的點是計算得到的最優(yōu)位置.從圖7 發(fā)現(xiàn), 控制節(jié)點處于對稱位置, 卻并不一定處于對角線上.

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

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

圖9 比較三個社團在網(wǎng)絡中的重要性, 圖中紅藍綠色標識了三個社團, 該圖取自文獻[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 結 論

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