相振子網絡中集聚系數和度分布對復雜度的影響

李玨璇，趙 明(.廣西師范大學物理科學與技術學院,廣西 桂林 54004； 2.廣西科技師范學院機械與電氣工程學院，廣西 柳州 545004)

相振子網絡中集聚系數和度分布對復雜度的影響

李玨璇1,2，趙 明1
(1.廣西師范大學物理科學與技術學院,廣西 桂林 541004； 2.廣西科技師范學院機械與電氣工程學院，廣西 柳州 545004)

分析了復雜網絡的集聚系數和度分布的異質性這兩個重要的描述復雜網絡結構特點的特征量對復雜度的影響。研究發現，增大集聚系數能增大復雜度的最大值以及增大復雜度鐘形曲線的寬度，而增大度分布的異質性不能增大復雜度的最大值卻可以明顯增大復雜度在上升段和下降段的取值。對于小世界網絡集聚系數對復雜度的影響更明顯，而對于無標度網絡，度分布的異質性更能顯著的改變復雜度的取值。進一步加深了人們對描述網絡部分同步狀態的復雜度的認識，為設計合理的網絡結構提供了理論基礎。

復雜度；集聚系數；度分布

0 引言

經過十余年的發展，人們對復雜網絡[1-2]的結構、動力學等性質已經有了比較深刻的了解，目前人們的研究目標已經轉移到更符合實際背景的動力學行為[3-4]上，探討其具體過程及內在結構對動力學行為的影響。就復雜網絡上動力系統的同步現象來說，最初的研究主要考察了復雜網絡的整體同步性質、分析了網絡的各種結構特征量對網絡整體同步能力或穩定性的影響[5-7]，而目前的研究更多集中在網絡的中尺度結構對復雜網絡同步狀態的影響[8-13]上。中尺度結構包括網絡的群落結構、層次結構等，而此時的同步狀態更多的是部分同步而非之前研究的完全同步。以中尺度結構和部分同步狀態為研究目標是因為中尺度結構是一種廣泛存在的復雜網絡結構，并且部分同步而不是完全同步才是更常見的同步現象[14]。

很長時間以來，物理領域對部分同步的研究幾乎是空白的，為了解決這樣的問題，在之前的工作中，我們定義了復雜度的概念[13]：當網絡處于完全的不同步或者接近完全同步狀態時，網絡的同步狀態很簡單，復雜度的值很小；當網絡介于兩者之間處于部分同步狀態時，網絡的同步狀態很復雜，復雜度的值很大。具體說來，隨著耦合強度從0開始增加，網絡中的節點慢慢開始同步到部分同步狀態、再到完全同步狀態的過程中，復雜度的取值從0開始增加到一個小于1的最大值之后再降低到0。這樣，網絡的部分同步狀態就被定量刻畫出來。復雜度的取值與網絡結構和節點間的耦合強度都有關系，我們以貓的腦神經網絡[15]和線蟲的神經網絡[16]為例證明真實的神經網絡處于復雜度最大的結構狀態。在上述工作中，我們只研究了群落結構對復雜度的影響，實際上影響復雜度的網絡結構因素還有很多，本文就探討網絡的團簇結構和度分布對部分同步狀態的影響。本文以小世界網絡[1]和具有初始吸引度的無標度網絡[17-18]為模型，通過能夠保持節點度不變的隨機交叉換邊方法[19-20]討論網絡的聚類系數和度分布的異質性對網絡復雜度[13]的影響。

1 復雜度、隨機交叉換邊方法

1.1 復雜度

本文采用相振子作為節點上的動力系統：

(1)

其中，φi、ωi分別為第i個節點的位相和固有頻率，σ為節點間的耦合強度，N為網絡規模，〈k〉為網絡中節點的平均度，aij為鄰接矩陣的矩陣元，也就是說當節點i和節點j之間有邊相連時aij取值為1，當兩節點間沒有邊相連時aij取值為0。網絡的部分同步狀態用復雜度[13]來描述，為了獲得復雜度，首先就要計算所有節點對之間的平均位相差，注意這個位相差是要經過不同的固有頻率分布、初始位相分布和長時間演化的平均獲得的。本文中固有頻率ω∈(0,1)，節點的位相φ的取值在0到2π之間均勻且隨機分布。由于沒有反相同步現象的存在，平均位相差的取值介于0(同步)到π/2(完全不同步)之間。將0到π/2之間的空間均勻劃分m個，平均位相差落在第l個空間的節點對概率為Pl，那么利用式(2)就可以計算出復雜度：

(2)

其中，Sm為復雜度的最大可能取值，用于歸一化，這時所有的平均位相差均勻地落在m個區間里，即Sm=lnm。本文取m=50。

1.2 隨機交叉換邊算法

我們的工作研究集聚系數和度分布對復雜度的影響，這就需要調節這兩個網絡結構參數，為了在調節的過程中這兩者不互相干擾，采用隨機交叉換邊的方法[19-20]調節網絡結構，在調節的過程中節點的度分布保持不變，而集聚系數卻發生了改變。具體的操作過程是：隨機找到兩條邊并斷開，將這兩個邊交叉重新連接起來，如果經過這個操作網絡的集聚系數變大(小)該操作就保留，否則撤銷。重連過程要保證節點之間沒有重復連邊也不會連接到自身。重復上述操作直到獲得足夠大(小)的集聚系數。

2 集聚系數和度分布對復雜度的影響

由于WS型小世界網絡和具有初始吸引度的無標度網絡具有比較大的集聚系數，因此本文以這兩種網絡模型為研究對象，通過隨機交叉換邊的方法在保證度分布異質性不變的同時逐步降低網絡的集聚系數。

2.1 小世界網絡中的情況

在我們的工作中，取WS型小世界網絡的規模為1 000，平均度為6，重連概率分別為0.001、0.01、0.1，保證網絡具有小世界屬性，這時對應的網絡的平均集聚系數分別為0.68、0.66、0.50，平均度分布的方差μ分別為0.11、0.35、1.07。以這些網絡為初始網絡，對它們進行斷邊重連操作，只保留能使得集聚系數變小的操作，在重連的過程中記錄下來一些典型的集聚系數下的網絡結構，比如當集聚系數降到0.55，0.45，0.35，0.20，0.05時就記錄下網絡結構，并計算其復雜度S隨耦合強度σ的變化關系，如圖1所示。注意在同一幅圖中，例如圖1a，雖然這些網絡的集聚系數不同，但是度分布是保持不變的，也就保證度分布的方差相同。圖1a、b、c分別對應于重連概率為0.001，0.01，0.1的3類初始網絡。可以看到在同一幅圖中即使度分布的方差相同，不同的集聚系數也會使得復雜度曲線截然不同：集聚系數越大曲線越右移、上升段與下降段之間的寬度越大，并且集聚系數越大該現象越明顯；同時注意到：集聚系數越大復雜度的最大值也越大，其所對應的耦合強度也是單調遞增的，兩者之間存在一一對應關系。產生該現象的物理機制如下：通過交叉換邊網絡的集聚系數逐漸減小，在此過程中網絡的平均距離也逐漸降低，網絡中節點之間的連邊也越來越隨機，使得網絡的整體同步能力顯著提高，在小的耦合強度下網絡就能開始同步(復雜度增大)并迅速接近完全同步(復雜度減小)狀態，網絡中不會出現很復雜的同步狀態(最大復雜度比較小)，這就使得網絡的復雜度曲線表現出在小的耦合強度下就能提升并在達到峰值后迅速下降，上升和下降段之間的寬度不寬；但當集聚系數比較大時，網絡中除了少量的長程連邊外絕大多數的邊還局限在小范圍內，網絡的平均距離還是比較大，耦合強度要比較大時網絡才開始出現同步現象(復雜度曲線上升段右移)，增加耦合強度的取值只能使得團簇內部的同步狀態變好卻不能促進整體的同步，網絡中出現復雜的同步狀態(最大復雜度比較大)，耦合強度的持續增加也難以實現網絡的完全同步(復雜度的取值依然較大)，這就是在大的集聚系數時復雜度曲線整體右移、峰值升高并且寬度變大的原因。上述結果表明在小世界網絡中集聚系數對復雜度有很大的影響，大的集聚系數意味著更緊密的局部連接，更有利于網絡中形成同步團簇，進而造成網絡在很大的耦合強度范圍內都能處在比較復雜的同步狀態。

經過仔細觀察還可以發現由于大的集聚系數所造成的復雜度曲線整體右移導致了在耦合強度比較小的區域在相同的耦合強度下集聚系數越大復雜度越小(如圖1中的區域I所示)，在耦合強度很大的區域集聚系數越大復雜度越大(如圖1中的區域III所示)，而當耦合強度介于兩者之間時復雜度隨集聚系數先上升后下降(如圖1中的區域II所示)，復雜度存在最大值。區域I、II的分界線位于最小的集聚系數對應的復雜度曲線的最大值位置σ1，區域II、III的分界線位于最大的集聚系數對應的復雜度曲線的最大值位置σ2。為了更仔細地分析集聚系數對復雜度的影響，將兩者的關系用曲線表示出來，如圖2所示。圖中明顯表現出了對于3個不同的度分布方差，當耦合強度的取值小于σ1時復雜度隨集聚系數的增加單調遞減(所有的點都取在復雜度曲線的上升段)，當耦合強度的取值大于σ2時復雜度隨集聚系數的增加單調遞增(所有的點都取在復雜度曲線的下降段)，而當耦合強度的取值介于兩者之間時復雜度的值表現為先升高(下降段)后降低(上升段)，由于復雜度的最大值與耦合強度之間存在一一對應關系，該曲線的最大值就是對應耦合強度的復雜度最大值。

為了分析度分布的異質性對復雜度的影響，重新排布了圖1中的曲線，將集聚系數相同而度分布的方差不同的曲線畫到了同一幅圖里，如圖3所示。有趣的是，即使度分布方差不同，只要集聚系數相同，同一幅圖中的曲線都非常接近。分析造成這一現象的原因可能是度分布的方差差別不大，比如模擬中3條曲線的度分布方差分別為0.11、0.35和1.07，所有節點的度都非常接近。在后面的結果中可以證明本文分析的正確性。

2.2 具有初始吸引度的無標度網絡中的情況

除了小世界網絡，本文還研究了具有初始吸引度的無標度網絡的情況，該網絡的生成過程與經典的BA無標度網絡類似，都是從初始的m個全連通的節點出發，只不過引入一個初始吸引度k0，即新加入的節點連接到已有節點的概率正比于已有節點的度與初始吸引度的和ki+k0，這樣，通過調節k0的大小就可以獲得具有不同冪指數的無標度網絡。值得注意的是要求k0>-m+1，使得ki+k0>0。在模擬中同樣采用網絡的規模為1 000，平均度為6，而初始吸引度分別取-5.0，-4.0，-3.0，這時對應的網絡的集聚系數分別為0.33、0.17、0.11，對應的網絡的度分布方差分別為29.77、21.78、17.65。與具有相同的網絡規模和平均度的WS小世界網絡比較，此時集聚系數要小一些而度分布方差要遠遠大于小世界網絡的度分布方差。圖4給出了在度分布的異質性相同而集聚系數不同時網絡的復雜度與耦合強度的變化關系，圖4a、4b、4c分別對應初始吸引度為-5.0，-4.0，-3.0的網絡。從圖4可以看出：與小世界網絡的情況不同，相同的度分布情況下集聚系數的不同沒有造成復雜度曲線的明顯差異。仔細觀察就可以發現這是由于在該網絡模型中集聚系數可調節的范圍不是很大，以至于集聚系數的影響難以體現出來。

為了分析度分布的異質性對該網絡的影響，在圖5a-c中給出了集聚系數相同而度分布方差不同的情況下復雜度隨耦合強度的變化曲線，從圖5可以看出在相同的集聚系數下不同的度分布異質性使得不同的網絡具有相接近的復雜度最大值，并且最大值對應的耦合強度也是重合的，但是當耦合強度偏離該最大值附近，復雜度處于上升和下降段時度分布的異質性更大的網絡具有更大的復雜度。為了解釋這一現象，計算了描述系統同步狀態的序參量，序參量的定義如下：

(3)

其中，i為虛數單位，φj為第j個振子的相位，括號〈〉表示對時間取平均。當網絡中各振子振蕩的相位不相關時R=0，當所有振子達到同步時R=1，因此R越大，網絡同步狀態越好。在圖5d中給出了集聚系數為0.11，而度分布方差分別為29.77和17.65的兩個網絡的序參量隨耦合強度的變化關系。有趣的是耦合強度使得復雜度曲線差異比較大時對應的序參量曲線差異也比較大，而復雜度曲線差異比較小時對應的序參量曲線差異也比較小。但這兩種曲線在耦合強度比較大和比較小的時候的排布順序是不同的：對于復雜度曲線，大的度分布異質性總是對應著大的復雜度，但是對于序參量曲線，在耦合強度比較小時度分布異質性大的網絡的序參量相對大，但不十分明顯，而在耦合強度比較大時度分布異質性大的網絡的序參量反而明顯小。通過分析不難理解這種現象：當耦合強度比較小時，在度比較大的節點周圍會形成同步團簇，并且度分布的異質性越大這種同步團簇越容易形成，這使得度分布異質性大的網絡的序參量比較大并且復雜度也較大；當耦合強度比較大時，在不同大度節點周圍形成的同步團簇不容易融合起來，并且度分布異質性越大越不容易融合，這就造成度分布異質性大的網絡的同步狀態更差但復雜度依然較大。

3 結論

本文以小世界網絡和具有初始吸引度的無標度網絡為模型，分析了集聚系數和度分布的異質性對復雜度的影響，研究發現：集聚系數能增大復雜度的最大值以及增大復雜度曲線中峰的寬度，而度分布的異質性不能增大復雜度的最大值卻可以增大復雜度在上升段和下降段的值。在小世界網絡中由于集聚系數取值范圍比較大因此該參數對復雜度的影響比較明顯；在無標度網絡中，由于度分布的異質性有很大的調節空間因此該參數對復雜度的影響比較明顯。我們的工作加深了人們對于網絡結構對復雜度影響的理解，為設計合理有效的網絡結構提供了新的理論基礎。我們的工作目前僅考慮了網絡的度分布的異質性和集聚系數對復雜度的影響，而刻畫復雜網絡結構的參數還有很多，比如度相關性、平均距離、網絡的層次結構等，這些參數對復雜度的影響情況還不清楚，有待于進一步研究。

[1]Watts D J, Strogatz S H. Collective dy-namics of “small-world” networks[J]. Nature, 1998,393:440-442.

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

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

[4]Petter H, Jari S. Temporal networks[J]. Physics Reports,2012, 519: 97-125.

[5]Barahona M，Pecora L M. Synchronization in small-world systems[J]. Phys Rev Lett， 2002，89(5)：054101.

[6]Nishikawa T, Motter A E, Lai Y C, et al. Heterogeneity in oscillator networks: are smaller worlds easier to synchronize?[J]. Phys Rev Lett，2003, 91(1): 014101.

[7]Arenas A, Diaz-Guilera A, Kurths J, et al. Synchronization in complex networks[J]. Phys Rep， 2008,469(3):93-153.

[8]Arenas A, Diaz-Guilera A, Perez-Vicente C J. Synchronization processes in complex networks[J]. Physica D， 2006,224:27-34.

[9]Gomez-Gardenes J , Moreno Y , Arenas A. Paths to synchronization on complex networks[J]. Phys Rev Lett，2007, 98(3):034101.

[10] Chen J, Lu J A, Wu X, et al. Generalized synchronization of complex dynamical networks via impulsive control[J]. Chaos,2009,19(4):043119.

[11] Liu H, Chen J , Lu J A , et al. Generalized synchronization in complex dynamical networks via adaptive couplings[J]. Physica A,2010, 389:1759-1770.

[12] Zhang J , Zhou C , Xu X , et al. Mapping from structure to dynamics: a unified view of dynamical processes on networks [J]. Phys Rev E,2010, 82(2):026116.

[13] Zhao M , Zhou C , Chen Y , et al. Complexity versus modularity and heterogeneity in oscillatory networks: combining segregation and integration in neural systems[J]. Phys Rev E,2010, 82(4):046225.

[14] Stam C J. Nonlinear dynamical analysis of EEG and MEG: review of an emerging field[J]. Clin Neurophysiol 116:2266.

[15] Scannell J W, Burns G A P C, Hilgetag C C, The connectional organization of the cortico-thalamic system of the cat[J]. Cereb Cortex，1999, 9:277-299.

[16] White J G, Southgate E, Thompson J N, et al. The structure of the nervous system of the nematode Caenorhabditis elegans[J].Philosphical Transactions of the Royal Society B Biological Sciences,2011,118(314):1-340.

[17] Dorogovtsev S N , Mendes J F F , Samukhin A N. Structure of growing networks with preferential linking[J]. Phys Rev Lett,2000, 85:4633-4636.

[18] Krapivsky P L , Redner S. Organization of growing random networks[J]. Phys Rev E,2001, 63(6):066123.

[19] Maslov S , Sneppen K. Specificity and stability in topology of protein networks[J]. Science,2002, 296:910-913.

[20] Kim B J. Coherent potential approximation and projection operators for interacting electrons[J]. Phys Rev E,2004, 69(4):045101.

(責任編輯 耿金花)

Effects of Clustering Coefficient and Degree Distribution on Complexity in Oscillator Networks)

LI Juexuan1,2，ZHAO Ming1)

(1.College of Physics and Technology, Guangxi Normal University, Guilin 541004, China； 2.Department of Physics and Information Science, Liuzhou Teachers College, Liuzhou 545004, China)

Complexity is defined to describe the partial synchronization state in complex networks, which is sensitive to the network structure, however, how the structure affects the complexity is still unclear. Clustering coefficient and degree distribution are two typical parameters in complex networks. In this paper, the effects of these two parameters on complexity are studied. After careful study it is found that increasing clustering coefficient would increase the maximal complexity and broaden the width of the complexity curves, and increasing the heterogeneity of the degree distribution will increase the value of rising and falling part of complexity curve but have no effect on the maximal complexity. Furthermore, complexity is sensitive to clustering coefficient in small-world networks and sensitive to heterogeneity of degree distribution in scale-free networks. Our work deepens the knowledge of complexity, and provide useful theory to design complex network structure.

complexity; clustering coefficient; degree distribution

10.13306/j.1672-3813.2016.04.005

2015-03-12；

2015-10-09

國家自然科學基金(11165003)；廣西自然科學基金(2015GXNSFGA139009)；廣西高校優秀人才資助計劃項目

李玨璇(1964-),女,廣西武宣人,高級實驗師,主要研究方向為普通物理實驗。

TP79

A