徐明 許傳云 曹克非

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

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

3)(貴州財經(jīng)大學數(shù)學與統(tǒng)計學院,貴陽 550025)

度相關(guān)性對無向網(wǎng)絡可控性的影響?

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

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

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

3)(貴州財經(jīng)大學數(shù)學與統(tǒng)計學院,貴陽 550025)

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

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

復雜網(wǎng)絡,無向網(wǎng)絡,可控性,度相關(guān)性

1 引 言

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

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

圖1 度相關(guān)系數(shù)對有向ER隨機網(wǎng)絡(節(jié)點數(shù)N=10000)的結(jié)構(gòu)可控性指標nD的影響 網(wǎng)絡的平均度分別為〈k〉=1(紅色),〈k〉=3(綠色),〈k〉=5(藍色),〈k〉=7(黑色)和〈k〉=9(橙色);每一數(shù)據(jù)點為100次獨立模擬的平均;對有向無標度網(wǎng)絡也有類似的結(jié)果(引自文獻[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]).

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

本文后續(xù)內(nèi)容安排如下：首先介紹網(wǎng)絡可控性和度相關(guān)性的概念;接著對無向網(wǎng)絡及對應有向網(wǎng)絡中的度相關(guān)性對網(wǎng)絡可控性的影響進行數(shù)值模擬和分析;最后對模擬結(jié)果進行討論.

2 相關(guān)理論

2.1 網(wǎng)絡的結(jié)構(gòu)可控性

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

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

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

定理1如果網(wǎng)絡是完全匹配,則使網(wǎng)絡結(jié)構(gòu)可控所需的最少輸入數(shù)目或最少驅(qū)動節(jié)點數(shù)ND是1,此時任選一個節(jié)點都可作為網(wǎng)絡的驅(qū)動節(jié)點;如果網(wǎng)絡不是完全匹配,則最少驅(qū)動節(jié)點數(shù)ND等于網(wǎng)絡最大匹配后未匹配節(jié)點的數(shù)目：

其中|M?|為有向網(wǎng)絡中最大匹配M?所對應的匹配節(jié)點數(shù),此時需獨立控制的驅(qū)動節(jié)點恰是未匹配節(jié)點.

需要注意的是,網(wǎng)絡的最大匹配的具體形式可能不惟一,因而驅(qū)動節(jié)點的選擇可能不惟一,但最少驅(qū)動節(jié)點數(shù)ND是不變的.

2.2 網(wǎng)絡的嚴格可控性

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

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

定理2對于大型稀疏網(wǎng)絡(有向或無向,加權(quán)或無權(quán),無自環(huán)或少量自環(huán)),網(wǎng)絡系統(tǒng)(1)滿足可控性所需的最少輸入數(shù)目或最少驅(qū)動節(jié)點數(shù)ND為[3]

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

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

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

2.3 網(wǎng)絡的度相關(guān)性

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

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

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

3 主要方法

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

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

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

圖2 邊的重連示意圖 (a)無向網(wǎng)絡的無向邊重連：隨機挑選一對無向邊AB和CD,如果A與D之間、C與B之間均無連邊,則讓A改為與D連接,C改為與B連接,從而將所挑選出的那一對邊重連成一對新邊AD和CB;(b)雙向網(wǎng)絡的雙向邊重連;(c)雙向網(wǎng)絡的一般性有向邊重連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.

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

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

圖3 無向網(wǎng)絡和對應雙向網(wǎng)絡的最大匹配 (a)簡單無向網(wǎng)絡的最大匹配;(b)由(a)推廣的雙向網(wǎng)絡及其最大匹配;(c)與(b)對應的二分網(wǎng)絡及其最大匹配.其中,紅色邊為匹配連邊,綠色點為匹配節(jié)點.無向網(wǎng)絡(a)的最大匹配無法包含全部節(jié)點,而對應雙向網(wǎng)絡(b)的最大匹配為完全匹配,包含全部節(jié)點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.

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

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

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

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

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

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

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

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

4 模擬結(jié)果

圖4 在無向邊重連變換下,無向無權(quán)網(wǎng)絡的度相關(guān)系數(shù)對網(wǎng)絡嚴格可控性指標nD(ECb)的影響 (a)ER隨機網(wǎng)絡(節(jié)點數(shù)N=10000)的情況;(b)無標度網(wǎng)絡(節(jié)點數(shù)N=10000)的情況.網(wǎng)絡的平均度分別為〈k〉=1/2(紅色),〈k〉=3/2(綠色),〈k〉=5/2(藍色),〈k〉=7/2(黑色)和〈k〉=9/2(橙色).每一數(shù)據(jù)點為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).

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

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

圖5 對于ER隨機模型(節(jié)點數(shù)N=10000),在邊的重連變換下,無向無權(quán)網(wǎng)絡(〈k〉=5/2)和對應雙向網(wǎng)絡(〈k〉=5)的度相關(guān)系數(shù)對各種可控性指標(nD)的影響.每一數(shù)據(jù)點為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.

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

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

圖6 無向ER隨機網(wǎng)絡與對應雙向網(wǎng)絡在邊重連變換下幾種可控性之間的相對偏差Δ1和Δ2 網(wǎng)絡節(jié)點數(shù)N=10000,無向網(wǎng)絡的平均度〈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.

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

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

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

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

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

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

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

綜上可知,當網(wǎng)絡度相關(guān)系數(shù)在0附近時,可控性指標單調(diào)減小;當度相關(guān)系數(shù)趨近于-1時,可控性指標趨于最大值;當度相關(guān)系數(shù)趨近于1時,可控性指標趨于最小值.因此,度相關(guān)系數(shù)由-1變?yōu)?的過程中,網(wǎng)絡的可控性指標連續(xù)地逐漸減小;度相關(guān)系數(shù)由0變?yōu)?的過程中,網(wǎng)絡的可控性指標繼續(xù)逐漸減小或保持不增.

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

圖7 一般的有向邊重連變換下,雙向網(wǎng)絡的度相關(guān)系數(shù)r對結(jié)構(gòu)可控性指標nD(SCd)的影響 (a)網(wǎng)絡理論與實驗方面科學家們的合著關(guān)系網(wǎng);(b)美國西部電網(wǎng).圖中結(jié)果來自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 兩個實際網(wǎng)絡的度相關(guān)系數(shù)r和結(jié)構(gòu)可控性指標nD的計算值Table 1.Calculated values of the degree correlation coefficientrand the structural controllability measurenDfor the two real networks.

5 總 結(jié)

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

在不考慮網(wǎng)絡的度相關(guān)性因素情況下,文獻[3]通過大量數(shù)值模擬發(fā)現(xiàn)無自環(huán)的大型稀疏網(wǎng)絡的嚴格可控性近似地與結(jié)構(gòu)可控性一致.在此,我們通過數(shù)值模擬,進一步驗證了對于無自環(huán)的大型稀疏網(wǎng)絡,即使在同配或異配非常明顯的情況下,網(wǎng)絡的嚴格可控性與結(jié)構(gòu)可控性的結(jié)果仍符合得很好.

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

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

[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)[周濤,張子柯,陳關(guān)榮,汪小帆,史定華,狄增如,樊瑛,方錦清,韓筱璞,劉建國,劉潤然,劉宗華,陸君安,呂金虎,呂琳媛,榮智海,汪秉宏,許小可,章忠志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)、貴州省科技廳/黔東南州科技局/凱里學院科技聯(lián)合基金(批準號：黔科合LH字[2014]7231)和貴州省教育廳優(yōu)秀科技創(chuàng)新人才支持計劃(批準號：黔教合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