復(fù)雜網(wǎng)絡(luò)譜粗?；椒ǖ母倪M(jìn)算法?

周建 賈貞?李科贊

1)(桂林理工大學(xué)理學(xué)院,桂林 541004)

2)(桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,桂林 541004)

(2016年10月2日收到;2016年11月21日收到修改稿)

復(fù)雜網(wǎng)絡(luò)譜粗?；椒ǖ母倪M(jìn)算法?

周建1)賈貞1)?李科贊2)

1)(桂林理工大學(xué)理學(xué)院,桂林 541004)

2)(桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,桂林 541004)

(2016年10月2日收到;2016年11月21日收到修改稿)

大規(guī)模網(wǎng)絡(luò)的同步問(wèn)題是網(wǎng)絡(luò)科學(xué)的重要研究課題之一.粗?；椒ㄌ峁┝艘环N將大規(guī)模網(wǎng)絡(luò)轉(zhuǎn)化為小規(guī)模網(wǎng)絡(luò),同時(shí)又能較好地保持原始網(wǎng)絡(luò)的拓?fù)湫再|(zhì)或動(dòng)態(tài)特性的研究途徑,其中比較有代表性的譜粗?；椒茌^好地保持初始網(wǎng)絡(luò)的同步能力.然而,譜粗?；椒ㄔ趯?shí)際計(jì)算中計(jì)算量大、對(duì)實(shí)際大規(guī)模網(wǎng)絡(luò)可執(zhí)行性差.本文提出一種改進(jìn)的譜粗?；惴?能大幅減少計(jì)算量,同時(shí)獲得更好的譜粗?；Ч?通過(guò)理論分析和大量的數(shù)值仿真實(shí)驗(yàn)驗(yàn)證了所提改進(jìn)算法的粗?；Ч陀?jì)算量都明顯優(yōu)于原譜粗?；椒?

復(fù)雜網(wǎng)絡(luò),同步,譜粗?；?改進(jìn)算法

1 引 言

同步是自然界、人類(lèi)社會(huì)和工程技術(shù)領(lǐng)域中一種常見(jiàn)的集合運(yùn)動(dòng)現(xiàn)象,如蛙聲齊鳴、有節(jié)律的鼓掌等.近二十多年來(lái),研究人員對(duì)復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的同步進(jìn)行了大量研究,特別是對(duì)于中尺度網(wǎng)絡(luò)的同步研究取得了豐富的研究成果[1?11].然而,許多實(shí)際網(wǎng)絡(luò)是擁有成千上萬(wàn)甚至上億節(jié)點(diǎn)的大規(guī)模網(wǎng)絡(luò),研究大規(guī)模耦合復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)同步常常會(huì)產(chǎn)生大量的耦合微分方程,給計(jì)算和仿真實(shí)驗(yàn)都帶來(lái)巨大困難,許多中尺度網(wǎng)絡(luò)同步算法在大規(guī)模網(wǎng)絡(luò)研究中難以實(shí)現(xiàn),因此人們提出了一些粗?；椒ㄔ噲D將大規(guī)模網(wǎng)絡(luò)轉(zhuǎn)化為中尺度網(wǎng)絡(luò)來(lái)研究[12?17].粗粒化方法通過(guò)合并相似節(jié)點(diǎn)將大規(guī)模網(wǎng)絡(luò)縮減為中尺度網(wǎng)絡(luò),同時(shí)盡量保持原始網(wǎng)絡(luò)的某些重要性質(zhì),如拓?fù)涮匦曰騽?dòng)力學(xué)性質(zhì)等.近年來(lái),在粗?；难芯糠矫嬉踩〉昧艘恍┲匾M(jìn)展.例如, K im[18]提出了一種粗粒化方法能保持原始網(wǎng)絡(luò)的度分布、聚類(lèi)系數(shù)、同配系數(shù)等性質(zhì);Chen等[19]提出了一種基于網(wǎng)絡(luò)度的粗?；椒?能保持原始網(wǎng)絡(luò)平衡態(tài)統(tǒng)計(jì)分布的一致性.在這些粗?；椒ㄖ?比較典型的是由G feller和Rios[20,21]在2008年提出的譜粗?；?spectral coarse graining,SCG)方法,通過(guò)分析網(wǎng)絡(luò)結(jié)構(gòu)矩陣的特征值譜,合并網(wǎng)絡(luò)中結(jié)構(gòu)相同和相似的節(jié)點(diǎn),從而有效地將大規(guī)模網(wǎng)絡(luò)縮減為小規(guī)模網(wǎng)絡(luò)同時(shí)又能較好地保持初始網(wǎng)絡(luò)的同步能力.Chen等[15]進(jìn)一步研究了SCG方法在聚類(lèi)網(wǎng)絡(luò)中的應(yīng)用效果,Zeng和Lü[16]進(jìn)一步提出了基于有向網(wǎng)絡(luò)的SCG方法,能很好地保持粗粒化網(wǎng)絡(luò)的同步能力.

SCG方法在保持網(wǎng)絡(luò)同步能力方面獨(dú)占優(yōu)勢(shì),然而在確定網(wǎng)絡(luò)中的哪些節(jié)點(diǎn)被合并時(shí)需要反復(fù)判斷,這樣會(huì)產(chǎn)生非常巨大的計(jì)算量,其計(jì)算復(fù)雜度為O(N3)[16].對(duì)于現(xiàn)實(shí)中少則成千上萬(wàn)節(jié)點(diǎn)的網(wǎng)絡(luò),多則上百萬(wàn)甚至上億節(jié)點(diǎn)的大規(guī)模網(wǎng)絡(luò),其巨大的計(jì)算量致使SCG方法在實(shí)際中難以執(zhí)行.為了克服SCG方法計(jì)算量大的缺陷,本文提出了一種改進(jìn)的SCG方法,記為ISCG(improved spectral coarse graining)算法,將計(jì)算復(fù)雜度從O(N3)降到O(N2),同時(shí)還改善了粗?；Ч?所得粗粒化網(wǎng)絡(luò)能夠更好地保持初始網(wǎng)絡(luò)的同步能力.

2 網(wǎng)絡(luò)同步能力的刻畫(huà)

考慮N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),其動(dòng)力學(xué)方程為

其中xi∈Rm表示第i個(gè)節(jié)點(diǎn)的m維狀態(tài)變量;是第i個(gè)節(jié)點(diǎn)的動(dòng)態(tài)方程;δ＞0為耦合強(qiáng)度;H(·):Rm→Rm是節(jié)點(diǎn)內(nèi)部耦合函數(shù); Laplacian矩陣L=(Lij)N×N∈RN×N為外部耦合矩陣,刻畫(huà)了網(wǎng)絡(luò)的耦合拓?fù)浣Y(jié)構(gòu).若網(wǎng)絡(luò)節(jié)點(diǎn)j和i(i=j)相連,則Lij=1,否則Lij=0;Laplacian矩陣L的對(duì)角線(xiàn)元素滿(mǎn)足,即矩陣L滿(mǎn)足耗散耦合條件:.當(dāng)網(wǎng)絡(luò)是無(wú)向無(wú)權(quán)的連通網(wǎng)絡(luò)時(shí),對(duì)應(yīng)的矩陣L是對(duì)稱(chēng)不可約的正半定矩陣,具有非負(fù)特征值且滿(mǎn)足0=λ1＜ λ2≤ ···≤ λN.網(wǎng)絡(luò)(1)同步狀態(tài)x1(t)=x2(t)=···=xN(t)=s(t)的同步流形s(t)滿(mǎn)足=F(s(t)),它可以是孤立節(jié)點(diǎn)的平衡點(diǎn)、周期軌道或混沌軌道.將方程(1)線(xiàn)性化,令ξi為第i個(gè)節(jié)點(diǎn)狀態(tài)的變分,得到變分方程

其中D F(s)和D H(s)分別是F(s)和H(s)關(guān)于s(t)的Jacobi矩陣.將方程(2)對(duì)角化可得到

ηk是矩陣L關(guān)于特征值λk的特征模式.將方程(3)一般化,得到主穩(wěn)定方程:

該方程的最大Lyapunov指數(shù)Lmax是實(shí)變量α的函數(shù),稱(chēng)之為網(wǎng)絡(luò)(1)的主穩(wěn)定函數(shù),記為L(zhǎng)max(α).網(wǎng)絡(luò)(1)的同步化區(qū)域是指使Lmax(α)＜ 0的實(shí)數(shù)α的取值范圍,記為SR,它是由孤立節(jié)點(diǎn)動(dòng)力學(xué)函數(shù)F(xi(t))和內(nèi)連函數(shù)確定的,只要網(wǎng)絡(luò)的耦合強(qiáng)度δ與耦合矩陣L的特征值之積全部落入同步區(qū)域即δλk∈SR(k=2,3,···,N),網(wǎng)絡(luò)(1)就能達(dá)到完全同步[22].網(wǎng)絡(luò)的同步區(qū)域主要分為以下4種類(lèi)型:1)有界區(qū)域(α1,α2); 2)無(wú)界區(qū)域(α1,+∞);3)若干個(gè)有界區(qū)域的并集∪(α1i,α2i);4)空集.一般地,3)和4)的情形下網(wǎng)絡(luò)很難或完全無(wú)法達(dá)到同步,幸運(yùn)的是大多數(shù)網(wǎng)絡(luò)都是1)和2)兩種情形,此時(shí)只有當(dāng)L的特征值滿(mǎn)足λN/λ2＜ α2/α1或者λ2＞ α1/δ時(shí)網(wǎng)絡(luò)才能達(dá)到同步穩(wěn)定狀態(tài)(其中λ2和λN分別為L(zhǎng)ap lacian矩陣的最小非零特征值和最大特征值).這意味著當(dāng)λN/λ2越小或者λ2越大時(shí)網(wǎng)絡(luò)更容易達(dá)到同步,因此在同步研究中,常常用特征值比λN/λ2和最小非零特征值λ2兩個(gè)指標(biāo)來(lái)刻畫(huà)網(wǎng)絡(luò)的同步能力[23].

3 基于網(wǎng)絡(luò)同步的SCG方法

3.1 SCG方法

由于網(wǎng)絡(luò)的同步能力可用λ2或λN/λ2來(lái)刻畫(huà),因此要使粗粒化后的網(wǎng)絡(luò)仍保持原始網(wǎng)絡(luò)的同步能力,就應(yīng)使粗?；昂缶W(wǎng)絡(luò)的λ2或λN/λ2盡可能接近或不變.2008年,Gfeller和Rios[20,21]提出的SCG方法就是依此設(shè)計(jì)的,在縮減網(wǎng)絡(luò)規(guī)模的同時(shí),盡可能地保持網(wǎng)絡(luò)的同步能力.該方法主要解決了兩個(gè)關(guān)鍵問(wèn)題:一是如何合并節(jié)點(diǎn)和更新邊;二是確定哪些節(jié)點(diǎn)可以被合并.

首先,對(duì)于如何合并節(jié)點(diǎn)和更新邊,SCG方法將初始網(wǎng)絡(luò)的N個(gè)節(jié)點(diǎn)標(biāo)記為i=1,2,···,N,粗粒化后網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)記為C=1,2,···,?N,?N為粗?；蟮木W(wǎng)絡(luò)規(guī)模,C也表示初始網(wǎng)絡(luò)中的 ?N個(gè)團(tuán),每個(gè)團(tuán)的節(jié)點(diǎn)將被合并為粗?；W(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn).粗?；缶W(wǎng)絡(luò)的邊(對(duì)應(yīng)新的Lap lacian矩陣可通過(guò)下面的矩陣乘積進(jìn)行更新:

這里,|C|是團(tuán)C中包含節(jié)點(diǎn)的個(gè)數(shù);Ci是節(jié)點(diǎn)i所在團(tuán)C的標(biāo)號(hào),ψ是常用的K ronecker函數(shù).

其次,對(duì)于哪些節(jié)點(diǎn)被合并,分別考慮λ2和λN/λ2兩個(gè)指標(biāo).若考慮指標(biāo)λ2(網(wǎng)絡(luò)(1)的Lap lacian矩陣L的最小非零特征值),記λ2對(duì)應(yīng)的特征向量為p2,將p2中相同或相近的分量對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并,此時(shí)?L的最小非零特征值與λ2相同或相近. 理論上,特征向量p2的兩個(gè)分量和相同或相近,可表示為,其中和分別為p2的N個(gè)分量中的最大值和最小值.實(shí)際計(jì)算時(shí),把區(qū)間劃分為I個(gè)等分區(qū)間,對(duì)落入同一等分區(qū)間的p2分量對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并.一般地,I越小對(duì)應(yīng)的 ?N越小,因此可通過(guò)控制I值的大小來(lái)大致控制粗?；W(wǎng)絡(luò)的規(guī)模.相同或相似節(jié)點(diǎn)的合并過(guò)程及λ2的保持情況如圖1所示.

同理,當(dāng)考慮指標(biāo)λN/λ2(網(wǎng)絡(luò)(1)的Laplacian矩陣L中最大與最小非零特征值之比)時(shí),合并節(jié)點(diǎn)需同時(shí)滿(mǎn)足條件和.實(shí)際計(jì)算時(shí)分別把區(qū)間,劃分為I個(gè)等分區(qū)間(其中pN為最大特征值λN對(duì)應(yīng)的特征向量),找出p2和pN中同時(shí)落入等分區(qū)間內(nèi)的分量,將其對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并.此時(shí)?L的特征值比與λN/λ2相同或相近,即能保持粗?；W(wǎng)絡(luò)的同步能力.

圖1顯示,把結(jié)構(gòu)相同或相似的節(jié)點(diǎn)進(jìn)行合并,網(wǎng)絡(luò)的最小非零特征值λ2變化不大,即網(wǎng)絡(luò)的同步能力能夠很好地被保持.

圖1 (網(wǎng)刊彩色)合并節(jié)點(diǎn)過(guò)程[21]Fig.1.(color on line)Processing ofm erging nodes[21].

3.2 SCG方法的局限

我們通過(guò)大量仿真實(shí)驗(yàn)發(fā)現(xiàn),很多網(wǎng)絡(luò)的特征向量分量分布極不均勻,大多數(shù)分量分布相對(duì)集中、間距較小,極少數(shù)分量分布特別分散且間距很大.以節(jié)點(diǎn)N=100的NW小世界網(wǎng)絡(luò)為例,根據(jù)特征值λ2對(duì)應(yīng)的特征向量p2,將區(qū)間劃分為I=15的等分區(qū)間,p2的分量落入等分區(qū)間內(nèi)的分布情況如圖2所示,圖2中菱形對(duì)應(yīng)p2的所有分量,16條豎線(xiàn)將區(qū)間劃分為15個(gè)等分區(qū)間.從圖2可看出,p2的分量分布極不均勻.因此等區(qū)間劃分節(jié)點(diǎn)時(shí)可能造成有些距離特別近的兩個(gè)分量(對(duì)應(yīng)極相似的節(jié)點(diǎn),如圖2中藍(lán)色菱形對(duì)應(yīng)分量和錳紫色菱形對(duì)應(yīng)分量)被分割到兩個(gè)相鄰區(qū)間中,而與間距更大的分量(對(duì)應(yīng)不太相似的節(jié)點(diǎn))劃分到同一區(qū)間而合并相應(yīng)節(jié)點(diǎn),這會(huì)影響粗?；Ч?另一方面,計(jì)算中需要將每一個(gè)p2分量與等分區(qū)間所有的端點(diǎn)值進(jìn)行比較,依此判斷落在哪個(gè)等分區(qū)間內(nèi),這會(huì)造成較大的計(jì)算量,特別是對(duì)規(guī)模巨大的網(wǎng)絡(luò)更為明顯,其計(jì)算復(fù)雜度為O(N3)[16].例如,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)N=1000時(shí),SCG方法的計(jì)算量達(dá)到10億次.此外,由于p2的分量分布極不均勻,一些等分區(qū)間內(nèi)沒(méi)有分量落入,導(dǎo)致合并后的網(wǎng)絡(luò)規(guī)模隨I變化不大.例如,節(jié)點(diǎn)N=1000的NW小世界網(wǎng)絡(luò),當(dāng)劃分等區(qū)間數(shù)I為102,103,104,105,106時(shí),分別為14,69, 381,871,991,因此I值對(duì)網(wǎng)絡(luò)規(guī)模的控制效果并不理想,也在一定程度上會(huì)影響粗粒化效果.綜上所述,SCG化方法存在兩方面的缺陷.一是計(jì)算量過(guò)大,對(duì)于大規(guī)模網(wǎng)絡(luò)實(shí)際計(jì)算難以實(shí)現(xiàn);二是對(duì)某些網(wǎng)絡(luò)粗?；Ч⒉皇掷硐?

圖2 (網(wǎng)刊彩色)特征向量p2的分量分布情況Fig.2.(color on line)Distribution of com ponentsof eigenvector p2.

4 改進(jìn)的SCG算法

本節(jié)我們?cè)谠椒ǖ幕A(chǔ)上提出一種改進(jìn)的SCG算法,不僅降低了計(jì)算復(fù)雜度,還改善了粗?；Ч?使粗?；蟮木W(wǎng)絡(luò)更好地保持初始網(wǎng)絡(luò)的同步能力.

與SCG方法采取等分區(qū)間確定合并節(jié)點(diǎn)的做法不同,ISCG算法依特征向量分量的分布情況采取分裂聚類(lèi)方法來(lái)確定合并節(jié)點(diǎn).具體做法是:先將特征向量分量由小到大排序,計(jì)算兩兩相鄰分量間的距離,根據(jù)相鄰分量之間的間距大小將分量分裂成若干個(gè)聚類(lèi),然后將每個(gè)聚類(lèi)中對(duì)應(yīng)的節(jié)點(diǎn)合并為一個(gè)節(jié)點(diǎn).選擇間距的大小將決定同一聚類(lèi)中節(jié)點(diǎn)的相似程度和粗粒化網(wǎng)絡(luò)的規(guī)模.例如,選擇較大的前?1個(gè)間距將所有分量分裂成個(gè)聚類(lèi),這個(gè)聚類(lèi)對(duì)應(yīng)節(jié)點(diǎn)合并為個(gè)節(jié)點(diǎn),從而可以精確控制網(wǎng)絡(luò)的規(guī)模,越大,相鄰分量的間距越小,合并節(jié)點(diǎn)的相似度越高,粗?；Ч胶?

下面我們以保持λ2為例進(jìn)一步說(shuō)明ISCG算法的步驟. 首先假設(shè)λ2的特征向量p2的分量由小到大排序?yàn)橄噜彿至恐g的間距為i=1,···,N?1),假設(shè)選擇最大的前3個(gè)間距,分別記為這3個(gè)間距將分裂成4個(gè)聚類(lèi),分別為,其中間距分裂區(qū)間時(shí)對(duì)應(yīng)的左右端點(diǎn)分別為和和和,再將這4個(gè)聚類(lèi)中對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并,即得到 ?N=4的粗粒化網(wǎng)絡(luò).由此可見(jiàn),ISCG算法可以根據(jù)需要,選擇一定的間距將原始網(wǎng)絡(luò)N個(gè)節(jié)點(diǎn)合并到任何指定規(guī)模 ?N的粗?；W(wǎng)絡(luò),并且合理區(qū)分不同節(jié)點(diǎn)間的相似程度,從而能確保被合并節(jié)點(diǎn)之間的相似程度高于不同聚類(lèi)之間節(jié)點(diǎn)的相似程度,因此粗?；Ч^SCG方法更好.在計(jì)算量方面,由于ISCG算法只需計(jì)算分量之間的間距,而不需判斷比較每一個(gè)特征向量分量落入等區(qū)間的情況,只要確定了粗?；W(wǎng)絡(luò)模型,便可一次完成所有節(jié)點(diǎn)的合并,因此大幅減少了計(jì)算量,其計(jì)算復(fù)雜度為O(N2).此外,ISCG算法能精確控制粗?；W(wǎng)絡(luò)規(guī)模,這點(diǎn)優(yōu)于SCG算法對(duì)粗?；W(wǎng)絡(luò)規(guī)模的控制.

類(lèi)似地,對(duì)于保持特征值比λN/λ2的情況,可根據(jù)λ2和λN的特征向量p2和pN的分量之間的間距將各分量分裂成不同的聚類(lèi),將同時(shí)分裂在同一聚類(lèi)中對(duì)應(yīng)節(jié)點(diǎn)合并為一個(gè)節(jié)點(diǎn),計(jì)算過(guò)程與上述保持λ2的情形類(lèi)似,這里不再贅述.

5 數(shù)值仿真

本節(jié)將分別對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)和耦合相振子網(wǎng)絡(luò)模型進(jìn)行數(shù)值仿真,分別應(yīng)用ISCG算法和SCG方法對(duì)網(wǎng)絡(luò)進(jìn)行粗?；?比較兩種不同粗?；惴▽?duì)幾種典型網(wǎng)絡(luò)同步能力的保持效果.

5.1 連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)的同步效果

下面對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)模型(1)進(jìn)行數(shù)值仿真.分別選取四種典型的復(fù)雜網(wǎng)絡(luò),即NW小世界網(wǎng)絡(luò)、ER隨機(jī)網(wǎng)絡(luò)、BA無(wú)標(biāo)度網(wǎng)絡(luò)和一類(lèi)復(fù)雜聚類(lèi)網(wǎng)絡(luò)[15],分別應(yīng)用ISCG和SCG算法粗?；W(wǎng)絡(luò),觀察并比較粗?；Ч?原始網(wǎng)絡(luò)規(guī)模均為N=1000.

圖3和圖4展示了分別采用ISCG和SCG兩種算法對(duì)四種典型網(wǎng)絡(luò)進(jìn)行粗?；慕Y(jié)果和網(wǎng)絡(luò)同步能力的保持情況.無(wú)論對(duì)哪種網(wǎng)絡(luò),采取ISCG算法獲得的粗?；W(wǎng)絡(luò)與原始網(wǎng)絡(luò)的λ2和λN/λ2的近似程度都明顯優(yōu)于SCG方法獲得的粗?；W(wǎng)絡(luò),說(shuō)明ISCG算法的粗?；Ч屯侥芰Ρ３智闆r優(yōu)于SCG方法.從運(yùn)算時(shí)間上看,在實(shí)驗(yàn)中獲得相同規(guī)模的粗粒化網(wǎng)絡(luò),ISCG算法比SCG方法所用的時(shí)間大大減少.以上述N=1000的NW小世界網(wǎng)絡(luò)為例,在保持λ2的情形,獲得 ?N=600的粗?；W(wǎng)絡(luò),采用ISCG算法和SCG方法在MATLAB軟件試驗(yàn)中的運(yùn)行時(shí)間分別是2.94 s和18.4 s.實(shí)際上,由于后者需要經(jīng)過(guò)多次反復(fù)實(shí)驗(yàn)才能獲得規(guī)模 ?N=600的粗?；W(wǎng)絡(luò),故實(shí)際獲得結(jié)果時(shí)間遠(yuǎn)不止18.4 s,而ISCG算法可以精確控制粗?；W(wǎng)絡(luò)規(guī)模,一次完成實(shí)驗(yàn),故運(yùn)行時(shí)間只需要2.94 s,可見(jiàn)ISCG算法的運(yùn)算速度大幅提高.此外, ISCG算法可以精確獲得任意規(guī)模的粗?；W(wǎng)絡(luò),從而能夠更精細(xì)地展示網(wǎng)絡(luò)的粗?；葑冞^(guò)程,而SCG方法卻做不到這點(diǎn).當(dāng)然,粗?；W(wǎng)絡(luò)規(guī)模越小,合并的節(jié)點(diǎn)就越多,對(duì)原始網(wǎng)絡(luò)同步能力的保持效果越差,但對(duì)于同等規(guī)模的粗?；W(wǎng)絡(luò),顯然ISCG算法的同步能力的保持效果更好.

圖3 (網(wǎng)刊彩色)分別采用ISCG和SCG算法獲得粗粒化網(wǎng)絡(luò)對(duì)λ2的保持情況 (a)NW小世界網(wǎng)絡(luò);(b)ER隨機(jī)網(wǎng)絡(luò);(c)BA無(wú)標(biāo)度網(wǎng)絡(luò);(d)聚類(lèi)網(wǎng)絡(luò)Fig.3.(color on line)Them aintaining ofλ2obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

圖4 (網(wǎng)刊彩色)分別采用ISCG和SCG算法獲得粗?；W(wǎng)絡(luò)對(duì)λN/λ2的保持情況 (a)NW 小世界網(wǎng)絡(luò); (b)ER隨機(jī)網(wǎng)絡(luò);(c)BA無(wú)標(biāo)度網(wǎng)絡(luò);(d)聚類(lèi)網(wǎng)絡(luò)Fig.4.(color on line)The m aintaining ofλN/λ2obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

5.2 耦合K u ram oto相振子網(wǎng)絡(luò)的同步效果

下面對(duì)耦合Kuramoto網(wǎng)絡(luò)[24,25]模型進(jìn)行數(shù)值仿真,進(jìn)一步比較ISCG和SCG算法對(duì)保持相振子同步的效果.耦合Kuramoto網(wǎng)絡(luò)模型方程為

其中,ωi表示第i個(gè)振子的固有頻率,σ表示全局振子耦合強(qiáng)度,Aij為鄰接矩陣,θi表示第i個(gè)振子的相位,N表示振子的個(gè)數(shù).全局振子的相同步程度可用序參量r(t)刻畫(huà):

其中序參量r(t)(∈[0,1])為0時(shí)表示全局振子以各自的固有頻率運(yùn)動(dòng),即完全不同步狀態(tài),為1時(shí)表示全局振子以相同頻率運(yùn)動(dòng),即達(dá)到完全同步狀態(tài);?(t)表示全局振子的平均相位.因此可通過(guò)序參量r(t)來(lái)研究粗粒化網(wǎng)絡(luò)的同步保持情況.

以上文N=1000的NW小世界網(wǎng)絡(luò)、ER隨機(jī)網(wǎng)絡(luò)、BA無(wú)標(biāo)度網(wǎng)絡(luò)、聚類(lèi)網(wǎng)絡(luò)為例,采用ISCG和SCG算法粗?；W(wǎng)絡(luò),得到網(wǎng)絡(luò)規(guī)模 ?N均為200的ISCG網(wǎng)絡(luò)和SCG網(wǎng)絡(luò),ωi在(?0.5,0.5)中隨機(jī)選擇,初始相位θi在(?π,π)中隨機(jī)選擇,σ分別為0.2,0.2,1.5,0.5.其序參量r(t)保持情況如圖5所示.

圖5展示了分別采用ISCG和SCG兩種算法對(duì)振子相同步的保持情況,可見(jiàn)ISCG獲得網(wǎng)絡(luò)的序參量r(t)收斂性與原始網(wǎng)絡(luò)基本一致,且ISCG算法獲得的粗?；W(wǎng)絡(luò)同步能力保持情況優(yōu)于SCG方法.

圖5 (網(wǎng)刊彩色)分別采用ISCG和SCG算法保持序參量r(t)的情況 (a)NW小世界網(wǎng)絡(luò);(b)ER隨機(jī)網(wǎng)絡(luò); (c)BA無(wú)標(biāo)度網(wǎng)絡(luò);(d)聚類(lèi)網(wǎng)絡(luò)Fig.5.(color on line)The m aintaining of the order param eter r(t)obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

6 結(jié) 論

復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的耦合拓?fù)浣Y(jié)構(gòu)直接影響網(wǎng)絡(luò)的動(dòng)力學(xué)性質(zhì).一般來(lái)說(shuō),兩個(gè)節(jié)點(diǎn)的外部連接相同或相近,意味著它們接收外部的信息和作用也相同或相近,因而具有相近的動(dòng)力學(xué)性質(zhì),SCG方法的基本思想正是基于這一點(diǎn),把網(wǎng)絡(luò)中外部鏈接相同或相近似的節(jié)點(diǎn)進(jìn)行合并,從而把大規(guī)模網(wǎng)絡(luò)縮減為中尺度網(wǎng)絡(luò),這是研究大規(guī)模網(wǎng)絡(luò)的重要途徑之一.本文提出的ISCG算法,以特征向量分量之間的間距大小來(lái)劃分相似節(jié)點(diǎn),從而自適應(yīng)地對(duì)聚類(lèi)節(jié)點(diǎn)進(jìn)行分組,能夠確保網(wǎng)絡(luò)中越相近的節(jié)點(diǎn)越被優(yōu)先合并,避免了SCG方法對(duì)節(jié)點(diǎn)進(jìn)行硬性分組而導(dǎo)致某些情況下相似節(jié)點(diǎn)被拆分而與不相近節(jié)點(diǎn)合并的缺陷.仿真實(shí)驗(yàn)也驗(yàn)證了ISCG算法既能很好地改善粗?；Ч?又大幅降低了運(yùn)算的時(shí)間復(fù)雜度.

從算法分析和仿真結(jié)果看,在粗?；^(guò)程中應(yīng)該存在一個(gè)最優(yōu)的聚類(lèi)個(gè)數(shù),即存在一個(gè)既能很好地保持原始網(wǎng)絡(luò)同步能力又能最大程度地縮減原始網(wǎng)絡(luò)規(guī)模的聚類(lèi)個(gè)數(shù),例如,用λ2來(lái)刻畫(huà)網(wǎng)絡(luò)的同步能力,可以滿(mǎn)足(ε比較小,可設(shè)定)的對(duì)應(yīng)的最小 ?N即為最優(yōu)聚類(lèi)個(gè)數(shù).以上文中所列舉的四種典型即NW小世界網(wǎng)絡(luò)、ER隨機(jī)網(wǎng)絡(luò)、BA無(wú)標(biāo)度網(wǎng)絡(luò)和聚類(lèi)網(wǎng)絡(luò)為例,可求得最優(yōu)聚類(lèi)個(gè)數(shù) ?N分別為915,805,795,768.然而,對(duì)于最優(yōu)的聚類(lèi)個(gè)數(shù)問(wèn)題,還有更多的未知需要我們?nèi)ヌ剿?例如衡量最優(yōu)粗?；垲?lèi)個(gè)數(shù)的指標(biāo)函數(shù)如何確定?各種不同結(jié)構(gòu)的網(wǎng)絡(luò)的最優(yōu)指標(biāo)有何差異?且有待我們進(jìn)行更深入的探索研究,也是我們今后的努力方向.

本文提出的ISCG算法具有誤差更小、效果更優(yōu)、運(yùn)算量大幅降低等諸多優(yōu)點(diǎn),能極大地改善原粗?；Ч?提高了網(wǎng)絡(luò)同步能力的保持狀況,同時(shí)為實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)的同步研究提供了一種更簡(jiǎn)單、高效和可操作的有效方法.

[1]Pecora L M,Carroll T L 1998 Phys.Rev.Lett.80 2109

[2]Jost J,Joy M P 2001 Phys.Rev.E 65 016201

[3]W ang X F,Chen G R 2002 IEEE Trans.Circuits-I 49 54

[4]Barahona M,Pecora L M 2002 Phys.Rev.Lett.89 054101

[5]W ang X F,Chen G R 2002 In t.J.Bifurcat.Chaos 12 187

[6]M otter A E,Zhou C S,Kurths J 2005 Phys.Rev.E 71 016116

[7]N ishikawa T,M otter A E 2006 Physica D 224 77

[8]Zhou J,Lu JA,Lu JH 2006 IEEE Trans.Au to.Con trol 51 652

[9]A renas A,Díaz-Guilera A,Kurths J,M oreno Y,Zhou C S 2008 Phys.Rep.469 93

[10]Zhu T X,W u Y,X iao J H 2012 Acta Phys.Sin.61 040502(in Chinese)[朱廷祥,吳曄,肖井華2012物理學(xué)報(bào)61 040502]

[11]Xu M M,Lu JA,Zhou J 2016 Acta Phys.Sin.65 028902 (in Chinese)[徐明明,陸君安,周進(jìn) 2016物理學(xué)報(bào) 65 028902]

[12]K urkcuoglu O,Jernigan R L,Doruker P 2004 Polym er 45 649

[13]M arrink S J,Vries A H D,M ark A E 2004 J.Phys. Chem.B 108 750

[14]Bornhold t S 2005 Science 310 449

[15]Chen J,Lu J A,Lu X F,W u X Q,Chen G R 2013 Comm un.Non linear Sci.18 3036

[16]Zeng A,LüL Y 2011 Phys.Rev.E 83 056123

[17]Saunders M G,Voth G A 2013 Annu.Rev.Biophys.42 73

[18]K im B J 2004 Phys.Rev.Lett.93 168701

[19]Chen H S,Hou Z H,Xin HW,Yan Y J 2010 Phys.Rev. E 82 011107

[20]G feller D,Rios P D L 2007 Phys.Rev.Lett.99 038701

[21]G feller D,Rios P D L 2008 Phys.Rev.Lett.100 174104

[22]Chen G R,W ang X F,Li X,LüJ H 2009 Som e Recen t Advances in Com plex Networks Synchronization(Heidelberg:Sp ringer)pp3–16

[23]Lu JA,Liu H,Chen J 2016 Synchronization in Com plex Dynam ical Networks(Beijing:Higher Education Press) pp120–125(in Chinese)[陸君安,劉慧,陳娟2016復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的同步(北京:高等教育出版社)第120—125頁(yè)]

[24]Kuram oto Y 1975 Lect.Notes Phys.39 420

[25]Aceb rón J A,Bonilla L L,Pérez V icente C J,Ritort F, Sp igler R 2005 Rev.M od.Phys.77 137

PACS:05.45.–a,05.45.X tDOI:10.7498/aps.66.060502

Im p roved algorithm of spectral coarse grain ing m ethod of com p lex netw ork?

Zhou Jian1)Jia Zhen1)?Li Ke-Zan2)

1)(College of Science,Guilin University of Technology,Guilin 541004,China)
2)(School ofM athem atics and Com puting Science,Guilin University of E lectronic Technology,Guilin 541004,China)
(Received 2 O ctober 2016;revised m anuscrip t received 21 Novem ber 2016)

Com p lex network as a key app roach to understandingmany com p lex system s,such as biological,chem ical,physical, technological and social system s,is ubiquitous in nature and society.Synchronization of large-scale com p lex networks is one of the m ost im portant issues in network science.In the last two decades,much attention has been paid to the synchronization of com p lex dynam ic networks,especially themeso-scale networks.However,many real networks consist of even hundreds ofm illions of nodes.Analyzing the synchronization of such large-scale coup led com p lex dynam ic networks often generate a large number of coup led diff erentialequations,which m ay m akem any synchronization algorithm s inapp licable formeso-scale networks due to the com p lexities of simu lation experiments.Coarse grainingmethod canmap the large-scale networks into m eso-scale networks while preserving som e of topological p roperties or dynam ic characteristics of the original network.Especially,the spectral coarse-graining scheme,as a typical coarse grainingmethod,is proposed to reduce the network size while preserving the synchronization capacity of the initial network.Nevertheless, p lenty of studies dem onstrate that the com ponents of eigenvectors for the eigenvalue of the coup ling m atrix,which can depict the ability to synchronizing networks,distribute uneven ly.Most of the com ponents distribute concentrically and the intervals are sm all,while som e other com ponents distribute dispersed ly and the intervals are large,which renders the app lications of original spectral coarse graining m ethod unsatisfactory.Inspired by the adap tive clustering,we p ropose an im proved spectral coarse graining algorithm,which clusters the same or the sim ilar nodes in the network according to the distance between the com ponents of eigenvectors for the eigenvalue of network coup ling m atrices,so that the nodesw ith the sam e or the sim ilar dynam ic properties can be eff ectively clustered together.Com pared w ith the original spectral coarse graining algorithm,thismethod can im p rove the accuracy of the result of clustering.M eanwhile,our m ethod can greatly reduce algorithm com p lexity,and obtain better spectral coarse graining resu lt.Finally,num erical simulation experim ents are im p lem ented in four typical com p lex networks:NW network,ER network,BA scale-free network and clustering network.The com parison of results demonstrate that ourmethod outperform s the original spectral coarse graining approach under various criteria,and im proves the eff ect of coarse graining and the ability to synchronize networks.

comp lex network,synchronization,spectral coarse graining,im proved algorithm

10.7498/aps.66.060502

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):61563013,61663006)資助的課題.

?通信作者.E-m ail:jjjzzz0@163.com

*Pro ject supported by the National Natural Science Foundation of China(G rant Nos.61563013,61663006).

?Corresponding author.E-m ail:jjjzzz0@163.com