杜亞星，魯富榮，仇智鵬，錢宇華+

1.山西大學 大數(shù)據(jù)科學與產業(yè)研究院，太原 030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006

3.山西大學 計算機與信息技術學院，太原 030006

1 引言

控制復雜系統(tǒng)是人們對復雜系統(tǒng)模型結構及相關動力學進行研究的最終目標，具有廣泛的應用價值，例如控制網絡上的同步、控制疾病和謠言的傳播等，引起眾多學者的廣泛關注。Liu等人[1]基于結構可控理論[2]，首次提出了控制復雜網絡系統(tǒng)的方法，并且取得了很多重要的研究成果。然而在實際中，通常缺乏有效的技術和工具來實現(xiàn)復雜網絡的有效控制[3-8]。

通過結構可控性理論和最大匹配方法[9-10]，人們能夠確定控制一個網絡所需的最小的驅動節(jié)點數(shù)目[11]。對于工程系統(tǒng)，如自動駕駛飛機系統(tǒng)，結構控制是至關重要的。然而，許多生物、技術和社會系統(tǒng)是巨大的和復雜的[12]，對它們實現(xiàn)結構控制既不可行，也不必要。因此，在一個選定的任務中控制一個系統(tǒng)的目標節(jié)點是至關重要的。在生物、化學工程[13]、傳播學[14]和經濟網絡[15]確定一組最小的驅動節(jié)點方法滿足任意的目標控制復雜的網絡，仍然是一個懸而未決的問題[16]。

由于現(xiàn)有的復雜網絡節(jié)點重要性的單一評價指標存在局限性，并且節(jié)點在復雜網絡中的重要性不僅僅受單一因素的影響，可以采用一種基于多屬性決策的節(jié)點重要性綜合評價方法[17]。運用此方法可以有效地找出整個網絡中比較重要的節(jié)點，對其進行目標控制，其所需的驅動節(jié)點數(shù)目在很大程度上比單一指標所需的數(shù)目少。

2 目標控制理論

與結構控制理論不同，目標控制不會對整個網絡的所有節(jié)點加以控制，而是旨在選擇并控制網絡中的部分節(jié)點。本文將主要研究線性時不變系統(tǒng)的目標控制[18]。對于以下一個線性時不變系統(tǒng)：

其中，x∈RM，u∈RM和y∈RS分別代表系統(tǒng)的初始狀態(tài)、輸入和輸出向量。A∈RN×N,B∈RN×M和C∈RS×N分別代表系統(tǒng)的狀態(tài)、輸入和輸出矩陣。A是網絡系統(tǒng)的鄰接矩陣，B代表輸入外部信號后哪些節(jié)點被控制，u是對矩陣B施加的獨立不相干的控制輸入，C是需要控制的目標節(jié)點的輸出矩陣。

給定一個特定的網絡N={1,2,…N},θ={c1,c2,…,cs}為所需要控制的目標節(jié)點集，其中S=|C|=fN。C=[I(c1),I(c2),…,I(cs)]表示輸出矩陣，其中I(ci)表示一個N×N單位矩陣的第I行。系統(tǒng)(A,B,C)是否可控定義如下：對于一個給定的目標節(jié)點集，如果存在相互獨立的輸入向量u(t)=(u1(t),u2(t),…,uM(t))Τ，能夠使得驅動節(jié)點在有限的時間間隔內從任意的初始狀態(tài)到達任意想要的最終狀態(tài)。

系統(tǒng)(A,B,C)是可控的當且僅當輸出可控子集的維度滿足：

以上給出了目標可控的數(shù)學條件。如果S=N，C是單位矩陣，式（2）和結構控制一樣滿足Kalman可控條件[18]。

3 節(jié)點重要性

重要節(jié)點是指相比網絡其他節(jié)點而言，能夠在更大程度上影響網絡結構與功能的一些特殊節(jié)點。重要節(jié)點一般數(shù)量非常少，但其影響卻可以快速地波及到網絡中大部分節(jié)點[19]。例如，在對一個無標度網絡的蓄意攻擊中，少量最重要節(jié)點被攻擊就會導致整個網絡瓦解[20]；微博中最有影響力的幾個用戶所發(fā)的微博很快就能傳遍整個網絡[21]；僅僅1%的公司卻控制著40%的全球經濟?？梢娭匾?jié)點對網絡的結構和功能有著巨大的影響。因此，在一個網絡中選出重要的節(jié)點并對它們進行目標控制意義重大[22]。

3.1 單一評價指標

目前，學術界已經提出很多衡量節(jié)點重要性的單一評價指標。然而，在復雜網絡中，僅僅依賴于單一指標來判斷節(jié)點在網絡中的重要程度具有很大的片面性[17]。需要從不同的角度，利用節(jié)點的多個重要性指標來進行綜合評價。

進行綜合評價時，首先要對可用的評價指標進行篩選。本文基于“逼近理想排序法”[23]的多屬性決策方法，對網絡中單個節(jié)點的度中心性、介數(shù)中心性、接近中心性、PageRank[24-25]這4個指標作為決策評價方案的屬性進行綜合計算。度中心性對于有向網絡來說，每個節(jié)點的度分為出度和入度，這里僅對入度中心性進行分析，也就是說，只考慮進入一個節(jié)點的流通量以及它的接收信息的能力；對于介數(shù)中心性和接近中心性，其基礎思想都是按照最短路徑定義的，最短路徑算法對有向網絡是適用的，因此可以對其進行相應的修改使其適用于有向網絡；Page-Rank本身就可以對有向網絡進行計算。

（1）入度中心性（degree centrality）

節(jié)點i的度ki定義為與該節(jié)點連接的其他節(jié)點的數(shù)目。入度中心性定義為節(jié)點i的入度與該節(jié)點可能存在的最大邊數(shù)的比率。入度中心性可由式（3）計算：

其中，N為節(jié)點數(shù)量；表示網絡中進入節(jié)點i的邊數(shù)。入度中心性定義表明了一個節(jié)點接收其他節(jié)點信息通信的能力，數(shù)值越大，在網絡中越重要。

（2）介數(shù)中心性（betweenness centrality）

節(jié)點i的介數(shù)定義為網絡中節(jié)點對j與k之間最短路徑經過節(jié)點i的條數(shù)占所有最短路徑數(shù)的比例。若gjk(i)表示節(jié)點對j與k之間經過節(jié)點i的條數(shù)，njk表示節(jié)點對j與k之間存在的所有最短路徑的條數(shù)，則介數(shù)中心性可表示為：

介數(shù)中心性的值越大，表示該節(jié)點在網絡中的影響力越大。

（3）接近中心性（closeness centrality）

節(jié)點i的接近中心性定義為其到網絡中其他所有節(jié)點距離之和的倒數(shù)。實際網絡并不都是完全連通的，將接近中心性用以下公式表示，同樣適合不連通復雜網絡的情形，其表達式為：

如果節(jié)點vi和vj之間沒有路徑可達，則定義dij=∞，即1/dij=0。N為節(jié)點數(shù)量，dij表示以節(jié)點i為起點，以j為終點的最短路徑中所含邊的數(shù)量[25]。接近中心性越大，表示節(jié)點越居于復雜網絡的中心位置。

（4）PageRank

PageRank算法認為萬維網中一個頁面的重要性取決于指向它的其他頁面的數(shù)量和質量。初始時刻，賦予每個節(jié)點（網頁）相同的PR值，然后進行迭代，每一步把每個節(jié)點當前的PR值平分給它所指向的所有節(jié)點。修正的PageRank算法在上述過程基礎上引入一個隨機跳轉概率c。每一步，不管一個節(jié)點是否為懸掛節(jié)點（出度為0的節(jié)點），其PR值都將以c的概率均分給網絡中所有節(jié)點，以1-c的概率均分給它指向的節(jié)點。每個節(jié)點更新后的PR值為它所獲得的PR值之和，因此節(jié)點vi在t時刻的PR值為：

其中，kojut為節(jié)點vj的出度。針對萬維網的網頁排序，研究顯示c=0.15是一個比較好的參數(shù)。節(jié)點的PR值越大，表示節(jié)點越重要。

基于以上4個指標，本文將建立一種基于多屬性決策的節(jié)點重要性評價方法。

3.2 綜合評價體系

基于多屬性決策的節(jié)點重要性綜合評價方法，其基本思想是將復雜網絡中的每一個節(jié)點看作一個方案，將評價節(jié)點重要性的多個評價指標分別看作各方案的屬性，從而將節(jié)點重要性的評價問題轉化為一個多屬性決策問題，決策的準則是評價各方案在復雜網絡中的重要程度。

假設復雜網絡中有N個節(jié)點，用集合P={P1,P2,…,PN}表示，每個節(jié)點特性指標有M個，用集合Q={Q1,Q2,…,QM}來表示，則此網絡中的第i個節(jié)點的第j個指標可用Pi(Qj)(i=1,2,…,N;j=1,2,…,M)來表示，則節(jié)點的多屬性（指標）矩陣可表示為:

上述所選指標（入度中心性DC、介數(shù)中心性BC、接近中心性CC和PageRankPR）均為效益型指標，即值越大表示該節(jié)點越重要，因此需要對矩陣X做歸一化，得到R=(rij)N×M，其中：

根據(jù)層次分析法（analytic hierarchy process，AHP）[26]，并經過一致性經驗，為節(jié)點重要性多屬性評價模型的各個指標賦予權重：首先經過比較計算建立一個比較矩陣B；然后通過變換將比較矩陣轉化為判斷矩陣，并進行一致性檢驗；最后得到指標權重。參照文獻[15]對比較矩陣的值做了調整，見表1。

Table 1 Value of comparison matrix表1 比較矩陣的值

表1中：

對比較矩陣B的構建基于以下因素考慮：因為度中心性在有向網絡中涉及的網絡結構因素最少，所以和其他指標相比重要性較差；介數(shù)中心性和接近中心性均基于最短路徑理論，很難對比兩個指標的好壞，在矩陣B中給出了重要性相同的評價；Page-Rank和其他3個指標相比，針對有向網絡可以準確地找出網絡中相對重要的節(jié)點，因此本文在比較矩陣B的構造中給PageRank賦予了比其他指標更高的值。

對比較矩陣B按照極差法構造判斷矩陣[26]，經一致性檢驗，得到各相關指標權重的值分別為wDC=0.086 1,wBC=0.207 3,wCC=0.207 3,wPR=0.499 3。

設第j個指標的權重為wj(j=1,2,…,m,∑wj=1)，該向量和規(guī)范化決策矩陣R構成加權規(guī)范化矩陣：

采用理想方案[23]對每個節(jié)點的重要性進行評估，計算公式如下：

其中，與可通過歐式范數(shù)計算得到：=為矩陣Y每列中的最大值，yminj為矩陣Y每列中的最小值。

計算理想方案的值Ki，按照Ki值的大小進行重要度排序，完成評估任務。經過上述處理，Ki值越大表示節(jié)點在網絡中的重要程度越高。

4 實驗分析

4.1 在真實網絡上的實驗分析

基于以上理論，對不同類型的真實數(shù)據(jù)分別按DC、BC、CC、PR和綜合指標對節(jié)點的重要性進行計算排序，從大到小選取前10%的節(jié)點，把它們當作目標節(jié)點分別進行控制，用目標控制算法在整個網絡中控制這些目標節(jié)點，然后分析驅動節(jié)點的數(shù)量。結果如表2所示，其中黑色加粗下劃線數(shù)字表示效果差的方法所需要的驅動節(jié)點數(shù)目。

表2中Type為數(shù)據(jù)類型，Name為數(shù)據(jù)名稱，N和L是節(jié)點和邊的數(shù)量，ND是控制整個網絡所需要的驅動節(jié)點數(shù)目，這個結果和結構可控理論運用最大匹配算法得出的結果一致；n為分別對各個數(shù)據(jù)選取10%節(jié)點的數(shù)目（即各個數(shù)據(jù)在整個網絡中需要控制的目標節(jié)點數(shù)目）；DC、BC、CC、PR和AD是按各自的指標值進行排序選取前10%的節(jié)點作為目標節(jié)點進行控制時得出的驅動節(jié)點的數(shù)目（AD為綜合指標下計算得出的驅動節(jié)點數(shù)目）。從表2中可以看出，對于大部分數(shù)據(jù)來說，綜合性指標比其他單一指標得出的驅動節(jié)點的數(shù)量都少。

Table 2 Driver nodes based on single index and integrated index表2 基于單一指標及綜合指標所得到的驅動節(jié)點數(shù)

可以看出，各個數(shù)據(jù)在綜合性指標下計算得出的驅動節(jié)點數(shù)目大部分都比單一指標低。雖然有個別指標，例如介數(shù)中心性BC對于數(shù)據(jù)WikiVote比綜合性指標低，但是對于其他數(shù)據(jù)，驅動節(jié)點數(shù)目的結果并不是很理想。其他指標如入度中心性DC、接近中心性CC以及PageRank值PR等單一指標的結果均類似這種情況，對于大部分數(shù)據(jù)來說綜合指標情況下驅動節(jié)點數(shù)量均相對較少。因此在綜合性指標能夠有效地選取出網絡中重要節(jié)點的基礎上，達到了整體而言驅動節(jié)點數(shù)目相對最少。

4.2 在人工生成網絡上的實驗分析

為了研究平均度＜k＞和冪律γ對驅動節(jié)點數(shù)目的影響，將4.1節(jié)的分析過程運用到無標度網絡和ER隨機模型網絡中。

圖1是無標度網絡的處理結果，縱坐標均是控制模型網絡所需驅動節(jié)點數(shù)量與網絡目標節(jié)點數(shù)量的比值。圖1中橫坐標＜k＞和γ分別代表平均度和冪律，縱坐標ratio代表驅動節(jié)點與目標節(jié)點的比率。圖（a）和（c）為基于結構控制理論即控制整個網絡（10 000個節(jié)點）的結果，圖（b）和（d）是基于目標控制理論對網絡選取的10%重要節(jié)點（1 000個節(jié)點）進行目標控制的結果。所有實驗結果都是重復做了10次取平均值。

圖2是ER隨機網絡的處理結果，縱坐標依舊是控制模型網絡所需驅動節(jié)點數(shù)量與網絡目標節(jié)點數(shù)量的比值。橫坐標＜k＞代表平均度，縱坐標ratio代表驅動節(jié)點與目標節(jié)點的比率。圖（a）為基于結構控制理論即控制整個ER網絡（10 000個節(jié)點）的結果，圖（b）則是基于目標控制理論對網絡選取的10%重要節(jié)點（1 000個節(jié)點）進行目標控制的結果。所有實驗結果都是重復做了10次取平均值。

圖1（a）說明，網絡冪律γ一定時，隨著網絡平均度＜k＞的增大，結構控制時驅動節(jié)點與網絡節(jié)點的比值逐步降低，即所需驅動節(jié)點的數(shù)量在減少；網絡平均度＜k＞一定時，冪律γ越大，比值越小，驅動節(jié)點的數(shù)量越小。

Fig.1 Scale-free network processing results圖1 無標度網絡的處理結果

Fig.2 ER network processing results圖2 ER隨機網絡的處理結果

圖1 （b）說明，網絡冪律γ一定時，隨著＜k＞增大，目標控制時驅動節(jié)點與目標節(jié)點的比值整體先下降后上升；對于不同的冪律值又有不同的變化，γ=2.4時，曲線先上凸后下凹；而γ=5.0時，曲線先下凹后上凸。

圖1（c）表明，網絡平均度＜k＞一定時，隨著冪律γ增大，結構控制時驅動節(jié)點與網絡節(jié)點的比值逐步降低，所需驅動節(jié)點的數(shù)量減少；冪律值γ一定時，平均度＜k＞越大，比值越小，驅動節(jié)點的數(shù)量反而越小。

圖1（d）表明，平均度 ＜k＞=5時，隨著冪律γ增大，目標控制時驅動節(jié)點與目標節(jié)點的比值曲線先下凹后上凸，當＜k＞逐漸增大，所需驅動節(jié)點的數(shù)量逐漸上升，并且驅動節(jié)點與目標節(jié)點的比值逐漸趨于1，當＜k＞=16時，比值幾乎完全為1?？梢缘贸?，當網絡異常稠密時，目標控制所需驅動節(jié)點數(shù)目即為目標節(jié)點的數(shù)目；當網絡冪律γ一定時，隨著平均度＜k＞的增大，目標控制時驅動節(jié)點與目標節(jié)點的比值增加，所需驅動節(jié)點數(shù)量增加。

對于圖1（d），正是由于只選取了10%的目標節(jié)點（其選取數(shù)量為1 000），驅動節(jié)點數(shù)量大部分密集在950～1 000之內，從而驅動節(jié)點與目標節(jié)點比例也集中在[0.95,1.00]區(qū)間內，則縱坐標值很接近，導致個別數(shù)據(jù)波動時被放大，實際曲線變化的趨勢為開始時下降，然后逐漸上升，整體趨勢是很明顯的。

由圖2（a）可以看出，隨著網絡平均度的增大，通過結構匹配算法控制整個網絡所需驅動節(jié)點減少；從圖2（b）看出，隨著網絡平均度的增大，目標控制時所需驅動節(jié)點增加。由此可以得出，對于越稠密的ER隨機網絡，目標控制時所需的驅動節(jié)點越多。

5 結束語

本文在目標控制中提出一種基于多屬性決策的節(jié)點重要性綜合評價方法，以此來選取重要的節(jié)點進行目標控制。在真實網絡與人工生成網絡上進行實驗，通過綜合性指標選取10%的節(jié)點。結果表明，在真實網絡上，通過綜合性指標得出的驅動節(jié)點數(shù)量明顯整體比單一指標少；在人工生成網絡上，無論對于無標度網絡還是ER隨機網絡，驅動節(jié)點與目標節(jié)點數(shù)量的比值曲線整體的趨勢是一個上升的過程。此外，對于上述兩種網絡，平均度越大，即當網絡越稠密時，目標控制所選出的重要節(jié)點需要的驅動節(jié)點越多。

[1]Liu Yangyu,Slotine J J,BarabásiAL.Controllability of complex networks[J].Nature,2011,473(7346):167-173.

[2]Lin C T.Structural controllability[J].IEEE Transactions on Automatic Control,1974,19(3):201-208.

[3]Yuan Zhengzhong,Zhao Chen,Di Zengru,et al.Exact controllability of complex networks[J].Nature Communications 2013,4:2447.

[4]Gong De'en.An introduction to the economic cybernetics[M].Beijing:China Renmin University Press,1988.

[5]Zheng Dazhong.Linear system theory[M].Beijing:Tsinghua University Press,1990.

[6]Guan Zhizhong,Xia Gongke,Meng Qiao.Signal and linear system[M].Beijing:People's Education Press,1982.

[7]Rugh W J.Linear system theory[M].Upper Saddle River:Prentice-Hall,1996.

[8]Chen C T.Linear system theory and design[M].Oxford:Oxford University Press,1995.

[9]Lovasz L.Matching theory(North-Holland mathematics studies)[M].Oxford:Elsevier Science Ltd,1986.

[10]Hopcroft J E,Karp R M.Ann5/2algorithm for maximum matchings in bipartite graphs[J].SIAM Journal on Computing,1973,2(4):225-231.

[11]Kuchtey J,Fulton S A,Reba S M,et al.Interferon-αβ mediates partial control of early pulmonary mycobacterium bovis,bacillus Calmette-Guérin infection[J].Immunology,2006,118(1):39-49.

[12]Kalman R E.Mathematical description of linear dynamical systems[J].Journal of the Society for Industrial&Applied Mathematics,1963,1(2):152-192.

[13]Baldea M,Daoutidis P.Model reduction and control of reactorheat exchanger networks[J].Journal of Process Control,2006,16(3):265-274.

[14]Cohen R,Havlin S,Ben-Avraham D.Efficient immunization strategies for computer networks and populations[J].Physical Review Letters,2004,91(24):247901.

[15]Galbiati M,Delpini D，Battiston S.The power to control[J].Nature Physics,2013,9(3):126-128.

[16]Xie Guangming,Wang Long.Controllability and stabilizability of switched linear-systems[J].Systems&Control Letters,2003,48(2):135-155.

[17]Yu Hui,Liu Zun,Li Yongjun.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):020204.

[18]Gao Jianxi,Liu Yangyu,D'Souza R M,et al.Target control of complex networks[J].Nature Communications,2014,5:5415.

[19]Albert R,Jeong H,Barabási A L.Error and attack tolerance of complex networks[J].Nature,2000,406:378-382.

[20]Cohen R,Erez K,Ben-Avraham D,et al.Breakdown of the Internet under intentional attack[J].Physical Review Letters,2001,86(16):3682.

[21]Weng Jianshu,Lim E P,Jiang Jing,et al.Twitterrank:finding topic-sensitive influential Twitterers[C]//Proceedings of the 3rd International Conference on Web Search and Web Data Mining,New York,Feb 4-6,2010.New York:ACM,2010:261-270.

[22]Hou Lvlin,Lao Songyang,Xiao Yandong,et al.Recent progress in controllability of complex network[J].Acta Physica Sinica,2015,64(18):477-487.

[23]Dedania H V,Shah V R,Sanghvi R C.Portfolio management:stock ranking by multiple attribute decision making methods[J].Technology&Investment,2015,6(4):141-150.[24]Qin Li,Yang Zilong,Huang Shuguang.Synthesis evaluation method for node importance in complex networks[J].Computer Science,2015,42(2):60-64.

[25]Ren Xiaolong,Lv Linyuan.Review of ranking nodes in complex networks[J].Chinese Science Bulletin,2014,13:1175-1197.

[26]Zhu Yin,Meng Zhiyong,Kan Shuyu.Determination of weight value by AHP[J].Journal of Northern Jiaotong University,1999,23(5):119-122.

附中文參考文獻：

[4]龔德恩.經濟控制論概論[M].北京:中國人民大學出版社,1988.

[5]鄭大鐘.線性系統(tǒng)理論[M].北京:清華大學出版社,1990.

[6]管致中,夏恭恪,孟橋.信號與線性系統(tǒng)[M].北京:人民教育出版社,1982.

[17]于會,劉尊,李勇軍.基于多屬性決策的復雜網絡節(jié)點重要性綜合評價方法[J].物理學報,2013,62(2):020204.

[22]侯綠林,老松楊,肖延東,等.復雜網絡可控性研究現(xiàn)狀綜述[J].物理學報,2015,64(18):477-487.

[24]秦李,楊子龍,黃曙光.復雜網絡的節(jié)點重要性綜合評價[J].計算機科學,2015,42(2):60-64.

[25]任曉龍,呂琳媛.網絡重要節(jié)點排序方法綜述[J].科學通報,2014(13):1175-1197.

[26]朱茵,孟志勇,闞叔愚.用層次分析法計算權重[J].北京交通大學學報,1999,23(5):119-122.