徐明 許傳云 曹克非

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

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

3)(貴州財(cái)經(jīng)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,貴陽(yáng) 550025)

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

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

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

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

3)(貴州財(cái)經(jīng)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,貴陽(yáng) 550025)

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

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

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

1 引 言

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

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

圖1 度相關(guān)系數(shù)對(duì)有向ER隨機(jī)網(wǎng)絡(luò)(節(jié)點(diǎn)數(shù)N=10000)的結(jié)構(gòu)可控性指標(biāo)nD的影響 網(wǎng)絡(luò)的平均度分別為〈k〉=1(紅色),〈k〉=3(綠色),〈k〉=5(藍(lán)色),〈k〉=7(黑色)和〈k〉=9(橙色);每一數(shù)據(jù)點(diǎn)為100次獨(dú)立模擬的平均;對(duì)有向無(wú)標(biāo)度網(wǎng)絡(luò)也有類似的結(jié)果(引自文獻(xiàn)[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)性的共同變化會(huì)如何影響網(wǎng)絡(luò)的可控性則沒(méi)有徹底解決,這類問(wèn)題也顯得更加復(fù)雜.例如,當(dāng)四種度相關(guān)系數(shù)同步變大并趨近于1時(shí),可控性將如何變化？另外,是否所有的有向網(wǎng)絡(luò)均遵循文獻(xiàn)[2]所得規(guī)律也值得探究.在網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí),往往是多種度相關(guān)性同時(shí)發(fā)生變化,或者說(shuō)一種度相關(guān)性變化的同時(shí)也常伴隨著其他類型度相關(guān)性的變化.一個(gè)常見(jiàn)的例子就是對(duì)無(wú)向網(wǎng)絡(luò)進(jìn)行邊的重連變換.無(wú)向網(wǎng)絡(luò)可以看成特殊的有向網(wǎng)絡(luò),無(wú)向網(wǎng)絡(luò)中兩節(jié)點(diǎn)相連意味著它們彼此指向?qū)Ψ?本文就以無(wú)向網(wǎng)絡(luò)及其推廣形式為研究對(duì)象來(lái)探索度相關(guān)性對(duì)網(wǎng)絡(luò)可控性的影響,分析其與一般有向網(wǎng)絡(luò)情況下相關(guān)結(jié)論的異同.

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

2 相關(guān)理論

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

考慮一個(gè)線性時(shí)不變系統(tǒng),其動(dòng)力學(xué)方程描述為[1,3]

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

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

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

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

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

2.2 網(wǎng)絡(luò)的嚴(yán)格可控性

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

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

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

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

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

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

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

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

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

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

3 主要方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 模擬結(jié)果

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

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

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

圖5 對(duì)于ER隨機(jī)模型(節(jié)點(diǎn)數(shù)N=10000),在邊的重連變換下,無(wú)向無(wú)權(quán)網(wǎng)絡(luò)(〈k〉=5/2)和對(duì)應(yīng)雙向網(wǎng)絡(luò)(〈k〉=5)的度相關(guān)系數(shù)對(duì)各種可控性指標(biāo)(nD)的影響.每一數(shù)據(jù)點(diǎn)為50次獨(dú)立模擬的平均,誤差線表示標(biāo)準(zhǔn)偏差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.

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

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

圖6 無(wú)向ER隨機(jī)網(wǎng)絡(luò)與對(duì)應(yīng)雙向網(wǎng)絡(luò)在邊重連變換下幾種可控性之間的相對(duì)偏差Δ1和Δ2 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N=10000,無(wú)向網(wǎng)絡(luò)的平均度〈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)絡(luò)與無(wú)向(或雙向)網(wǎng)絡(luò)情形下,度相關(guān)性對(duì)網(wǎng)絡(luò)可控性的影響.從圖1可知,一般有向網(wǎng)絡(luò)在有向邊的重連變換下,可控性指標(biāo)與出度-入度相關(guān)系數(shù)呈現(xiàn)出穩(wěn)定的單調(diào)減小關(guān)系;入度-入度相關(guān)系數(shù)和出度-出度相關(guān)系數(shù)偏離0時(shí),均使可控性指標(biāo)nD不斷增大;可控性指標(biāo)與入度-出度相關(guān)系數(shù)沒(méi)有關(guān)聯(lián).從圖4和圖5可知：雙向網(wǎng)絡(luò)作為一種特殊的有向網(wǎng)絡(luò),在邊的重連變換下,網(wǎng)絡(luò)可控性指標(biāo)隨著度相關(guān)系數(shù)(出度-入度、出度-出度、入度-入度和入度-出度相關(guān)系數(shù))的增大均表現(xiàn)為逐步減小,并不完全遵循文獻(xiàn)[2]的結(jié)論.

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

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

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

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

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

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

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

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

圖7 一般的有向邊重連變換下,雙向網(wǎng)絡(luò)的度相關(guān)系數(shù)r對(duì)結(jié)構(gòu)可控性指標(biāo)nD(SCd)的影響 (a)網(wǎng)絡(luò)理論與實(shí)驗(yàn)方面科學(xué)家們的合著關(guān)系網(wǎng);(b)美國(guó)西部電網(wǎng).圖中結(jié)果來(lái)自50次獨(dú)立模擬的平均,誤差線表示標(biāo)準(zhǔn)偏差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 兩個(gè)實(shí)際網(wǎng)絡(luò)的度相關(guān)系數(shù)r和結(jié)構(gòu)可控性指標(biāo)nD的計(jì)算值Table 1.Calculated values of the degree correlation coefficientrand the structural controllability measurenDfor the two real networks.

5 總 結(jié)

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

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

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

雖然單一度相關(guān)性對(duì)網(wǎng)絡(luò)可控性的影響已有較系統(tǒng)的闡述,但多種度相關(guān)性的共同作用對(duì)可控性產(chǎn)生的效應(yīng)還不是很清楚.正如文獻(xiàn)[2]所反映的,測(cè)量實(shí)際網(wǎng)絡(luò)的度相關(guān)系數(shù),并通過(guò)各種度相關(guān)系數(shù)對(duì)可控性的影響去綜合分析和預(yù)測(cè)網(wǎng)絡(luò)的可控性在多數(shù)情況下是有效的,但這種預(yù)測(cè)方法還有一定的局限性和片面性.本文以無(wú)向網(wǎng)絡(luò)及其推廣網(wǎng)絡(luò)為研究對(duì)象,揭示了各種度相關(guān)系數(shù)同步變化對(duì)網(wǎng)絡(luò)可控性的影響(可控性指標(biāo)的變化規(guī)律).這里仍有一些需要繼續(xù)探索的問(wèn)題：無(wú)向網(wǎng)絡(luò)的度相關(guān)系數(shù)接近于1時(shí),為什么可控性指標(biāo)變小?無(wú)向網(wǎng)絡(luò)(或雙向網(wǎng)絡(luò))的可控性隨度相關(guān)性變化的內(nèi)部機(jī)理是什么?另外,是否可以通過(guò)對(duì)其他特殊有向網(wǎng)絡(luò)的探索來(lái)發(fā)現(xiàn)更多相關(guān)規(guī)律?相信對(duì)這一系列問(wèn)題的探索將有助于人們理解各種度相關(guān)系數(shù)與網(wǎng)絡(luò)可控性的更深層關(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)榮,汪小帆,史定華,狄增如,樊瑛,方錦清,韓筱璞,劉建國(guó),劉潤(rùn)然,劉宗華,陸君安,呂金虎,呂琳媛,榮智海,汪秉宏,許小可,章忠志2014電子科技大學(xué)學(xué)報(bào)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)[侯綠林,老松楊,肖延?xùn)|,白亮2015物理學(xué)報(bào)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物理學(xué)報(bào) 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

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào)：11365023)、貴州省科技廳/黔東南州科技局/凱里學(xué)院科技聯(lián)合基金(批準(zhǔn)號(hào)：黔科合LH字[2014]7231)和貴州省教育廳優(yōu)秀科技創(chuàng)新人才支持計(jì)劃(批準(zhǔn)號(hào)：黔教合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