0 引言

    近年來，復(fù)雜網(wǎng)絡(luò)引起了科學(xué)家的廣泛關(guān)注^[1]。復(fù)雜網(wǎng)絡(luò)最重要的統(tǒng)計(jì)特征是小世界效應(yīng)^[2]和無標(biāo)度特性^[3]，其中，小世界網(wǎng)絡(luò)具有小的特征路徑長度和大的簇系數(shù)，而無標(biāo)度特性指的是網(wǎng)絡(luò)的節(jié)點(diǎn)度(節(jié)點(diǎn)的度定義為與該節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù))分布服從冪律^[4]。

    復(fù)雜網(wǎng)絡(luò)上的同步現(xiàn)象是一種重要的研究課題^[5-7]。研究表明，無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)的同步能力好于規(guī)則網(wǎng)絡(luò)^[8]。對這一現(xiàn)象的普遍解釋是小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的平均最短距離小，使得信息之間的交流更高效。然而本文發(fā)現(xiàn)網(wǎng)絡(luò)的同步能力幾乎獨(dú)立于網(wǎng)絡(luò)的平均路徑長度，即平均路徑相同的網(wǎng)絡(luò)同步能力卻存在較大的差異。NISHIKAWA T、MOTTER A E等的研究表明，對無標(biāo)度網(wǎng)絡(luò)而言，網(wǎng)絡(luò)度分布的不均勻性抑制了網(wǎng)絡(luò)同步能力的增強(qiáng)^[9]；HONG H、KIM B J等的研究則表明，對WS小世界網(wǎng)絡(luò)而言，使節(jié)點(diǎn)度分布變得不均勻(即增大度分布的方差)增強(qiáng)了小世界網(wǎng)絡(luò)的同步能力^[10]，與文獻(xiàn)的結(jié)論貌似沖突。本文對此給出了詳盡的解釋。

    BARAHONA M和PECORA L M^[11]研究了線性耦合網(wǎng)絡(luò)的同步穩(wěn)定性問題，給出了主穩(wěn)定函數(shù)判據(jù)。如果在網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)上放置一個(gè)動(dòng)力學(xué)系統(tǒng)(該動(dòng)力學(xué)系統(tǒng)既可以是極限環(huán)，也可以是混沌的)，讓有邊相連的兩個(gè)節(jié)點(diǎn)的動(dòng)力學(xué)系統(tǒng)之間存在相互耦合作用，就形成了一個(gè)動(dòng)力學(xué)網(wǎng)絡(luò)。設(shè)網(wǎng)絡(luò)有N個(gè)節(jié)點(diǎn),那么第i個(gè)節(jié)點(diǎn)所滿足的狀態(tài)方程是：

    WS小世界網(wǎng)絡(luò)的構(gòu)造算法為：(1)給定一個(gè)節(jié)點(diǎn)數(shù)為N的規(guī)則網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都與它最鄰近的K=2k個(gè)節(jié)點(diǎn)相連，通常N≥K≥1；(2)依次訪問網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，對每個(gè)節(jié)點(diǎn)的所有連線以概率p進(jìn)行重連，連接該節(jié)點(diǎn)的一端不變，另一端隨機(jī)選擇節(jié)點(diǎn)連接，但兩個(gè)節(jié)點(diǎn)之間不允許重復(fù)連接，也不允許節(jié)點(diǎn)與自身相連。

    本文考慮了一種擇優(yōu)選擇的小世界網(wǎng)絡(luò)模型(Small-World Networks with Preferential Attachment，PA小世界網(wǎng)絡(luò))。其構(gòu)造算法為：(1)步驟(1)與WS小世界網(wǎng)絡(luò)模型相同；(2)在WS小世界網(wǎng)絡(luò)斷開重連時(shí)，不是隨機(jī)選擇一個(gè)節(jié)點(diǎn)連接，而是按照正比與節(jié)點(diǎn)度的概率選擇節(jié)點(diǎn)連接。

1 網(wǎng)絡(luò)幾何特征量

1.1 簇系數(shù)

    簇系數(shù)是表征網(wǎng)絡(luò)節(jié)點(diǎn)集群程度的物理量。節(jié)點(diǎn)i的簇系數(shù)定義為所有相鄰節(jié)點(diǎn)之間連邊的數(shù)目與可能的最大連邊數(shù)目的比例。假設(shè)節(jié)點(diǎn)i的度為k_i，它的所有鄰居節(jié)點(diǎn)之間的邊數(shù)為E_i，則節(jié)點(diǎn)i的簇系數(shù)定義為C_i=2E_i/(k_i(k_i-1))。對網(wǎng)絡(luò)中所有節(jié)點(diǎn)的簇系數(shù)求平均值就是整個(gè)網(wǎng)絡(luò)的簇系數(shù)。

1.2 特征路徑長度

    在網(wǎng)絡(luò)中，兩點(diǎn)間的距離定義為連接兩點(diǎn)的最短路徑所包含的邊的數(shù)目，對所有節(jié)點(diǎn)對的距離求平均就得到了網(wǎng)絡(luò)的特征路徑長度。

1.3 節(jié)點(diǎn)度的方差

    節(jié)點(diǎn)度的方差是衡量節(jié)點(diǎn)度分布均勻性的一種度量。度分布越均勻，方差越小；反之，方差越大。其定義為：

1.4 節(jié)點(diǎn)的介數(shù)

    節(jié)點(diǎn)k的介數(shù)定義為：

式中，g_ij是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間最短路徑的條數(shù)，g_ikj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間最短路徑中經(jīng)過節(jié)點(diǎn)k的條數(shù)。對網(wǎng)絡(luò)中的所有節(jié)點(diǎn)對(i，j)求和即可以得到節(jié)點(diǎn)k的介數(shù)。由此可以看出，一個(gè)節(jié)點(diǎn)的介數(shù)反映了該節(jié)點(diǎn)在其他節(jié)點(diǎn)通信中的重要程度。

2 仿真結(jié)果

    仿真中，選擇網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N=500(仿真表明，節(jié)點(diǎn)數(shù)的多少并不影響結(jié)果的普遍性)，K=2k=12，即網(wǎng)絡(luò)的平均度<k>=12。仿真圖的數(shù)據(jù)為節(jié)點(diǎn)數(shù)N=500時(shí)程序運(yùn)行50次的平均結(jié)果。

    首先研究了特征根比例R隨重連概率p的變化情況。如圖1所示，對于PA小世界網(wǎng)絡(luò)，隨著的p增大，R值先是單調(diào)減小然后單調(diào)增大，表明該網(wǎng)絡(luò)的同步能力隨著p先增強(qiáng)后減弱；對于WS小世界網(wǎng)絡(luò)，R單調(diào)遞減，這表明WS小世界網(wǎng)絡(luò)的同步能力隨著p的增大而增強(qiáng)。那么發(fā)生這種差異的原因是什么呢？為此，本文還研究了網(wǎng)絡(luò)的其他幾何特征量，如網(wǎng)絡(luò)的特征路徑長度l和簇系數(shù)C(如圖2所示)、節(jié)點(diǎn)度的方差σ²(如圖3所示)、節(jié)點(diǎn)的最大介數(shù)B_max(如圖4所示)以及節(jié)點(diǎn)的最大度數(shù)k_max(如圖5所示)等隨著p的變化情況。

    由圖2可以看出，對于PA小世界網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)，特征路徑長度l和簇系數(shù)C都隨著p的增加而單調(diào)減小，且?guī)缀醣３忠恢拢@說明圖1中R值的差異不是由特征路徑長度l和簇系數(shù)C的不同引起的；同時(shí)，也表明對于特征路徑長度和簇系數(shù)都幾乎相同的網(wǎng)絡(luò)，其同步性能仍然可以展現(xiàn)出相當(dāng)?shù)牟町悾舱f明了兩者中的任何一個(gè)都不是造成這種差異的原因。

    圖3是對PA小世界網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)的節(jié)點(diǎn)度的方差仿真的結(jié)果。顯而易見，PA小世界網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)的節(jié)點(diǎn)度的方差都隨著p的增大而增大，但在PA小世界網(wǎng)絡(luò)中，由于重連時(shí)另一端為擇優(yōu)選擇，導(dǎo)致節(jié)點(diǎn)度的方差增大的速度明顯快于WS小世界網(wǎng)絡(luò)。HONG H^[10]等人認(rèn)為小世界網(wǎng)絡(luò)中節(jié)點(diǎn)度的方差的增大會(huì)導(dǎo)致其同步能力的增強(qiáng)。本文的仿真也表明，在WS小世界網(wǎng)絡(luò)中，隨著p的增大，R逐漸減小，節(jié)點(diǎn)度方差σ²逐漸增大，那么是否節(jié)點(diǎn)度的方差的增大是導(dǎo)致網(wǎng)絡(luò)同步能力增強(qiáng)的原因呢？答案是否定的。可以看到，在PA小世界網(wǎng)絡(luò)中，隨著重連概率p的增大，方差也逐漸增大，且增加的速率明顯大于WS小世界網(wǎng)絡(luò)，但由于節(jié)點(diǎn)度的方差增加的太快，使得這種度分布的不均勻性對網(wǎng)絡(luò)的同步能力起了抑制作用(如在圖1中當(dāng)p≥0.7時(shí)R值的上揚(yáng)，表明了PA小世界網(wǎng)絡(luò)同步能力的下降)。從圖1可以看出，在整個(gè)p值的范圍內(nèi)，PA小世界網(wǎng)絡(luò)的同步能力明顯不及WS小世界網(wǎng)絡(luò)(因?yàn)镽_PA>R_WS)。

    另由圖3可知，在整個(gè)p值的范圍內(nèi)，PA小世界網(wǎng)絡(luò)的節(jié)點(diǎn)度的方差始終大于WS小世界網(wǎng)絡(luò)。因?yàn)閮煞N網(wǎng)絡(luò)的網(wǎng)絡(luò)特征路徑長度l和簇系數(shù)C幾乎相等(由圖2可知)，由此可以推斷，節(jié)點(diǎn)度的不均勻性實(shí)際上對網(wǎng)絡(luò)的同步能力起抑制作用。由此，在WS小世界網(wǎng)絡(luò)中，增強(qiáng)網(wǎng)絡(luò)同步能力的主要因素不是節(jié)點(diǎn)度方差逐漸增大(節(jié)點(diǎn)度方差只是由于小世界網(wǎng)絡(luò)中邊的重連引起的一種很自然且必然的結(jié)果)，網(wǎng)絡(luò)的特征路徑長度下降才是最主要的原因(當(dāng)p值較小時(shí)，盡管度分布的不均勻性抑制了網(wǎng)絡(luò)的同步能力，但由于網(wǎng)絡(luò)的特征路徑長度大幅下降，網(wǎng)絡(luò)的同步能力還是增強(qiáng)了；但是，當(dāng)網(wǎng)絡(luò)的特征路徑長度下降幾乎為常數(shù)時(shí)，如果節(jié)點(diǎn)度分布的方差大于一定的臨界值，其抑制作用就比較明顯了，如圖1和圖3所示)。所以，短的特征路徑長度和均勻的節(jié)點(diǎn)度分布綜合作用才能導(dǎo)致網(wǎng)絡(luò)同步能力的增強(qiáng)。此外，NISHIKAWA T^[9]和HONG H^[10]均認(rèn)為網(wǎng)絡(luò)節(jié)點(diǎn)的最大介數(shù)B_max是表征網(wǎng)絡(luò)同步能力的一種相對合理的因素。降低網(wǎng)絡(luò)節(jié)點(diǎn)的最大介數(shù)B_max將導(dǎo)致網(wǎng)絡(luò)同步能力的增強(qiáng)。圖4的仿真結(jié)果也說明了這個(gè)問題。可以看到，在PA小世界網(wǎng)絡(luò)中，B_max隨p先是單調(diào)下降然后單調(diào)上升，與R隨p的變化趨勢相同。所以，網(wǎng)絡(luò)中節(jié)點(diǎn)的最大介數(shù)B_max的確可以作為表征網(wǎng)絡(luò)同步能力的一種度量。

    由圖4可知，在整個(gè)p值范圍內(nèi)，PA小世界網(wǎng)絡(luò)中節(jié)點(diǎn)的最大介數(shù)始終大于WS小世界網(wǎng)絡(luò)中節(jié)點(diǎn)的最大介數(shù)；而圖1中，在整個(gè)p值范圍內(nèi)，PA小世界網(wǎng)絡(luò)的同步能力始終不及WS小世界網(wǎng)絡(luò)，這從另外一個(gè)側(cè)面反映了最大介數(shù)表征網(wǎng)絡(luò)同步能力的合理性。在無標(biāo)度網(wǎng)絡(luò)中，網(wǎng)絡(luò)中最大節(jié)點(diǎn)度k_max和最大介數(shù)B_max是正相關(guān)的，即k_max越大，通常B_max也越大；在WS小世界網(wǎng)絡(luò)中，變化呈相反的趨勢，隨著k_max的增大，B_max單調(diào)下降，如圖4和圖5所示，在PA小世界網(wǎng)絡(luò)中，k_max和B_max呈現(xiàn)一種相對微妙復(fù)雜的關(guān)系。

3 結(jié)論

    本文研究了一種擇優(yōu)選擇的小世界網(wǎng)絡(luò)模型，基于這種模型，詳盡地研究了網(wǎng)絡(luò)的同步能力與網(wǎng)絡(luò)中的各種幾何特征量(如網(wǎng)絡(luò)平均路徑、簇系數(shù)、度分布以及介數(shù)等)之間的關(guān)系。研究結(jié)果表明，網(wǎng)絡(luò)的特征路徑長度和簇系數(shù)都不能單獨(dú)決定網(wǎng)絡(luò)的同步能力，因?yàn)椋趦烧叨枷嗟鹊那闆r下網(wǎng)絡(luò)仍然可以有很多不同的配置，因而網(wǎng)絡(luò)的同步能力仍然可以存在較大的差異。節(jié)點(diǎn)度分布的不均勻性從本質(zhì)上抑制了網(wǎng)絡(luò)的同步能力。仿真結(jié)果表明，網(wǎng)絡(luò)中節(jié)點(diǎn)的最大介數(shù)是表征網(wǎng)絡(luò)同步能力的一種相對統(tǒng)一的物理量。

參考文獻(xiàn)

[1] NEWMAN M E J.The structure and function of complex networks[J].SIAM Review，2003，45(2)：167-256.

[2] WANG X F，CHEN G R.Synchronization in small-world dynamical networks[J].Bifurcation and Chaos，2002，12(1)：187-192.

[3] LI Z，CHEN G R.Global synchronization and asymptotic stability of complex dynamical networks[J].IEEE Transactions Circuit and System，2006，53(1)：28-33.

[4] WANG X F, CHEN G R.Synchronization in scale-free dynamical networks：robustness and fragility[J].IEEE Transactions on Circuits and Systems I，2002，49(8)：54-62.

[5] ZHAO M，ZHOU T，WANG B H，et al.Relations between average distance, heterogeneity and network synchronizaility[J].Physica A，2006，371(2)：773-780.

[6] WU X，WANG B H，ZHOU T，et al.Synchronizability of highly clustered scale-free networks[J].Chinese Physics Letters，2006，23(4)：1046.

[7] 魏民，王莉，張強(qiáng).基于復(fù)雜網(wǎng)絡(luò)理論的典型電力電子電路復(fù)雜性研究[J].電子技術(shù)應(yīng)用，2011，37(9)：118-121.

[8] MOTTER A E，ZHOU C，KURTHS J.Network synchronization，diffusion，and the paradox of heterogeneity[J].Physical Review E，2005，71(1)：016116.

[9] NISHIKAWA T，MOTTER A E，LAI Y C，et al.Heterogeneity in oscillator networks: are smaller worlds easier to synchronize?[J].Physical Review Letters，2003，91(7)：014010(1-4).

[10] HONG H，KIM B J，CHOI M Y，et al.Factors that predict better synchronizability on complex networks[J].Physical Review E，2004，69(6)：067105(1-4).

[11] BARAHONA M，PECORA L M.Synchronization in small-world systems[J].Physical Review Letters，2002，89(5)：054101(1-4).

作者信息：

呂  瑛，李穎華

(西北工業(yè)大學(xué)明德學(xué)院 信息工程學(xué)院，陜西 西安710124)