度相關性對無向網絡可控性的影響?

徐明 許傳云 曹克非

1)(云南大學物理與天文學院,非線性復雜系統中心,昆明 650091)

2)(凱里學院數學科學學院,凱里 556011)

3)(貴州財經大學數學與統計學院,貴陽 550025)

度相關性對無向網絡可控性的影響?

徐明1)2)3)許傳云1)曹克非1)?

1)(云南大學物理與天文學院,非線性復雜系統中心,昆明 650091)

2)(凱里學院數學科學學院,凱里 556011)

3)(貴州財經大學數學與統計學院,貴陽 550025)

(2016年7月23日收到;2016年9月5日收到修改稿)

復雜網絡的可控性不僅與網絡的度分布有關,還受到度相關性的影響,但這種影響在無向網絡的情況下尚不清楚.本文采用模擬退火算法,通過邊的重連改變網絡的度相關性從而研究其對網絡可控性的影響.數值模擬結果顯示,在度分布不變的情況下,無向網絡的可控性指標(驅動節點密度)一般隨著度相關系數的增大而單調減小;進一步研究表明,雙向網絡和某些有向網絡也遵循這種規律.無向網絡的度相關系數增大意味著對應有向網絡的各種度相關系數同步增大,但這些綜合變化對網絡可控性的影響不能簡單歸結為對應有向網絡中各影響的疊加.本文對這種現象給出了部分解釋.此外,對于無自環的大型稀疏網絡,無論其同配還是異配,驗證了其結構可控性與嚴格可控性是幾乎相同的.這些研究將深化對網絡可控性與網絡結構之間關系的理解.

復雜網絡,無向網絡,可控性,度相關性

1 引 言

對復雜網絡進行控制是分析和研究復雜網絡系統的一個重要目標,也是當前復雜網絡研究的熱點[1-12].其中,各種復雜網絡乃至各種復雜系統是否可控(即可控性問題)是極為關鍵且有著廣泛科學意義和應用價值的研究課題[1,4,9],例如,選擇哪些基因作為藥物的靶標來調控整個基因網絡,從而實現對一些疾病的治療等.系統的可控性也叫能控性,如果系統所有的狀態變量都可以通過輸入來影響和控制而在有限時間內由任何初始狀態達到所期望的目標狀態,則稱系統是可控的,或者更確切地說是狀態可控的,否則就稱系統是不可控的[1,13].可控性的基礎理論在數學上已較為成熟,并被廣泛應用于工程中.然而,實踐中要把傳統的可控性理論直接應用到復雜系統或網絡卻往往是困難的[4,9,14].如何控制一個節點眾多的復雜系統呢？首要問題是至少需要多少外界輸入信號才能使系統可控,也就是滿足可控性條件的控制器的最少個數問題.由于計算復雜度太大,該問題很難直接通過傳統的Kalman秩條件[13]來解決.2011年,Liu等[1]在《自然》上發表了關于復雜網絡的結構可控性(structural controllability)論文,開拓性地將傳統的結構可控性理論[15]應用到網絡的結構可控性問題,對網絡結構可控所需的最少輸入和最小驅動節點集做了深入研究：通過引入圖的匹配[16]得到了求解最少輸入信號和驅動節點的最少(最小)輸入定理;通過cavity方法[17]揭示了驅動節點密度nD(可控性指標)與網絡結構的深層聯系.這一突破性工作引發了復雜網絡可控性研究的熱潮.由于結構可控性忽略了網絡中邊權的大小和相互聯系,因此該理論對某些網絡(如無向網絡)不適用.2013年,Yuan等[3]從Popov-Belevitch-Hautus(PBH)可控性判據[18]出發提出了求解網絡嚴格可控性(exact controllability)的理論框架,可用于求解具有確定性邊權和任意結構的網絡的可控性(如無向無權網絡的可控性),使得網絡可控性的理論更加完備.這里需要說明的是,牽制控制[19]是復雜網絡系統控制研究的另一個重要方向,其目的是通過有選擇地對網絡中的少數節點施加控制而使整個網絡系統達到所期望的行為(使網絡中每個節點的軌跡“收斂”到某條期望的軌跡);結構可控性則主要研究系統是否可控,即系統狀態變量能否在有限時間內“到達”任何期望的狀態.由于研究目的不同,牽制控制與結構控制在驅動節點的選擇上差異較大[1,20-22],本文將不研究牽制控制.

文獻[1]給出一個重要結論：復雜網絡的結構可控性主要取決于網絡的度分布.隨后的研究發現,復雜網絡的可控性不能由網絡的度分布惟一確定,它還與度相關性有聯系[2,9,10].在保持網絡度分布不變的情況下,文獻[2]分別從入度-入度相關性、入度-出度相關性、出度-入度相關性和出度-出度相關性四個方面系統地研究了一般有向網絡的度相關性對網絡的結構可控性的影響.其中,四種度相關性對有向Erd?s-Rényi(ER)隨機網絡的結構可控性的影響規律如圖1所示,對有向無標度(scale-free)網絡也有類似的結果.

圖1 度相關系數對有向ER隨機網絡(節點數N=10000)的結構可控性指標nD的影響 網絡的平均度分別為〈k〉=1(紅色),〈k〉=3(綠色),〈k〉=5(藍色),〈k〉=7(黑色)和〈k〉=9(橙色);每一數據點為100次獨立模擬的平均;對有向無標度網絡也有類似的結果(引自文獻[2])Fig.1.The impact of degree correlation coefficients on the structural controllability measurenDfor the directed ER random network(N=10000)for average degrees〈k〉=1(red),〈k〉=3(green),〈k〉=5(blue),〈k〉=7(black)and〈k〉=9(orange).Each data point is an average of 100 independent runs.The results are similar for the directed scale-free network(cited from Ref.[2]).

然而,兩種或兩種以上的度相關性的共同變化會如何影響網絡的可控性則沒有徹底解決,這類問題也顯得更加復雜.例如,當四種度相關系數同步變大并趨近于1時,可控性將如何變化？另外,是否所有的有向網絡均遵循文獻[2]所得規律也值得探究.在網絡拓撲變化時,往往是多種度相關性同時發生變化,或者說一種度相關性變化的同時也常伴隨著其他類型度相關性的變化.一個常見的例子就是對無向網絡進行邊的重連變換.無向網絡可以看成特殊的有向網絡,無向網絡中兩節點相連意味著它們彼此指向對方.本文就以無向網絡及其推廣形式為研究對象來探索度相關性對網絡可控性的影響,分析其與一般有向網絡情況下相關結論的異同.

本文后續內容安排如下：首先介紹網絡可控性和度相關性的概念;接著對無向網絡及對應有向網絡中的度相關性對網絡可控性的影響進行數值模擬和分析;最后對模擬結果進行討論.

2 相關理論

2.1 網絡的結構可控性

考慮一個線性時不變系統,其動力學方程描述為[1,3]

將狀態變量看作節點,結合它們的相互作用可形成對應的網絡.其中向量x(t)=(x1(t),x2(t),···,xN(t))T和u(t)=(u1(t),u2(t),···,uM(t))T分別表示t時刻網絡中N個節點的狀態和M個輸入控制信號的狀態;A∈RN×N是節點間的耦合矩陣,B∈RN×M是輸入控制信號與節點的連接關系矩陣.

通過傳統的Kalman秩條件[13]來得到網絡可控所需的最少輸入或驅動節點,其計算時間復雜度為O(2N),這對于大規模的復雜系統或復雜網絡而言很難實現.但人們發現,如果存在矩陣A和B中的非零元素的一組取值,使得在這組值下的系統是可控的,則網絡中的待定邊權參數幾乎可以任意變化(保持非零)而不會破壞系統的可控性,這時的網絡被稱為是結構可控的[15].結構可控性的引入有效地解決了現實世界中無法準確度量邊權的問題,極大地推動了可控性的應用研究.Lin[15]提出的結構可控性定理從圖論的角度分析了結構可控性.在此基礎上,Liu等[1]將一般有向網絡的結構可控性問題轉化成求解有向圖的最大匹配,給出了如下的最少輸入定理.

定理1如果網絡是完全匹配,則使網絡結構可控所需的最少輸入數目或最少驅動節點數ND是1,此時任選一個節點都可作為網絡的驅動節點;如果網絡不是完全匹配,則最少驅動節點數ND等于網絡最大匹配后未匹配節點的數目：

其中|M?|為有向網絡中最大匹配M?所對應的匹配節點數,此時需獨立控制的驅動節點恰是未匹配節點.

需要注意的是,網絡的最大匹配的具體形式可能不惟一,因而驅動節點的選擇可能不惟一,但最少驅動節點數ND是不變的.

2.2 網絡的嚴格可控性

結構可控性主要針對網絡中每條(有向)非空連接的權重不確定且邊權間相互無關聯的情況[1,15].當邊權有關聯或邊權精確可知時,使用結構可控性理論所得結果可能會不夠準確,此時應采用網絡的嚴格可控性理論.嚴格可控性理論從PBH秩條件出發,證明了網絡系統(1)滿足可控性條件所需的最少輸入數目或最少驅動節點數ND應為[3]

其中μ(λi)是耦合矩陣A的特征值λi的幾何重數.網絡的嚴格可控性理論認為,無自環或少自環的大型稀疏網絡中零特征值的幾何重數最大,又由于此時零特征值的幾何重數可計算為μ(0)=N-rank(A),故可得如下最少驅動節點數ND的快速計算方法.

定理2對于大型稀疏網絡(有向或無向,加權或無權,無自環或少量自環),網絡系統(1)滿足可控性所需的最少輸入數目或最少驅動節點數ND為[3]

一般地,網絡的可控性度量指標(controllability measure)定義為使網絡可控所需的最少驅動節點在網絡節點中所占的比例,即網絡中的驅動節點密度(density of driver nodes),記為

該指標從控制輸入的需求比例上反映網絡的可控難易程度,nD越小的網絡越容易控制,反之則網絡越難于控制.

如果一個網絡的邊權是固定且精確可知的,則可采用網絡的嚴格可控性理論求解其可控性.但通常情況下,人們知道某些節點間存在連邊,卻無法獲取或難以精確測量邊權的值,另外邊權還可能隨時間而變化(保持非零),此時可以轉而利用網絡的結構可控性理論求解其可控性.雖然一個網絡系統是結構可控的并不等同于該系統一定可控,但可以說該系統幾乎(以概率為1的可能發生)是可控的.

2.3 網絡的度相關性

通常,人們用網絡的度分布描述網絡的拓撲結構特征.然而,這種描述有一個重要缺陷,即很難反映節點連接時的度的混合程度.度相關性則在本質上反映了不同度值節點間的連接傾向(偏好性)：如果度值高(低)的節點傾向于與其他度值高(低)的節點連接,那么該網絡關于度是同配的;反之,則稱該網絡是異配的[23].大量研究表明,真實網絡中的很多社會網絡關于度是同配的,而很多技術網絡和生物網絡關于度是異配的.度相關性對網絡傳播現象、博弈演化、隨機游走和網絡可控性有著不可忽視的影響.如果不考慮度相關性,通常將導致研究結果的片面性或不準確性.實踐中,可以通過Newman提出的計算網絡度相關性的Pearson系數來進行量化,該系數具體定義為[23]

其中,ji和ki分別為第i條邊的兩個端點的度(與其直接相連的邊數),M為網絡中的邊數.度相關系數(6)式對于無向和有向網絡均適用.特別地,對于有向網絡,利用以上Pearson系數可得到四種度相關系數：入度-入度相關系數、入度-出度相關系數、出度-入度相關系數和出度-出度相關系數,具體計算公式可表為[2,24]

其中,E是有向邊的數目,表示關于每一條邊求和;α,β∈{in,out}為入度或出度;和分別是關于有向邊e的起始節點的(α)度和末端節點的(β)度;是起始節點的平均度,是對應的標準偏差;kβ和σβ類似.以上兩個相關系數(6)式和(7)式實質上是一致的.無向網絡可以看作有向網絡的特殊情況,此時無向網絡的度相關系數((6)式)與對應有向網絡的四種度相關系數((7)式)均相等.

3 主要方法

這里主要對無向網絡及其推廣形式進行討論.無向網絡可以看作特殊的有向網絡：將一條無向邊看作一對有向邊,無向網絡G就直接推廣為對應的雙向網絡.當雙向網絡的邊權均確定時,例如邊權均為1,我們可求解其嚴格可控性;當雙向網絡的邊權非零但無法準確測量時,則求解其結構可控性.現有結果表明,在不考慮度相關性的因素時,無自環的大型稀疏網絡的結構可控性(利用(2)式)與嚴格可控性(利用(4)式)保持較高程度的一致[3].在度相關性發生較大變化時,此結論是否成立尚不清楚.

為了研究度相關性對網絡可控性所產生的影響,通常對網絡做邊的重連變換[2,25,26],它可以在保證網絡度分布不變的情況下改變度相關性.這里用圖例來說明邊的重連變換.假設在初始無向網絡G中隨機挑選到一對邊為AB和CD,如果A與D之間、C與B之間均無連邊,則對無向網絡G和對應雙向網絡可進行邊的重連變換,具體如圖2所示.

從(6)式和(7)式不難看出,這里的度相關系數由網絡的拓撲結構決定,即只與節點的連接方式有關,而與邊的權重無關.如果重連后(圖2(a))無向網絡G的度相關性發生變化,則對應雙向網絡在雙向邊重連后(圖2(b))各種度相關性也發生著完全同步的變化.圖2(c)所示則是對雙向網絡進行一般性的有向邊重連,所得網絡雖為更一般的有向網絡,但所得網絡的四種度相關系數仍然彼此相等,即有向邊重連過程導致的各種度相關性同步變化.正如圖2(c)所示：有向邊A→B和C→D重連為A→D和C→B,則出度-出度關系相應地從1→2和3→4轉化成1→4和3→2,且出度-入度、入度-入度和入度-出度關系也同時經歷著一樣的變化.基于此,只需研究雙向網絡的某一種度相關系數(例如出度-出度相關系數)對可控性的影響即可,其余度相關系數對可控性的影響與之完全相同.

圖2 邊的重連示意圖 (a)無向網絡的無向邊重連：隨機挑選一對無向邊AB和CD,如果A與D之間、C與B之間均無連邊,則讓A改為與D連接,C改為與B連接,從而將所挑選出的那一對邊重連成一對新邊AD和CB;(b)雙向網絡的雙向邊重連;(c)雙向網絡的一般性有向邊重連Fig.2. Schematic diagramsoflink rewiring：(a)Rewiring of undirected edges in an undirected network：after a pair of undirected edgesABandCDis randomly selected,these edges are then rewired by connectingAtoD,whileCtoB,provided that none of these edges already exist in the network;(b)rewiring of bidirectional edges in a bidirectional network;(c)rewiring of directed edges in a bidirectional network.

為了方便敘述,當網絡的邊權不確定且相互無關聯時,在雙向(bidirectional)邊重連變換下的結構可控性記為SCb,在一般有向(directed)邊重連變換下的結構可控性記為SCd;當網絡的邊權確定為1時,在雙向邊(或無向邊)重連變換下的嚴格可控性記為ECb,在一般有向邊重連變換下的嚴格可控性記為ECd.文獻[2]討論的是在一般有向邊重連變換下的結構可控性,即SCd.

對于邊權不確定且邊權之間相互無關聯的雙向網絡,我們討論其結構可控性,可用最大匹配的方法求其最小驅動節點集.注意雙向網絡的最大匹配不同于無向網絡的最大匹配.如圖3所示：在求解雙向網絡(圖3(b))的最大匹配時,不能等同于無向網絡(圖3(a))的最大匹配,而要將網絡轉化為無向二分網絡(圖3(c))來求其最大匹配.對于無向二分網絡,具體可采用Hopcroft-Karp算法[27]求解其最大匹配.

圖3 無向網絡和對應雙向網絡的最大匹配 (a)簡單無向網絡的最大匹配;(b)由(a)推廣的雙向網絡及其最大匹配;(c)與(b)對應的二分網絡及其最大匹配.其中,紅色邊為匹配連邊,綠色點為匹配節點.無向網絡(a)的最大匹配無法包含全部節點,而對應雙向網絡(b)的最大匹配為完全匹配,包含全部節點Fig.3.Maximum matchings in an undirected network and its corresponding bidirectional network：(a)Maximum matching of a simple undirected network;(b)maximum matching of the bidirectional network generalized from(a);(c)maximum matching of the bipartite network corresponding to(b).Among them,the red edges are matched edges,and the green nodes matched nodes.In the undirected network(a),the maximum matching cannot contain all nodes of the network;while in the corresponding bidirectional network(b),the maximum matching is a perfect matching which contains all nodes.

為了更有代表性地對各類網絡進行討論,理論模型選用ER隨機網絡模型(典型的同質網絡)和無標度網絡模型(常見的異質網絡).然而,一般的BA無標度網絡可能會導致不必要的度的相關性,并可能大大限制通過重新連邊所能得到的度相關系數的范圍.文獻[28]對使用重連方法產生反匹配無標度網絡的有效性進行的專門探討表明,在BA無標度網絡中,度相關性本質上受到度分布的制約,特別是在網絡規模較大和節點度差異性較強時,重連所產生的異配效果較差.

為了克服這些困難,這里先引入一個生成無標度網絡的統計模型[29].設網絡系統的初始狀態有N個節點,每個節點用一個整數i(i=1,2,...,N)進行標記.然后我們再對每個節點賦予一個權重pi=i-τ,其中τ是位于區間[0,1)內的控制參數.接下來,我們以歸一化的權重值和為概率隨機選取兩個節點i和j,若選取的兩個節點之間沒有連邊,則在它們之間添加一條邊.持續該過程直到系統中有mN條連邊,從而使網絡平均度為2m.由于連邊概率與節點的權重相關,因而節點i的度ki滿足

以上模型只是從統計角度構造了無標度網絡,并未從根本上改變無標度網絡對度相關性的制約.下面做進一步改造[2]：對節點i賦予權重pi=(i+i0)-τ,其中i0為可調參數,取值約為網絡平均度的2倍.改造后的無標度統計模型能生成近似的無標度網絡,既保持網絡的異質特性,又能適當擴大重連變換下網絡度相關系數的變化范圍.這種改造也是合理的,因為現實中的無標度網絡大多是近似的.

為了通過邊的重連變換有效地改變度相關系數,這里采用模擬退火算法[30]來具體實現.設定目標度相關系數r?并定義能量函數E(r)=|r-r?|,可按照下列步驟調節網絡的度相關系數：

1)對初始網絡計算出度相關系數r和對應的能量E(r),并初始化溫度參數T和每個T值的迭代次數L;

2)任意選擇兩條合適的連邊,對它們做邊的重連變換,計算變化后的能量E(r′),并得到增量ΔE=E(r′)-E(r);

3)按Metropolis準則,以一定的概率接受此種換邊方式：若ΔE≤0則直接接受該換邊方式,否則以概率exp(-ΔE/(kBT))接受該換邊方式(kB為Boltzmann常數).當新的連邊方式被確定接受時,相應地更新能量函數的值,并在此基礎上開始下一輪連邊試驗.而當新連邊被判定為舍棄時,則在原網絡狀態的基礎上繼續下一輪試驗.

4)如果|E(r)-E(r?)|的數值小于給定的閾值(這里取為0.01)則停止計算.否則逐漸減小T值,并返回步驟2重復此過程.

4 模擬結果

圖4 在無向邊重連變換下,無向無權網絡的度相關系數對網絡嚴格可控性指標nD(ECb)的影響 (a)ER隨機網絡(節點數N=10000)的情況;(b)無標度網絡(節點數N=10000)的情況.網絡的平均度分別為〈k〉=1/2(紅色),〈k〉=3/2(綠色),〈k〉=5/2(藍色),〈k〉=7/2(黑色)和〈k〉=9/2(橙色).每一數據點為50次獨立模擬的平均Fig.4.The impact of the degree correlation coefficient on the exact controllability measurenD(ECb)for undirected unweighted networks with rewiring of undirected edges for average degrees〈k〉=1/2(red),〈k〉=3/2(green),〈k〉=5/2(blue),〈k〉=7/2(black)and〈k〉=9/2(orange).Each data point is an average of 50 independent runs：(a)The results for the ER random network(N=10000);(b)the results for the scale-free network(N=10000).

我們先按照以上方法研究無向無權網絡(邊權為1)在無向邊重連變換下度相關性對網絡嚴格可控性(ECb)的影響.數值模擬結果如圖4所示：在相同條件下,無標度(異質)網絡比ER隨機(同質)網絡更難于控制;對于同樣類型的網絡,平均度越大則可控性指標(驅動節點密度)一般會越小,即稠密網絡比稀疏網絡更容易控制;無論是同質(均勻)網絡還是異質(非均勻)網絡,網絡可控性指標nD(ECb)在整體上隨著度相關系數r的增大而呈現減小的變化趨勢;度相關性對可控性的影響有時非常顯著,例如,對于平均度〈k〉=9/2的無標度網絡,當度相關系數r=0時網絡可控性指標約為0.13,而當度相關系數r=-0.6時網絡可控性指標約為0.5.圖4從平均值角度展示了度相關性對無向網絡嚴格可控性(ECb)的影響.

接著,對雙向網絡進行邊的重連變換,可類似地得到其他情形下度相關性與網絡可控性的關系.例如,將無向網絡看作邊權不確定的雙向網絡,對該網絡進行一般的有向邊重連可以得到度相關性與有向網絡結構可控性(SCd)的關系.有趣的是,雙向網絡的可控性SCb,ECb,SCd和ECd隨度相關性的變化規律均與圖4中ECb的變化規律表現出高度的一致性,其中無向網絡與對應雙向網絡的ECb實質上是相同的.這里以平均度〈k〉=5/2的無向ER隨機網絡(僅考慮ECb)與對應雙向網絡為例,說明度相關性對各種可控性的影響高度地一致,具體如圖5所示.從圖5還可以看出,50次獨立模擬得到的可控性指標的標準偏差不大,大都在0.02以內,即度相關系數對各種可控性指標(nD)的影響效應都是穩定的.

圖5 對于ER隨機模型(節點數N=10000),在邊的重連變換下,無向無權網絡(〈k〉=5/2)和對應雙向網絡(〈k〉=5)的度相關系數對各種可控性指標(nD)的影響.每一數據點為50次獨立模擬的平均,誤差線表示標準偏差Fig.5.The impact of the degree correlation coefficient on various controllability measures(nD)for the undirected unweighed network(〈k〉=5/2)and the corresponding bidirectional network(〈k〉=5)with rewiring of edges for the ER random model(N=10000).Each data point is an average of 50 independent runs,and the error bars denote the standard deviations.

實際上,網絡的各種可控性指標除了變化趨勢一致,相互間的數值差異也很小.為了進一步細致地考察圖5中各種可控性之間的差異,選取以下兩個指標對該差異進行探討：

反映嚴格可控性指標與結構可控性指標在雙向邊(或無向邊)重連下的相對偏差,其中表示雙向邊(或無向邊)重連下邊權均為1時的嚴格可控性指標nD(ECb)的平均值,表示邊權不確定時的結構可控性指標nD(SCb)的平均值;

圖6 無向ER隨機網絡與對應雙向網絡在邊重連變換下幾種可控性之間的相對偏差Δ1和Δ2 網絡節點數N=10000,無向網絡的平均度〈k〉=5/2Fig.6.Relative deviationsΔ1andΔ2of controllability measures for the undirected ER random network and its corresponding bidirectional network with rewiring of edges.The network size isN=10000,and the average degree of the undirected network is〈k〉=5/2.

下面比較一般有向網絡與無向(或雙向)網絡情形下,度相關性對網絡可控性的影響.從圖1可知,一般有向網絡在有向邊的重連變換下,可控性指標與出度-入度相關系數呈現出穩定的單調減小關系;入度-入度相關系數和出度-出度相關系數偏離0時,均使可控性指標nD不斷增大;可控性指標與入度-出度相關系數沒有關聯.從圖4和圖5可知：雙向網絡作為一種特殊的有向網絡,在邊的重連變換下,網絡可控性指標隨著度相關系數(出度-入度、出度-出度、入度-入度和入度-出度相關系數)的增大均表現為逐步減小,并不完全遵循文獻[2]的結論.

如何解釋無向(或雙向)網絡的度相關性對可控性的這種影響規律呢?考慮到雙向網絡的四種度相關系數在邊重連過程中是同步變化的,從圖1出發我們嘗試對四種度相關系數的影響效應做一個簡單的平均.當平均度〈k〉≥5時,在各種度相關系數均接近于-1處,驅動節點在網絡中所占的比例較大,網絡最難達到可控;在各種度相關系數均接近于0處,驅動節點在網絡中所占的比例應該較小;但是在各種度相關系數均接近于1處,驅動節點在網絡中所占的比例應該介于前兩者之間,這與圖4的結果顯然不相符,說明各種度相關系數對可控性的綜合影響不能簡單地看成各種度相關系數對可控性影響的簡單平均.也就是說,雖然無向網絡可以看作有向網絡的特殊情況,但無向網絡中的度相關性與可控性的關系有著特殊的規律,不能由有向網絡中的度相關性與可控性的關系所直接反映.

對無向(或雙向)網絡的度相關性與可控性的關系,我們分三種情況做如下分析.

1)當各種度相關系數在0附近時,利用cavity方法可以分別推導出各種度相關系數對可控性指標所產生的影響[2].出度-入度相關系數r(out-in)對nD的影響(只計算展開到r(out-in)的一次項)為

其中M2(x)和H(α)(x)(α∈{in,out})的具體形式見文獻[2],且H(α)(x)僅與度分布P(kin,kout)有關.因此,可控性指標近似為關于出度-出度相關系數r(out-out)的二次函數,且二次項系數為正.如果將有向網絡中的所有邊的方向都反轉,則出度-出度關系恰變成入度-入度關系,而網絡的結構可控性不變.這說明入度-入度相關系數對網絡可控性的影響與出度-出度相關系數產生的影響一致,具體關系式與(10)式類似：可控性指標也近似為關于入度-入度相關系數r(in-in)的二次函數.由于的表達式不依賴于有向邊起始節點的入度和末端節點的出度,因此,入度-出度相關系數r(in-out)對網絡可控性沒有影響,圖1(b)中的數值模擬也表明了這一點[2].考慮到雙向網絡中因此雙向網絡的結構可控性指標nD是關于度相關系數r的函數,并且將函數nD關于變量r線性化后,r的一次項系數為負數.基于微擾的思想,在度相關系數r=0附近可以判斷nD關于r是單調減小的.我們的解析分析結果與實驗結果(圖4和圖5)一致.

2)當各種度相關系數較小且向-1靠近時,上述基于微擾的方法不再適用.由于入度-出度相關系數對網絡可控性沒有明顯影響,這里只考慮其他三種度相關系數的影響.當各種度相關系數較小且向-1靠近時,由于入度-入度相關系數、出度-出度相關系數和出度-入度相關系數的減小對可控性指標均產生增大的作用,故最終的影響結果是隨著各種度相關系數向-1靠近,可控性指標nD增大.這與我們實驗的結果也保持一致.

3)當各種度相關系數較大且向1靠近時,可控性指標nD的基本變化趨勢比較令人困惑,此時基于微擾的方法不適用,nD的變化趨勢也不能從有向網絡的各種度相關系數對可控性的影響簡單地進行綜合而推得.僅從實驗的結果來看,在各種度相關系數對可控性的影響中,似乎是出度-入度相關系數對雙向網絡的可控性起了主導作用.導致該現象的原因可能是,雙向網絡的度相關系數接近于1時,網絡中的大度值節點彼此相連容易形成邊密度較大的點簇,這種內部大度值節點簇加上外圍小度值節點的結構使得雙向網絡的匹配集更大,從而使其驅動節點比例下降.

綜上可知,當網絡度相關系數在0附近時,可控性指標單調減小;當度相關系數趨近于-1時,可控性指標趨于最大值;當度相關系數趨近于1時,可控性指標趨于最小值.因此,度相關系數由-1變為0的過程中,網絡的可控性指標連續地逐漸減小;度相關系數由0變為1的過程中,網絡的可控性指標繼續逐漸減小或保持不增.

最后,我們從某些實際的網絡出發,對上述度相關性對可控性的影響規律做進一步驗證.這里采用的是網絡理論與實驗方面科學家們的合著關系網和美國西部的電網,它們分別來自文獻[31,32].將這兩個網絡看作權值不確定的雙向網絡,可計算出網絡的度相關系數和結構可控性指標如表1所示;網絡的結構可控性指標隨度相關性的變化如圖7所示.可見,網絡的結構可控性指標關于度相關系數單調減小,與理論模型中所反映的規律(圖4和圖5)一致.

圖7 一般的有向邊重連變換下,雙向網絡的度相關系數r對結構可控性指標nD(SCd)的影響 (a)網絡理論與實驗方面科學家們的合著關系網;(b)美國西部電網.圖中結果來自50次獨立模擬的平均,誤差線表示標準偏差Fig.7.The impact of the degree correlation coefficientron the structural controllability measurenDfor bidirectional networks with rewiring of directed edges：(a)Co-authorship network of scientists in network theory and experiments;(b)the power grid of the western United States.Each data point is an average of 50 independent runs,and the error bars denote the standard deviations.

表1 兩個實際網絡的度相關系數r和結構可控性指標nD的計算值Table 1.Calculated values of the degree correlation coefficientrand the structural controllability measurenDfor the two real networks.

5 總 結

本文的研究對象主要是無向網絡及對應的雙向網絡,其邊權既可以是確定的也可以是未知的.實際上,我們的研究可以做進一步推廣.對于更一般的有向網絡,如果每個節點的出度與入度都相同,則該網絡的四種度相關系數都相等,在邊的重連變換過程中網絡的各種度相關性也同步變化.通過類似的數值模擬發現,這種有向網絡的可控性指標也是關于其度相關系數的減函數,并且與無向網絡或雙向網絡中反映的規律(圖4、圖5和圖7)高度地一致,而不完全遵循文獻[2]中的規律(圖1).

在不考慮網絡的度相關性因素情況下,文獻[3]通過大量數值模擬發現無自環的大型稀疏網絡的嚴格可控性近似地與結構可控性一致.在此,我們通過數值模擬,進一步驗證了對于無自環的大型稀疏網絡,即使在同配或異配非常明顯的情況下,網絡的嚴格可控性與結構可控性的結果仍符合得很好.

通過數值仿真實驗發現,無向網絡及其推廣網絡的可控性指標是關于其度相關系數的減函數,即可控性指標隨著度相關性的增大而減小.隨后,我們對這種現象與有向網絡中的情形做了對比和分析,并做出了部分解釋,其中包括在度相關系數r=0附近的理論分析.雖然無向網絡可以看作有向網絡的特殊情況,但無向網絡中的度相關性與可控性的關系有著特殊的規律,不能全部由有向網絡中的度相關性與可控性的關系所直接反映.這一規律啟示我們：對于無向網絡及其推廣網絡,可以從度相關性角度去預測網絡的可控性;增加網絡的度相關性可能有助于減少驅動節點的數量,從而降低網絡的控制難度.

雖然單一度相關性對網絡可控性的影響已有較系統的闡述,但多種度相關性的共同作用對可控性產生的效應還不是很清楚.正如文獻[2]所反映的,測量實際網絡的度相關系數,并通過各種度相關系數對可控性的影響去綜合分析和預測網絡的可控性在多數情況下是有效的,但這種預測方法還有一定的局限性和片面性.本文以無向網絡及其推廣網絡為研究對象,揭示了各種度相關系數同步變化對網絡可控性的影響(可控性指標的變化規律).這里仍有一些需要繼續探索的問題：無向網絡的度相關系數接近于1時,為什么可控性指標變小?無向網絡(或雙向網絡)的可控性隨度相關性變化的內部機理是什么?另外,是否可以通過對其他特殊有向網絡的探索來發現更多相關規律?相信對這一系列問題的探索將有助于人們理解各種度相關系數與網絡可控性的更深層關系.

[1]Liu Y Y,Slotine J J,Barabási A L 2011Nature473 167

[2]Pósfai M,Liu Y Y,Slotine J J,Barabási A L 2013Sci.Rep.3 1067

[3]Yuan Z Z,Zhao C,Di Z R,Wang W X,Lai Y C 2013Nat.Commun.4 2447

[4]Zhou T,Zhang Z K,Chen G R,Wang X F,Shi D H,Di Z R,Fan Y,Fang J Q,Han X P,Liu J G,Liu R R,Liu Z H,Lu J A,Lü J H,Lü L Y,Rong Z H,Wang B H,Xu X K,Zhang Z Z 2014J.Univ.Electron.Sci.Technol.China43 1(in Chinese)[周濤,張子柯,陳關榮,汪小帆,史定華,狄增如,樊瑛,方錦清,韓筱璞,劉建國,劉潤然,劉宗華,陸君安,呂金虎,呂琳媛,榮智海,汪秉宏,許小可,章忠志2014電子科技大學學報43 1]

[5]Ruths J,Ruths D 2014Science343 1373

[6]Wuchty S 2014Proc.Natl.Acad.Sci.U.S.A.111 7156

[7]Xu M,Xu C Y,Wang H,Deng C Z,Cao K F 2015Eur.Phys.J.B88 168

[8]Xu C J,Zheng Y,Su H S,Wang H O 2015Int.J.Control88 248

[9]Hou L L,Lao S Y,Xiao Y D,Bai L 2015Acta Phys.Sin.64 188901(in Chinese)[侯綠林,老松楊,肖延東,白亮2015物理學報64 188901]

[10]Nie S,Wang X W,Wang B H 2015Physica A436 98

[11]Ruths D,Ruths J 2016Sci.Rep.6 19818

[12]Kawakami E,Singh V K,Matsubara K,Ishii T,Matsuoka Y,Hase T,Kulkarni P,Siddiqui K,Kodilkar J,Danve N,Subramanian I,Katoh M,Shimizu-Yoshida Y,Ghosh S,Jere A,Kitano H 2016NPJ Syst.Biol.Appl.2 15018

[13]Kalman R E 1963J.Soc.Ind.Appl.Math.Ser.A1 152

[14]Lombardi A,H?rnquist M 2007Phys.Rev.E75 056110

[15]Lin C T 1974IEEE Trans.Autom.Contr.19 201

[16]Lovász L,Plummer M D 1986Matching Theory(Amsterdam：North-Holland)pp83-119

[17]Mézard M,Parisi G 2001Eur.Phys.J.B20 217

[18]Hautus M L J 1969Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen Ser.A72 443

[19]Wang X F,Chen G R 2002Physica A310 521

[20]Zhou M Y,Zhuo Z,Liao H,Fu Z Q,Cai S M 2015Sci.Rep.5 17459

[21]Zhou M Y,He X S,Fu Z Q,Liao H,Cai S M,Zhuo Z 2016Physica A446 120

[22]Orouskhani Y,Jalili M,Yu X H 2016Sci.Rep.6 24252

[23]Newman M E J 2002Phys.Rev.Lett.89 208701

[24]Foster J G,Foster D V,Grassberger P,Paczuski M 2010Proc.Natl.Acad.Sci.U.S.A.107 10815

[25]Newman M E J 2003Phys.Rev.E67 026126

[26]Maslov S,Sneppen K 2002Science296 910

[27]Hopcroft J E,Karp R M 1973SIAM J.Comput.2 225

[28]Qu J,Wang S J 2015Acta Phys.Sin.64 198901(in Chinese)[屈靜,王圣軍 2015物理學報 64 198901]

[29]Goh K I,Kahng B,Kim D 2001Phys.Rev.Lett.87 278701

[30]Kirkpatrick S,Gelatt Jr C D,Vecchi M P 1983Science220 671

[31]Newman M E J 2006Phys.Rev.E74 036104

[32]Watts D J,Strogatz S H 1998Nature393 440

Effect of degree correlations on controllability of undirected networks?

Xu Ming1)2)3)Xu Chuan-Yun1)Cao Ke-Fei1)?
1)(Center for Nonlinear Complex Systems,School of Physics and Astronomy,Yunnan University,Kunming 650091,China)
2)(School of Mathematical Sciences,Kaili University,Kaili 556011,China)
3)(School of Mathematics and Statistics,Guizhou University of Finance and Economics,Guiyang 550025,China)

23 July 2016;revised manuscript

5 September 2016)

The controllability analysis of complex networks is of great importance for modern network science and engineering.Existing research shows that the controllability of a complex network is affected not only by the degree distribution of the network,but also by the degree correlation.Although the effect of degree correlations on the network controllability is well studied for directed networks,it is not yet very clear for the case of undirected networks.To explore the impact of degree correlations on the controllability of undirected networks and their corresponding generalized(bidirectional and directed)networks,in this paper,we use the simulated annealing algorithm to change the network degree correlation coefficients by link rewiring.First,the undirected Erd?s-Rényi random network and the modified scale-free network are taken as example models to be investigated.Numerical simulations show that the controllability measure(density of driver nodes)of undirected networks decreases monotonically with the increase of the degree correlation coefficient under a constant degree distribution.Specifically,when the degree correlation coefficient changes from-1 to 0,the controllability measure decreases rapidly;while the decrease in the controllability measure is not obvious when the degree correlation coefficient changes from 0 to 1.Next,the bidirectional networks and some directed networks are considered;in these networks,the in-degree of each node is equal to its out-degree,thus link rewiring results in the simultaneous changes of various degree correlations(i.e.,in-in,in-out,out-in,and out-out degree correlations).Further investigations show that these bidirectional and directed networks also follow the above rule,which is verified by the two real networks.The increase of the degree correlation coefficient in undirected networks also implies the increases of various degree correlation coefficients in the corresponding directed networks.Although the effect of a single degree correlation on the controllability of directed networks is clear,the comprehensive effect of the simultaneous changes in various degree correlations on the network controllability cannot be additively and therefore directly estimated by the relevant results in the corresponding directed networks;namely,the effect of the degree correlation on the controllability in an undirected network has its special rule.Some explanations are given for this phenomenon.Moreover,for a large sparse network without self-loops,no matter how assortative or disassortative it is,its structural controllability and exact controllability are verified to be almost the same.These studies will deepen the understanding of the relationship between the network controllability and the network structure.

complex network,undirected network,controllability,degree correlationPACS:89.75.-k,89.75.Hc,02.30.Yy

10.7498/aps.66.028901

:89.75.-k,89.75.Hc,02.30.Yy DOI:10.7498/aps.66.028901

?國家自然科學基金(批準號：11365023)、貴州省科技廳/黔東南州科技局/凱里學院科技聯合基金(批準號：黔科合LH字[2014]7231)和貴州省教育廳優秀科技創新人才支持計劃(批準號：黔教合KY字[2015]505)資助的課題.

?通信作者.E-mail：kfcao163@163.com

*Project supported by the National Natural Science Foundation of China(Grant No.11365023),the Joint Fund of Department of Science and Technology of Guizhou Province/Bureau of Science and Technology of Qiandongnan Prefecture/Kaili University,China(Grant No.LH-2014-7231),and the Science and Technology Talent Support Program of Department of Education of Guizhou Province,China(Grant No.KY-2015-505).

?Corresponding author.E-mail：kfcao163@163.com