度相關性對復雜網絡目標控制的影響*

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

1.山西大學 大數據科學與產業研究院，太原 030006

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

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

1　引言

隨著對復雜網絡的深入研究，復雜網絡的結構、演化以及動力學問題已經獲得許多重要的突破[1-4]。對于復雜網絡動力學性質的研究，其最終目標是如何控制一個網絡以達到期待的目標狀態。復雜網絡的可控性問題是近年來提出的重要研究熱點之一。復雜網絡控制方面主要的工作包括牽制控制[5-6]和結構控制[3,7]等。近期的工作主要包括復雜網絡的可觀測性[8]、目標可控性[9]、控制能量[10]、精確可控性[11]及多層網絡的結構和動力學性質[12]等方面的研究[13-19]。對于復雜網絡而言，控制的目的是如何通過恰當的輸入在有限時間內使得網絡在自身動力學機制下演化到任意想要的狀態[20-21]。2011年，Liu等人[3]通過將復雜網絡的完全可控問題轉化為圖論中的最大匹配問題，找到了控制網絡的最少驅動節點數。2013年，Yuan等人[11]基于可控性的PBH秩判據提出了對于復雜網絡的精確控制，從而簡化了對于無向復雜網絡驅動節點數的計算。然而，對于真實網絡而言，對整個網絡進行完全控制有時是費時費力的，甚至是不可行的，例如微生物網絡和一些社會網絡，它們規模龐大且結構復雜。出于這個考慮，Gao等人[9]基于結構控制理論，利用貪婪算法提出了對網絡的目標控制。該算法首先選擇一部分節點作為需要控制的目標節點，再通過迭代使用匹配算法最終找到了驅動該部分目標節點達到理想狀態的最小驅動節點及其數目。

度相關性[22]是刻畫網絡屬性的一個重要指標，反映節點與其相鄰節點之間度的聯系。本文考慮的是有向網絡的度相關性，具體為入度-入度相關性、入度-出度相關性、出度-入度相關性、出度-出度相關性。如果網絡中兩個節點的邊連接情況與兩個節點的度值無關，稱網絡不具有度相關性。如果度值較大的節點傾向于連接度值較大的節點，那么就稱這個網絡是同配的。反之，如果度值較大的節點傾向于連接度值相對較低的節點，那么就稱這個網絡是異配的。

由于復雜網絡節點數目多，連邊復雜度高，不能像低維小系統一樣通過遍歷的方法來尋找控制輸入位置。因此，如何有效地確定所需要獨立控制的節點數目和控制輸入的位置，以滿足復雜網絡可控性的要求就成為網絡控制需要解決的首要問題。對于控制而言，除了探究其控制的機理，提出有效的控制手段之外，探究影響該控制方法效率的因素也是一個重要的方面。度相關性對于復雜網絡結構可控具有重要的影響已經被證實[23]。在真實網絡中，例如電力網絡、生物網絡，其度相關性呈現出一定的異配性，而社會網絡呈現出一定的同配性，網絡的同配性與異配性會影響這些網絡控制的效率。而目標控制是采用貪婪算法，在結構控制的基礎上實現對于網絡部分節點的控制，因此本文選取度相關性作為目標控制的影響因素進行研究。探究復雜網絡目標控制的影響因素，能夠更好地認識網絡的拓撲結構對于網絡目標控制的影響，同時也能夠在此基礎上改進網絡使得網絡更易于被目標控制。

本文探究了各種度相關性對于目標控制效率的影響。實驗結果表明在目標控制的機制下，出度-入度相關性對網絡的目標控制效率影響較大，而隨著出度-入度相關性的逐步增加，驅動節點比例呈逐步下降趨勢。

2　相關內容

2.1　目標控制

本文采用的目標控制策略是由Gao等人[9]提出的，研究的是線性時不變系統的目標控制：

其中，x∈RN,u∈RM,y∈RS，這3個變量分別代表了系統的狀態向量、輸入向量以及輸出向量。A∈RN×N，B∈RN×M，C∈RS×N，分別表示狀態矩陣、輸入矩陣以及輸出矩陣。A描述的是系統的線性連接關系；B決定了外部輸入信號與網絡節點之間的連接關系；u是隨時間變化的輸入信號；C是所需要控制的目標節點。對于一個具有N個節點的網絡N={1,2,…,N}，所需要控制的目標節點集合是C={c1,c2,…,cS}，其中，S=|C|=fN。表示輸出的矩陣C=[I(c1),I(c2),…,I(cS)]，其中I(i)表示一個N×N單位矩陣的第i行。如果給定一個時變的輸入向量u(t)=(u1(t),u2(t),…,uM(t))T，這樣一個輸入向量可以使得目標節點變成任意期望的最終狀態，那么就說這個系統是目標可控的。目標控制可以被看作一種（A,B,C）特殊的輸出可控，而且在滿足如下條件的情況下：

如果滿足（2），對于任意的初始狀態x(0)，就可以計算出最優化的輸入向量u(t)使得網絡可以在有限時間tˉ>0達到任意最終狀態yˉ，也就是說最終y(tˉ)≡yˉ。

為了解決目標控制問題，采用“K-walk theory”。該理論的原理是：一個節點可以控制這樣的一組目標節點，即從驅動節點到任意目標節點的路徑長度是互不相同的。使用“K-walk theory”就可以確定這樣的一個受控節點的集合。對于需要超過一個控制輸入的網絡，采用貪婪算法（圖1），來找到最少的輸入節點。圖1（a）中對一個小型網絡施加目標控制。網絡中一共7個節點，其中節點{x3,x4,x6,x7}為目標節點（紅圈標出）。在圖1（b）中使用貪婪算法來解決網絡的目標控制問題。首先，將原網絡映射成一個二分圖的形式。目標節點是{x3,x4,x6,x7}，通過紅線所示的第一次迭代之后，找到匹配節點{x2,x3,x5,x6}，將這些節點作為第二次迭代的目標節點。通過3次迭代，最終得出{x1,x5}是{x3,x4,x6,x7}的驅動節點。

Fig.1　Progress of target control圖1　目標控制過程

2.2　度相關性

度相關性可以度量節點之間的連接趨勢，而且它可以有多種表示形式。本文采用皮爾遜相關系數刻畫度相關性：

2.3　度相關性影響

本文所研究的是度相關性對于網絡目標控制的影響。如圖2所示，從一個簡單的角度考慮一個網絡。在圖2（a）中，該矩陣為隨機重連之前網絡的連接矩陣，左半部分代表源節點（即有向邊的出節點），右半部分代表終節點（即有向邊的指入點）中N=7。圖2（b）展示的是隨機重連之后網絡的連接矩陣。

Fig.2　Connection matrix of networks before and after change圖2　網絡重連前后的連接矩陣

Fig.3　Effect of degree correlations on target control圖3　度相關性對目標控制驅動節點的影響

在圖3（a）～（d）中，所要控制的是{x3,x4,x6,x7}4個節點。圖（a）是初始網絡的連邊圖，圖（b）通過目標控制算法找出的網絡最終驅動節點{x1,x5}，圖（c）是隨機重連之后生成的網絡連邊圖，圖（d）為改變度相關性之后，通過目標控制算法找出的網絡最終驅動節點變為{x5}，從而使得驅動節點的數目降低。因此，網絡的目標可控性會受到度相關性的影響。

3　度相關性影響的實驗分析

3.1　模擬退火算法

為了探索度相關性對于復雜網絡目標控制的影響，本文采用模擬退火算法，使得在保持度分布不變的情況下，改變度相關性到任意期望的目標值。

（1）設定了初始溫度T和每個溫度下的迭代次數iter，以及能量函數E(r)=|r-r*|；

（2）采用隨機擾動的方法，每次從網絡中任取兩條邊，交換兩條連邊的終節點，該操作的目的是使得網絡中每個節點的出度和入度保持不變；

（3）計算出E(r)的值，看是否小于閾值，如果小于閾值，則已經達到所需要的r值范圍；

（4）繼續迭代，直到達到所需要的r值范圍，或者溫度T小于所設定的最小溫度t。

3.2　度相關性對E-R隨機網絡的實驗分析

圖4為在E-R隨機網絡中度相關性對目標控制的影響(nD=ND/(N×p))。其中，nD為目標控制驅動節點比例，ND為驅動節點數目，N為節點數，p為選擇的目標節點比例。本文研究的是度相關性對網絡目標控制的影響，因此每次隨機選取一半的節點(p=50%)為目標節點。該E-R隨機網絡的平均度為=1(red),=2(green),=3(blue),=5(black)。圖中每一個數據點為5次實驗取平均值。圖4（a）考慮了入度-入度相關性(rin-in)和驅動節點比例(nD)的關系；圖4（b）考慮了入度-出度相關性(rin-out)和驅動節點比例(nD)的關系；圖4（c）考慮了出度-入度相關性(rout-in)和驅動節點比例(nD)的關系；圖4（d）考慮了出度-出度相關性(rout-out)和驅動節點比例(nD)的關系。

實驗表明對于目標控制而言，在4種度相關性中，出度-入度相關性的影響最為明顯。

對于E-R隨機網絡，首先從入度-入度相關性角度來看，在網絡處于異配的情況(rin-in<0)，網絡中入度較大的節點連接網絡中入度較小的節點，而該入度較小的節點連接網絡中入度較大的節點。從形成匹配的角度來看，該結構會在形成二階路徑的過程中，浪費大量的入邊，從而抑制了網絡中其他匹配的形成，加大了網絡目標可控的難度。

Fig.4　Correlations betweennDand all kinds ofrin random network圖4　隨機網絡中驅動節點比例和各種相關性的關系

因此，網絡異配性較強(r<-0.3)時，網絡的驅動節點比例較大。通過模擬退火算法改變網絡的度相關性后，網絡在逐步變為同質網絡(rin-in>0)的過程中，相關性逐步上升，由二階路徑所帶來的對于匹配的抑制性降低，所以網絡驅動節點的比例逐步下降。而當網絡的入度-入度相關性逐步增加時，網絡中入度較高的節點相互連接，使得網絡中入邊存在較大的浪費，所以在度相關性增高的后半階段，目標控制的驅動節點比例逐步上升。因此，隨著網絡入度-入度相關性的增加，網絡的驅動節點比例首先會逐步降低，在網絡入度-入度相關性增高的后半階段，網絡驅動節點比例逐步上升。

從入度-出度相關性的角度來看，在求網絡中目標節點的驅動時，所考慮的是節點之間的匹配關系。以連邊兩端的節點考慮，對于源節點而言，考慮的是源節點的出度，而對于連邊另一端的節點，考慮的是其入度，以此衡量網絡中的匹配數目。這樣的一個匹配數目與網絡的入度-出度相關性幾乎無關，因此網絡的目標可控性對于網絡的入度-出度相關性沒有體現出很強的依賴關系。

從出度-入度相關性的角度來看，因為有向網絡的控制問題可以轉化為匹配問題，而匹配本身從源節點的角度看就是出邊，從終節點的角度看就是入邊，所以網絡本身體現出對于該相關性很高的依賴性。當網絡體現出很高的異配性時（網絡中節點的出度很高而入度很低時），因為該出度高的節點只能控制其中一個入度低的節點，所以想要控制其他入度低的節點就需要另外施加控制輸入，網絡的異配性對于網絡的目標可控體現出較高的抑制性。因此，對于目標控制而言，其驅動節點的比例會相對較高。反之，如果網絡有良好的同配性，則對于出度較低的節點，其入度也會較低，對于網絡中出邊或者入邊的利用率較高，在形成匹配的過程中，目標節點易處于一條有向路徑中。因此，當網絡同配性越來越高時，網絡的驅動節點比例會降低。

對于出度-出度相關性而言，網絡驅動節點的比例體現出和入度-入度相關性良好的吻合。因為如果將原網絡中所有的連邊反向，則網絡中的匹配性質不會發生變化，即網絡的驅動節點比例不會發生變化，此時網絡的出度-出度相關性等價于原來的入度-入度相關性，所以網絡的驅動節點比例與入度-入度相關性圖所體現出來的規律一致。

3.3　度相關性對S-F無標度網絡的實驗分析

如圖5所示，對于該無標度網絡，其平均度=1,=2,=3,=5,γ=3,N=5 000。目標節點的選擇也是每次隨機選擇總節點數目的一半(p=50%)。每一個數據點都是取了5次實驗的平均值。圖5表示了驅動節點比例和4種度相關性之間的關系。對于S-F無標度網絡而言，度相關性對于其影響表現出和E-R隨機網絡類似的性質。

Fig.5　Correlations betweennDand all kinds ofrin scale-free network圖5　無標度網絡中驅動節點比例和各種相關性的關系

從入度-入度相關性和出度-出度相關性的角度來看，在目標控制中，所體現的性質與E-R隨機網絡相差不大。然而，因為網絡為S-F無標度網絡，不考慮網絡中具體連邊的方向，網絡本身體現出較高的異配性，即使網絡的入度-入度相關性逐步增加，網絡本身也很難有較高的同配性，所以不容易構成入度-入度相關性對于網絡形成匹配的抑制，從而網絡在入度-入度相關性由-1到+1的過程中都保持驅動節點比例逐步降低。而當網絡的入度-入度相關性極高時，網絡中入度較高的節點相互連接，使得網絡中入邊存在較大的浪費，所以在度相關性接近+1的時候，目標控制的驅動節點比例存在上升的趨勢。因此，隨著網絡入度-入度相關性的增加，網絡的驅動節點比例首先會逐步降低，在網絡入度-入度相關性極高時，網絡驅動節點比例存在逐步上升的趨勢。

從入度-出度和出度-入度相關性的角度來看，入度-出度相關性對于網絡目標控制驅動節點比例幾乎沒有影響，而出度-入度相關性對S-F無標度網絡影響較大，且隨著出度-入度相關性的增加，驅動節點比例逐步降低。

3.4　真實網絡

本節用真實網絡數據檢驗相關性對于網絡目標控制效率的影響。所用的真實網絡的部分數據如表1所示，表格內從左到右的內容依次為真實網絡的編號、類型、名字、節點數目以及連邊數目。

Table 1　Data of real networks表1　真實網絡的數據

一共考慮了7個真實網絡，依舊隨機選擇總節點的一半節點(p=50%)作為目標節點，其中每個數據點重復5次實驗取平均值，所得出的關系如圖6所示。

對于選取的TRN-EC-Alon、TRN-EC-RDB64、TRNYeast-Alon而言，入度-入度相關性整體變化趨勢不明顯，但是在度相關性極高時驅動節點比例是增高的。而入度-出度相關性在該類型網絡上幾乎沒有影響。出度-入度相關性對于網絡驅動節點的比例影響較為明顯，隨著相關性的逐步增加，網絡的驅動節點比例逐步減少。由于真實網絡的限制，網絡在出度-出度相關性上無法有很大范圍的變化，然而在小范圍內的變化是伴隨度相關性的增加先降低后增高。

對于S420、S838網絡而言，從入度-入度的角度看，在度相關性為負時網絡的驅動節點比例浮動不大，而當度相關性取正值的時候網絡的驅動節點比例隨度相關性的增加而逐步上升。入度-出度相關性對于網絡驅動節點比例的影響不大。而伴隨網絡出度-入度相關性的增加，網絡的驅動節點比例迅速下降，對于出度-出度相關性而言，網絡體現出和入度-入度相關性良好的匹配，在負值時網絡的驅動節點比例變化不大，當網絡度相關性逐步變為+1的過程中，網絡驅動節點的比例逐步上升。

對于Dolphins、Prisoninmate網絡而言，伴隨著網絡入度-入度相關性的增加，網絡的驅動節點比例先是逐步下降，然后逐步上升。入度-出度相關性對其幾乎沒有影響，伴隨著出度-入度相關性的增加，網絡的驅動節點比例逐步降低。出度-出度相關性與入度-入度相關性的表現幾乎一致。

4　結論

通過對E-R隨機網絡、S-F無標度網絡和真實網絡的實驗數據分析，本文最終能得出各種度相關性對網絡目標控制效率影響的結論。

（1）對于絕大部分網絡而言，在入度-入度相關性由-1變為+1的過程中，網絡的驅動節點比例先是逐步降低，在度相關性為0的附近，網絡的驅動節點比例取得最低，并且在度相關性很小范圍內幾乎保持不變。隨后，當網絡的度相關性增大，網絡的驅動節點比例也隨之上升。

（2）入度-入度相關性，對于網絡目標控制的驅動節點比例幾乎沒有影響。

（3）出度-入度相關性，伴隨著出度-入度相關性的增大，網絡的驅動節點比例逐步降低，且該相關性對于網絡驅動節點比例的影響最大。

（4）出度-出度相關性，該相關性對于網絡目標控制驅動節點的比例影響與入度-入度相關性幾乎一致，都是隨著網絡度相關性的增大，驅動節點比例先降低后升高。

Fig.6　Correlations betweennDand all kinds ofrin real networks圖6　真實網絡中驅動節點比例和各種相關性的關系

5　展望

本文研究了在復雜網絡中，4種度相關性對于目標控制的影響，其中網絡的出度-入度相關性對于網絡的目標可控性具有較強的影響，并揭示了對于復雜網絡目標控制的影響因素，及其帶來的一些問題。接下來的研究方向主要包括：如何通過調整網絡的結構使得在目標控制的情況下，網絡的驅動節點數目盡可能得少；探究各種度相關性影響的內在機理；對于真實網絡，如何調整才能使其更易被控制等。

[1]Newman M,BarabásiAL,Watts D J.The structure and dynamics of networks[M].Princeton:Princeton University Press,2011.

[2]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(4):175-308.

[3]Liu Yangyu,Slotine J J E,Barabási A L,et al.Controllability of complex networks[J].Nature,2011,473(7346):167-173.

[4]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[5]Wang Xiaofan,Chen Guanrong.Pinning control of scale-free dynamical networks[J].Physica A:Statistical Mechanics and itsApplications,2002,310(3):521-531.

[6]Manaffam S,Seyedi A.Pinning control for complex networks of linearly coupled oscillators[C]//Proceedings of the 2013 American Control Conference,Washington,Jun 17-19,2013.Piscataway:IEEE,2013:6364-6369.

[7]Cowan N J,Chastain E,Vilhena D A,et al.Nodal dynamics,not degree distributions,determine the structural controllability of complex networks[J].PLOS ONE,2011,7(6):e38398.

[8]Liu Yangyu,Slotine J E,Barabási A L,et al.Observability of complex systems[J].Proceedings of the National Academy of Sciences of the United States of America,2013,110(7):2460-2465.

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

[10]Yan Gang,Ren Jie,Lai Yingcheng,et al.Controlling complex networks:how much energy is needed?[J].Physical Review Letters,2012,108(21):218703.

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

[12]Boccaletti S,Bianconi G,Criado R,et al.The structure and dynamics of multilayer networks[J].Physics Reports,2014,544(1):1-122.

[13]Gao Jianxi,Barzel B,Barabási A L.Universal resilience patterns in complex networks[J].Nature,2016,530(7615):307-312.

[14]Buldyrev S V,Parshani R,Paul G,et al.Catastrophic cascade of failures in interdependent networks[J].Nature,2010,464(7291):1025-1028.

[15]Liu Xueming,Stanley H E,Gao Jianxi,et al.Breakdown of interdependent directed networks[J].Proceedings of the National Academy of Sciences of the United States of America,2016,113(5):1138-1143.

[16]Zhang Xiyun,Boccaletti S,Guan Shuguang,et al.Explosive synchronization in adaptive and multilayer networks[J].Physical Review Letters,2014,114(3):038701.

[17]Menichetti G,Dall'Asta L,Bianconi G,et al.Network controllability is determined by the density of low in-degree and out-degree nodes[J].Physical Review Letters,2014,113(7):078701.

[18]D?rfler F,Chertkov M,Bullo F,et al.Synchronization in complex oscillator networks and smart grids[J].Proceedings of the National Academy of Sciences of the United States ofAmerica,2013,110(6):2005-2010.

[19]Zhang Y,Garas A,Schweitzer F,et al.Value of peripheral nodes in controlling multilayer scale-free networks[J].Physical Review E,2016,93(1):012309.

[20]Slotine J J E,Li Weiping.Applied nonlinear control[M].Upper Saddle River:Prentice Hall,1991.

[21]Haussmann U.Linear systems and optimal control[J].Siam Review,2012,31(4):696-698.

[22]Foster J G,Foster D V,Grassberger P,et al.Edge direction and the structure of networks[J].Proceedings of the National Academy of Sciences of the United States of America,2010,107(24):10815-10820.

[23]Pósfai M,Liu Yangyu,Slotine J J E,et al.Effect of correlations on network controllability[J].Scientific Reports,2013,3:1067.