基于隨機(jī)交叉機(jī)制的同步優(yōu)化網(wǎng)絡(luò)模型

王 丹，李彥平，郝彬彬

（1.沈陽大學(xué)裝備制造綜合自動化重點實驗室，遼寧沈陽 110044；2.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽 110004）

基于隨機(jī)交叉機(jī)制的同步優(yōu)化網(wǎng)絡(luò)模型

王 丹1，李彥平1，郝彬彬2

（1.沈陽大學(xué)裝備制造綜合自動化重點實驗室，遼寧沈陽 110044；2.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽 110004）

在不改變網(wǎng)絡(luò)度分布的前提下，采用隨機(jī)交叉機(jī)制對網(wǎng)絡(luò)的同步能力進(jìn)行優(yōu)化，提出了一種無標(biāo)度網(wǎng)絡(luò)的同步優(yōu)化網(wǎng)絡(luò)模型.在同步能力提高的過程中，觀察網(wǎng)絡(luò)匹配特性、聚類系數(shù)、特征路徑長度和最大介數(shù)的變化趨勢.仿真結(jié)果表明，對于類型Ⅰ無標(biāo)度網(wǎng)絡(luò)，最大介數(shù)與同步能力沒有相關(guān)性，而對于類型Ⅱ無標(biāo)度網(wǎng)絡(luò)，最大介數(shù)隨著同步能力的增加而減小.無論哪一種類型的無標(biāo)度網(wǎng)絡(luò)，網(wǎng)絡(luò)同步能力增加時同配特性均降低.

復(fù)雜網(wǎng)絡(luò)；同步優(yōu)化；網(wǎng)絡(luò)模型

目前研究網(wǎng)絡(luò)結(jié)構(gòu)特性與同步能力之間的關(guān)系是復(fù)雜網(wǎng)絡(luò)同步問題研究的前提和熱點之一.早期的關(guān)于同步能力的研究主要集中在具有完全規(guī)則拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，其中的兩個典型例子是耦合映象格子和細(xì)胞神經(jīng)網(wǎng)絡(luò).隨著小世界和無標(biāo)度特性的提出，人們注意到復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)同步特性起著重要的作用，使得人們開始關(guān)注網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)的同步化行為之間的關(guān)系，希望得到同步最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu).目前也有許多文獻(xiàn)通過改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來提高網(wǎng)絡(luò)的同步能力［1-6］.Fan和Wang給出了演化網(wǎng)絡(luò)的同步最優(yōu)演化模型和同步優(yōu)先演化網(wǎng)絡(luò)模型，在同步最優(yōu)演化模型中，每條新邊的加入都選擇使網(wǎng)絡(luò)的同步化性能達(dá)到最優(yōu)的節(jié)點相連.而在同步優(yōu)化網(wǎng)絡(luò)模型中，在每條新邊加入時優(yōu)先選取同步能力強(qiáng)的連接方式.同步最優(yōu)演化模型和同步優(yōu)化網(wǎng)絡(luò)模型與BA無標(biāo)度網(wǎng)絡(luò)相比更容易實現(xiàn)同步.Fan等人提出的這兩種模型，網(wǎng)絡(luò)的規(guī)模是不斷的增長的演化模型.

現(xiàn)有的研究表明，許多真實的網(wǎng)絡(luò)都具有無標(biāo)度特性，大部分的工作也都是針對無標(biāo)度網(wǎng)絡(luò)的結(jié)構(gòu)特性對網(wǎng)絡(luò)同步能力的影響進(jìn)行的研究.基于隨機(jī)重連，在網(wǎng)絡(luò)的度分布固定不變的情況下，是否存在一種同步最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)呢？這種同步能力強(qiáng)的網(wǎng)絡(luò)的結(jié)構(gòu)特性如何？因此，本文在度分布不變的前提下，提出了基于隨機(jī)重連的同步優(yōu)化無標(biāo)度網(wǎng)絡(luò)模型.分別研究在提高網(wǎng)絡(luò)的同步能力的同時，兩種同步類型網(wǎng)絡(luò)的結(jié)構(gòu)特性與同步能力的關(guān)系.發(fā)現(xiàn)同配特性、聚類系數(shù)、最大介數(shù)和網(wǎng)絡(luò)的特征路徑長度等參數(shù)在網(wǎng)絡(luò)同步能力增強(qiáng)的過程中不是單獨的一個量發(fā)生了改變，而是整體都發(fā)生變化.

1 無標(biāo)度網(wǎng)絡(luò)的同步優(yōu)化網(wǎng)絡(luò)模型

目前有很多文獻(xiàn)研究了各種特征參數(shù)與網(wǎng)絡(luò)同步能力的關(guān)系.大部分真實網(wǎng)絡(luò)都具有無標(biāo)度特性，因此，這些研究工作主要集中在無標(biāo)度網(wǎng)絡(luò)特性的研究.通常都是改變網(wǎng)絡(luò)的一個參數(shù)，研究對網(wǎng)絡(luò)同步能力帶來的影響.例如文獻(xiàn)［7］基于隨機(jī)重連調(diào)節(jié)聚類系數(shù)，研究聚類系數(shù)對網(wǎng)絡(luò)同步能力的影響.文獻(xiàn)［8］基于隨機(jī)重連調(diào)節(jié)度相關(guān)特性，研究同配參數(shù)對網(wǎng)絡(luò)同步能力的影響.受以上這幾篇文獻(xiàn)的啟發(fā)，提出基于交叉重連機(jī)制的同步優(yōu)化算法，而在整個交叉重連的過程中保證網(wǎng)絡(luò)度的分布是固定不變的，得到的網(wǎng)絡(luò)仍然是無標(biāo)度網(wǎng)絡(luò).研究在網(wǎng)絡(luò)同步能力逐漸增強(qiáng)的過程中，網(wǎng)絡(luò)同步能力與網(wǎng)絡(luò)匹配參數(shù)、聚類系數(shù)、特征路徑長度和網(wǎng)絡(luò)最大中心介數(shù)的關(guān)系.

無標(biāo)度網(wǎng)絡(luò)的同步優(yōu)化算法如下：

（1）隨機(jī)選擇網(wǎng)絡(luò)中存在的兩條邊e1＝x1x2和e2＝x3x4，使得x1≠x2≠x3≠x4，并且x1與x4之間、x2與x3之間不存在連接.

（2）交叉互換兩條邊，得到x1x4和x2x3，同時移除邊e1，e2.

（3）對于類型Ⅰ網(wǎng)絡(luò)而言，如果邊的交叉互換能降低網(wǎng)絡(luò)的第二大特征值λ2，則網(wǎng)絡(luò)的同步能力得到增強(qiáng)，保留此次交叉連接.對于類型Ⅱ網(wǎng)絡(luò)而言，如果邊的交叉互換能降低網(wǎng)絡(luò)的特征值比值R，則網(wǎng)絡(luò)的同步能力得到增強(qiáng)，保留此次交叉連接.

重復(fù)以上的過程，就可以在保證網(wǎng)絡(luò)度分布不變的前提下，提高網(wǎng)絡(luò)同步能力，得到無標(biāo)度網(wǎng)絡(luò)的同步優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)，在網(wǎng)絡(luò)同步能力提高的同時，研究網(wǎng)絡(luò)結(jié)構(gòu)特性的變化.研究同配參數(shù)、聚類系數(shù)、特征路徑長度、最大介數(shù)等對網(wǎng)絡(luò)同步能力的影響.其中同配參數(shù)r是描述網(wǎng)絡(luò)度分布的相關(guān)特性的參數(shù)，r＞0網(wǎng)絡(luò)中度數(shù)大的節(jié)點更傾向于與度數(shù)大的節(jié)點相連時，網(wǎng)絡(luò)是同配的.反之，r＜0表示整個網(wǎng)絡(luò)呈現(xiàn)異配性，網(wǎng)絡(luò)中度數(shù)大的節(jié)點更傾向于與度數(shù)小的節(jié)點相連，那么該網(wǎng)絡(luò)是異配的；r＝0表示網(wǎng)絡(luò)結(jié)構(gòu)不存在相關(guān)性.r按照式（1）計算［9］.

聚類系數(shù)C主要用來衡量網(wǎng)絡(luò)集團(tuán)化程度，在網(wǎng)絡(luò)特性中是一個比較重要的度量參數(shù).網(wǎng)絡(luò)的平均最短路徑l，也稱為網(wǎng)絡(luò)的特征路徑長度.目前對網(wǎng)絡(luò)特征路徑長度與網(wǎng)絡(luò)同步能力的研究結(jié)果顯示，大多數(shù)的作者指出網(wǎng)絡(luò)的特征路徑長度越短，網(wǎng)絡(luò)的同步能力越強(qiáng).另外，文獻(xiàn)［10］指出網(wǎng)絡(luò)的最大介數(shù)Bmax是衡量網(wǎng)絡(luò)同步能力的標(biāo)準(zhǔn).指出網(wǎng)絡(luò)的最大介數(shù)越大，網(wǎng)絡(luò)中單個節(jié)點的負(fù)載就越大，網(wǎng)絡(luò)容易發(fā)生擁塞，使得整個網(wǎng)絡(luò)的全局同步能力受到抑制，甚至不能實現(xiàn)同步.但是文獻(xiàn)［11］指出，單獨用一個最大介數(shù)Bmax來描述網(wǎng)絡(luò)的同步能力是不確切的.文獻(xiàn)［12］調(diào)節(jié)無標(biāo)度網(wǎng)絡(luò)的聚類系數(shù)，指出聚類系數(shù)越大網(wǎng)絡(luò)的同步能力越差.而文獻(xiàn)［8］研究了匹配參數(shù)對網(wǎng)絡(luò)同步能力的影響，給出網(wǎng)絡(luò)度相關(guān)的同配性增加時類型Ⅱ網(wǎng)絡(luò)的同步能力降低，類型Ⅰ網(wǎng)絡(luò)的同步能力增加.以上文獻(xiàn)在研究網(wǎng)絡(luò)結(jié)構(gòu)和同步能力的關(guān)系時，通過改變網(wǎng)絡(luò)的結(jié)構(gòu)特性，觀察對同步能力的影響.而這里我們關(guān)心的是度在分布固定的條件下，同步優(yōu)化的無標(biāo)度網(wǎng)絡(luò)所具有的結(jié)構(gòu)特性.

2 仿真分析

小世界網(wǎng)絡(luò)就是指具有大的聚類系數(shù)和小的特征路徑長度的網(wǎng)絡(luò)，例如WS小世界網(wǎng)絡(luò)模型和NW小世界網(wǎng)絡(luò)模型.小世界現(xiàn)象是自然界普遍存在的特性，真實網(wǎng)絡(luò)中還存在著另外一種特性，就是網(wǎng)絡(luò)的無標(biāo)度特性.例如BA無標(biāo)度網(wǎng)絡(luò).但是BA無標(biāo)度網(wǎng)絡(luò)不具備高的聚類系數(shù).現(xiàn)實生活中的網(wǎng)絡(luò)很多同時具有無標(biāo)度特性和小世界特性，因此，這里我們研究比較符合真實網(wǎng)絡(luò)特性的高聚類系數(shù)的無標(biāo)度網(wǎng)絡(luò).Holme-Kim（HK）模型是在BA無標(biāo)度網(wǎng)絡(luò)模型的基礎(chǔ)上，引入了三角結(jié)構(gòu)，提高了網(wǎng)絡(luò)的聚類系數(shù)［13］.HK模型不僅具備與BA模型同樣的度分布，同時又具有較高的聚類系數(shù).HK模型可以通過參數(shù)0≤p≤1來調(diào)節(jié)網(wǎng)絡(luò)的聚類系數(shù).以HK模型為初始的網(wǎng)絡(luò)模型，調(diào)節(jié)聚類系數(shù)的參數(shù)p選為0.5.網(wǎng)絡(luò)的規(guī)模為N＝1 000，每個時間步加入到網(wǎng)絡(luò)中的節(jié)點具有的邊數(shù)為m＝3.采用本文所提出的無標(biāo)度同步優(yōu)化網(wǎng)絡(luò)的算法.如果某一次的隨機(jī)交叉連接提高了網(wǎng)絡(luò)的同步能力，那么網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行一次更新.對網(wǎng)絡(luò)的各個特征參數(shù)進(jìn)行一次計算.不斷的重復(fù)這個過程.仿真中采用t＝100 000次的交叉連接作為程序結(jié)束的判定標(biāo)準(zhǔn).類型Ⅰ網(wǎng)絡(luò)，采用降低耦合矩陣第二大特征值作為網(wǎng)絡(luò)結(jié)構(gòu)更新的判定標(biāo)準(zhǔn).類型Ⅱ網(wǎng)絡(luò)，采用降低耦合矩陣特征值比值作為網(wǎng)絡(luò)結(jié)構(gòu)更新的判定標(biāo)準(zhǔn).

圖1給出了類型Ⅰ網(wǎng)絡(luò)結(jié)構(gòu)特性與同步能力比較.圖中，橫坐標(biāo)cv表示網(wǎng)絡(luò)的結(jié)構(gòu)更新次數(shù).在程序運行過程中要符合第2節(jié)中所提出的三條標(biāo)準(zhǔn)，確保網(wǎng)絡(luò)中的節(jié)點不能與自身相連，節(jié)點對之間也不存在重邊，并且提高了網(wǎng)絡(luò)的同步能力，才能更新網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)行結(jié)構(gòu)特性的統(tǒng)計.在網(wǎng)絡(luò)結(jié)構(gòu)不斷變化的過程中，λ2越來越小，網(wǎng)絡(luò)的全局同步能力增強(qiáng).隨著λ2減小的過程，觀察網(wǎng)絡(luò)其他特性的變化趨勢.圖1前四個子圖分別表示網(wǎng)絡(luò)的同配參數(shù)r，網(wǎng)絡(luò)的聚類系數(shù)C，網(wǎng)絡(luò)的最大介數(shù)Bmax以及網(wǎng)絡(luò)的特征路徑長度l.對于類型Ⅰ網(wǎng)絡(luò)而言，在網(wǎng)絡(luò)的同步能力不斷增加時，網(wǎng)絡(luò)的同配參數(shù)r越來越小，網(wǎng)絡(luò)度數(shù)大的節(jié)點更傾向于與度數(shù)小的節(jié)點相連.網(wǎng)絡(luò)的聚類系數(shù)和網(wǎng)絡(luò)的平均最短路徑都在不斷的減小.網(wǎng)絡(luò)同步能力增強(qiáng)時，網(wǎng)絡(luò)明顯的表現(xiàn)出聚類系數(shù)的降低和最短路徑的減小.但是網(wǎng)絡(luò)的最大介數(shù)Bmax與網(wǎng)絡(luò)同步能力不存在明確的關(guān)系.甚至在第400～800次更新矩陣時，網(wǎng)絡(luò)的最大介數(shù)時而增大，時而減小.而在這個過程中網(wǎng)絡(luò)的同步能力是不斷的增加的.

圖1 類型Ⅰ網(wǎng)絡(luò)結(jié)構(gòu)特性與同步能力比較Fig.1 Relations between structure characteristics and synchronizability for TypeⅠnetwork

圖2 類型Ⅱ網(wǎng)絡(luò)結(jié)構(gòu)特性與同步能力比較Fig.2 Relations between structure characteristics and synchronizability for TypeⅡnetwork

圖2給出了類型Ⅱ網(wǎng)絡(luò)結(jié)構(gòu)特性與同步能力比較.網(wǎng)絡(luò)以HK模型為初始狀態(tài)，網(wǎng)絡(luò)保持度分布不變，調(diào)節(jié)網(wǎng)絡(luò)的連接結(jié)構(gòu)，使得網(wǎng)絡(luò)的特征值比值R不斷減小.圖2中，橫坐標(biāo)表示網(wǎng)絡(luò)的迭代次數(shù).確保網(wǎng)絡(luò)中的節(jié)點不能與自身相連，節(jié)點對之間也不存在重邊，并且降低了網(wǎng)絡(luò)的特征值比值，才能更新網(wǎng)絡(luò)結(jié)構(gòu)，統(tǒng)計網(wǎng)絡(luò)特征參數(shù).在網(wǎng)絡(luò)結(jié)構(gòu)不斷變化的過程中，R越來越小，網(wǎng)絡(luò)的全局同步能力增強(qiáng).隨著R減小的過程，我們觀察網(wǎng)絡(luò)其他特性的變化.圖2前四個子圖分別表示網(wǎng)絡(luò)的同配參數(shù)r，網(wǎng)絡(luò)的聚類系數(shù)C，網(wǎng)絡(luò)的最大介數(shù)Bmax以及網(wǎng)絡(luò)的特征路徑長度l.對于類型Ⅱ網(wǎng)絡(luò)而言，在度分布不變的前提下，網(wǎng)絡(luò)同步能力增強(qiáng)時，匹配參數(shù)、聚類系數(shù)、平均最短路徑和網(wǎng)絡(luò)的最大介數(shù)Bmax減小.

在度分布不變的前提下，兩種同步類型網(wǎng)絡(luò)的同步能力增加時，網(wǎng)絡(luò)的匹配參數(shù)不斷的減小.表面上看，我們的結(jié)論和文獻(xiàn)［8］得到的結(jié)論并不一致，實際上兩者的結(jié)論并不矛盾.文獻(xiàn)［8］是單獨調(diào)節(jié)匹配特性，研究其與同步能力的關(guān)系.而我們是研究同步優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)具有的特性，網(wǎng)絡(luò)的整體特性，包括聚類系數(shù)、最短路徑等都發(fā)生了變化.整體的結(jié)構(gòu)參數(shù)變化帶來的同步能力的變化，網(wǎng)絡(luò)同步能力的增加是網(wǎng)絡(luò)整體結(jié)構(gòu)特性共同作用產(chǎn)生的結(jié)果.研究網(wǎng)絡(luò)整體結(jié)構(gòu)特性對網(wǎng)絡(luò)同步能力的影響，尤其是定量的給出公式化的描述，仍然是一個亟待解決的難點問題.

3 結(jié) 論

本文提出了一種基于交叉重連機(jī)制的同步優(yōu)化模型.在網(wǎng)絡(luò)度分布不變的前提下，采用隨機(jī)交叉重連的機(jī)制對網(wǎng)絡(luò)的同步能力進(jìn)行優(yōu)化，得到了無標(biāo)度網(wǎng)絡(luò)的同步優(yōu)化網(wǎng)絡(luò)模型.對于類型Ⅰ網(wǎng)絡(luò)和類型Ⅱ網(wǎng)絡(luò)，網(wǎng)絡(luò)在同步能力增強(qiáng)時網(wǎng)絡(luò)的非匹配特性增加，網(wǎng)絡(luò)中度數(shù)大的節(jié)點更傾向于與度數(shù)小的節(jié)點相連.無論是哪一種同步類型網(wǎng)絡(luò)，網(wǎng)絡(luò)的同步能力越強(qiáng)，網(wǎng)絡(luò)聚類系數(shù)和平均最短路徑越小.類型I網(wǎng)絡(luò)的最大介數(shù)與網(wǎng)絡(luò)同步能力關(guān)系不明顯，類型II網(wǎng)絡(luò)隨同步能力增強(qiáng)，網(wǎng)絡(luò)的最大介數(shù)減小.

［1］Fan J，Wang X F.On synchronization in scale-free dynamical networks［J］.Physica A，2005，349：443-451.

［2］Fan J，Li X，Wang X F.On synchronous preference of complex dynamical networks［J］.Physica A，2005，355：657-666.

［3］Zeng A，Son S W，Yeung C H，et al.Enhancing synchronization by directionality in complex networks［J］.Physical Review E，2011，83（4）：045101.

［4］Yuan W J，Zhou C S.Interplay between structure and dynamics in adaptive complex networks：Emergence and amplification of modularity by adaptive dynamics［J］.

Physical Review E，2011，84（1）：016116.

［5］Watanabe T，Masuda N.Enhancing the spectral gap of networks by node removal［J］.Physical Review E，2010，82（4）：046102.

［6］Boccaletti S，Hwang D H，Chavez M，et al.Synchronization in dynamical networks：Evolution along commutative graphs［J］.Physical Review E，2006，74（1）：016102.

［7］McGraw P N，Menzinger M.Clustering and the synchronization of oscillator networks［J］.Physical Review E，2005，72（1）：015101.

［8］Di Bernardo M，Garofalo F，Sorrentino F.Effects of degree correlation on the synchronization of networks of oscillators［J］.International Journal Bifurcation and Chaos，2007，17，3499-3506.

［9］Newman M E J.Mixing patterns in networks［J］.Physical Review E，2003，67（2）：026126.

［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.

［11］Zhao M，Zhou T，Wang B H，et al.Relations between average distance，heterogeneity and network synchronizability［J］.Physica A，2006，371：773-780.

［12］Wu X，Wang B H，Zhou T，et al.Synchronizability of Highly Clustered Scale-Free Networks［J］.Chinese Physics Letters，2006，23（4）：1046-1049.

［13］Holme P，Kim B J.Growing scale-free networks with tunable clustering［J］.Physical Review E，2002，65（2）：026107.

Synchronization-optimal Network Model based on Random Interchanging Mechanism

WANG Dan1，LI Yanping1，HAO Binbin2

（1.Key Laboratory of Manufacturing Industrial Integrated Automation，Shenyang University，Shenyang 110004，China；2.College of Information Science and Engineering，Northeastern University，Shenyang 110004，China）

Based on random interchanging mechanism and restricting the degree distribution of network，the synchronization-optimal scale-free network model was proposed.During the course of enhancing synchronizability of network，the changing of assortative coefficient，clustering coefficients，characteristic path length and maximal betweenness were investigated.Simulations showed，there was no relativity between maximal betweenness and synchronizability of Type I network.However，maximal betweenness decreased as the increase of synchronizability of Type II network.Simulations indicated that the disassortative increased as the increase of synchronizability for both Types network.

complex network；synchronization-optimal；network model

N 94

A

1008-9225（2012）03-0043-04

2012-01-11

國家自然科學(xué)基金資助項目（61104029）.

王 丹（1979-），女，遼寧沈陽人，沈陽大學(xué)講師，博士；李彥平（1958-），男，遼寧沈陽人，沈陽大學(xué)教授，博士.

王 穎】