楊青林 王立夫 李歡 余牧舟

(東北大學(xué)秦皇島分校 控制工程學(xué)院，秦皇島 066004)

1 引 言

從20世紀末開始,復(fù)雜網(wǎng)絡(luò)理論逐步成為社會、經(jīng)濟、化學(xué)和信息系統(tǒng)等領(lǐng)域的重要研究方法,對復(fù)雜網(wǎng)絡(luò)靜態(tài)特性和動態(tài)特性的定量定性描述,已經(jīng)成為網(wǎng)絡(luò)時代一個極其重要的挑戰(zhàn)性課題,被稱為“網(wǎng)絡(luò)的新科學(xué)(new science of network)”[1].復(fù)雜網(wǎng)絡(luò)的同步作為一種重要的網(wǎng)絡(luò)動態(tài)行為,在激光系統(tǒng)、超導(dǎo)材料和通信等領(lǐng)域有重要的意義.同步現(xiàn)象在自然界中也廣泛存在,例如螢火蟲有規(guī)律地閃光、心臟細胞同步震蕩、掛在同一橫梁上的鐘擺同步擺動等.近20多年來,研究人員對復(fù)雜網(wǎng)絡(luò)的同步研究取得了豐碩的成果[2-15].其中,對于一般連續(xù)時間耦合網(wǎng)絡(luò)最常用的方法是將網(wǎng)絡(luò)的狀態(tài)方程線性化后轉(zhuǎn)化成主穩(wěn)定函數(shù)來研究[2,3].然而對于實際網(wǎng)絡(luò)動輒成千上萬的節(jié)點來說,判斷他們是否同步需要求解大量耦合微分方程,并且小規(guī)模網(wǎng)絡(luò)得到的同步判據(jù)或定理不能直接推廣到大規(guī)模網(wǎng)絡(luò)[16].因此,如何將復(fù)雜網(wǎng)絡(luò)進行約簡并保留其同步能力不變,對大規(guī)模網(wǎng)絡(luò)的同步分析和仿真至關(guān)重要.Gfeller和Rios[17,18]提出的譜粗粒化(spectral coarse graining,SCG)算法通過分析網(wǎng)絡(luò)的結(jié)構(gòu)矩陣,把特征向量分量相同或相近的節(jié)點合并,從而保證了約簡后網(wǎng)絡(luò)的同步能力不變.周建等[19]提出的改進譜粗?；?improved spectral coarse graining,ISCG)算法采用了不同的分類方式,改善了在特征向量分量分布極不均勻時的粗?；Ч?并且降低了算法的復(fù)雜度.Chen等[20]進一步研究了網(wǎng)絡(luò)的聚類結(jié)構(gòu)對譜粗粒化效果的影響.Wang和Xu[21]發(fā)現(xiàn)采用SCG算法對網(wǎng)絡(luò)約簡后,其可控性也能很好地保留下來.

SCG算法和ISCG算法都給出了一種簡單可實現(xiàn)的譜粗?；椒?但是在確定網(wǎng)絡(luò)中哪些節(jié)點需要合并時都是以特征向量分量間的絕對距離為判斷依據(jù),沒有考慮到特征向量分量間的相對距離,即絕對距離占分量絕對值的比例.本文經(jīng)過理論推導(dǎo)證明了兩個節(jié)點合并前后特征值的變化量與分量間的相對距離成正比例關(guān)系,SCG和ISCG算法在分類時都忽略了分量間相對距離的影響,從而導(dǎo)致節(jié)點的分類不準(zhǔn)確.為了克服這一缺陷,本文提出了一種基于相對距離的譜粗粒化(improved spectral coarse graining based on relative distance,ISCGR)算法,在對節(jié)點分類時以特征向量分量間的相對距離作為判斷標(biāo)準(zhǔn),改善了網(wǎng)絡(luò)的粗?；Ч?提高了網(wǎng)絡(luò)約簡后保持同步的能力.采用本文所提的算法對27種實際網(wǎng)絡(luò)進行粗?；抡?發(fā)現(xiàn)互聯(lián)網(wǎng)、生物、社交、合作等具有明顯聚類結(jié)構(gòu)的網(wǎng)絡(luò)在約簡后比電力、化學(xué)等網(wǎng)絡(luò)更容易保持同步.

2 同步能力的刻畫

主穩(wěn)定方程法是研究一般連續(xù)時間耦合網(wǎng)絡(luò)同步的常用方法[2,3].考慮由N個節(jié)點構(gòu)成的復(fù)雜網(wǎng)絡(luò),其中第i個節(jié)點的動力學(xué)方程為

式中,xi∈Rm為節(jié)點i的m維狀態(tài)變量；f(xi)為第i個節(jié)點自身的狀態(tài)方程；常數(shù)μ＞0 是網(wǎng)絡(luò)的耦合強度；H(·):Rm→Rm表示各個節(jié)點之間的內(nèi)部耦合函數(shù)；Laplacian矩陣L=(lij)∈RN×N是外部耦合矩陣,表示網(wǎng)絡(luò)的拓撲結(jié)構(gòu),滿足耗散條件特別的,當(dāng)Laplacian矩陣L表示一個無向無權(quán)的網(wǎng)絡(luò)時,有如下定義：

對角元為

其中ki為節(jié)點i的度數(shù).此時,外部耦合矩陣L是一個不可約的對稱陣,具有非負特征根并且特征根滿足 0=λ1≤λ2≤···≤λN.如果在t→∞ 時有x1(t)=x2(t)=···=xN(t)=s(t),那么就稱動態(tài)網(wǎng)絡(luò)(1)式能夠達到完全同步,其中同步流形s(t)滿足(t)=f(s(t)).對(1)式在同步狀態(tài)s(t)處線性化,令ξi(t)=xi(t)-s(t),可以得到如下線性動力學(xué)方程：

其中Df(s)和DH(s)分別是f(s)和H(s)在同步s(t)處的Jacobi(雅可比)矩陣,令ξ=[ξ1,ξ2···ξN],則(4)式可以寫為

記LT=JΛJˉ1為Laplace矩陣L的Jordan分解,Λ=diag[λ1,λ2,···,λN]為L的特征值矩陣.再令ψ=[ψ1,ψ2,···ψN]=ξJ,將(5)式對角化可得

(6)式是一個關(guān)于λk的N維微分方程組,展開后可以寫成

將(7)式一般化后即可得到主穩(wěn)定方程：

這里,α=μλk.(8)式的最大Lyapunov指數(shù)Lmax是變量α的函數(shù),稱為動力學(xué)網(wǎng)絡(luò)(1)式的主穩(wěn)定函數(shù).給定一耦合強度μ,在坐標(biāo)軸上可以相應(yīng)地找到一點μλk,若該點對應(yīng)的Lmax為負數(shù)時,則該特征模態(tài)為穩(wěn)定態(tài)；反之,則該特征模態(tài)為不穩(wěn)定態(tài).如果與特征值λk(k=2,3,···,N)對應(yīng)的最大Lyapunov指數(shù)Lmax均為負數(shù),那么在該耦合強度μ下,整個網(wǎng)絡(luò)的同步流形是漸近穩(wěn)定的.我們把使得Lmax＜0 的α取值范圍S稱為動態(tài)網(wǎng)絡(luò)(1)式的同步化區(qū)域,它由孤立節(jié)點的動力學(xué)函數(shù)f(xi)和內(nèi)部耦合函數(shù)H(·)決定.如果耦合強度μ與Laplacian矩陣的每個非零特征值之積都在同步區(qū)域S內(nèi),即μλk∈S(k=2,3,···,N),那么動態(tài)網(wǎng)絡(luò)(1)式的同步流形是漸近穩(wěn)定的,網(wǎng)絡(luò)就能達到同步[2,3].同步區(qū)域S可以分為以下4種類型：Ⅰ.S=(α1,+∞)；Ⅱ.S=(α1,α2)；Ⅲ.S=(α1,α2)∪(α2,α3)∪···；Ⅳ.S=? .其中,類型Ⅰ網(wǎng)絡(luò)的同步化能力可以用Laplacian矩陣L的最小非零特征值λ2來刻畫,λ2越大,μλ2越容易大于α1,網(wǎng)絡(luò)的同步化能力越強；類型Ⅱ網(wǎng)絡(luò)的同步能力可以用Laplacian矩陣L的最大特征值λN與λ2的比值λN/λ2來刻畫,λN/λ2越小,網(wǎng)絡(luò)的同步能力越強；類型Ⅲ網(wǎng)絡(luò)需要所有特征值都滿足一定的條件,很難達到同步；類型Ⅳ網(wǎng)絡(luò)無論耦合強度μ和Laplacian矩陣L的特征值為何值,網(wǎng)絡(luò)都不能達到同步.大多數(shù)網(wǎng)絡(luò)都屬于Ⅰ或Ⅱ兩種類型,因此在分析網(wǎng)絡(luò)的同步能力時,通常考慮λ2和λN/λ2兩個指標(biāo)[22].

3 網(wǎng)絡(luò)同步的SCG算法和ISCG算法

3.1 SCG方法與ISCG方法的原理

由主穩(wěn)定方程法可知,當(dāng)動態(tài)網(wǎng)絡(luò)節(jié)點間的耦合強度、孤立節(jié)點的動力學(xué)方程和內(nèi)部耦合函數(shù)固定后,網(wǎng)絡(luò)的同步能力由Laplacian矩陣的λ2或λN/λ2決定.所以要想保持網(wǎng)絡(luò)的同步能力不變,需要盡量保持網(wǎng)絡(luò)在粗?；昂蟮摩?或λN/λ2不變.Dffller和Rios[17,18]提出的SCG算法較好地保留了約簡前后網(wǎng)絡(luò)的λ2和λN/λ2值,從而保持了約簡前后網(wǎng)絡(luò)的同步能力不變.這種算法主要解決了合并過程中的兩個主要問題,一是如何合并節(jié)點及更新邊,即如何更新約簡后網(wǎng)絡(luò)的Laplacian矩陣；二是確定哪些節(jié)點可以被合并.

首先,對于如何更新合并后的邊,我們先看一個小型的網(wǎng)絡(luò).圖1(a)是一個無向無權(quán)的網(wǎng)絡(luò),如果把節(jié)點c、d、e合并為圖1(b)中的節(jié)點g,則稱節(jié)點c、d、e組成了團Cg,記ωx→y是節(jié)點x到節(jié)點y的權(quán)值,我們有：

這里,|Cg| 表示團Cg中包含的節(jié)點個數(shù).同理,我們也可以求出其他的邊權(quán).在大型網(wǎng)絡(luò)中,記初始節(jié)點的標(biāo)號i=1,2,···,N.約簡后的節(jié)點標(biāo)號為C=1,2,···,,為約簡之后網(wǎng)絡(luò)的節(jié)點數(shù),C也可以表示原始網(wǎng)絡(luò)中要約簡的節(jié)點所在的團,同屬于一個團的節(jié)點被合并成一個節(jié)點.約簡之后網(wǎng)絡(luò)的Laplacian矩陣可以用以下公式求解

圖1 合并節(jié)點的過程Fig.1.The processing of merging nodes.

這里,K∈R×N和R∈RN×分別為

其中,Ci表示原始網(wǎng)絡(luò)節(jié)點i所在團的標(biāo)號；|C| 表示團C中節(jié)點的個數(shù),δ是常用的Kronecker函數(shù).

接下來考慮合并哪些邊,分別對λ2和λN/λ2兩種情況進行討論.若要保持網(wǎng)絡(luò)(1)式的Laplacian矩陣L的最小非零特征值λ2不變,SCG方法的原理是將λ2所對應(yīng)特征向量P2中分量相同或相近的節(jié)點合并在一起,這樣得到合并后網(wǎng)絡(luò)的Laplacian矩陣的最小非零特征值2與原來網(wǎng)絡(luò)的λ2相同或相近.通常,我們定義特征向量P2所對應(yīng)的兩個分量p2i和p2j相近是指‖p2i-p2j‖/‖p2max-p2min‖?1,其中p2max和p2min分別是特征向量分量中的最大值和最小值.具體的操作步驟為,先把區(qū)間 [p2min,p2max] 平均分成i個區(qū)間,再把分在同一個區(qū)間內(nèi)的特征向量分量對應(yīng)的節(jié)點合并為一個節(jié)點,最后利用(11)式求解約簡后網(wǎng)絡(luò)的Laplacian矩陣.類似地,當(dāng)要保持網(wǎng)絡(luò)(1)的Laplacian矩陣L的最大特征值與第二小特征值之比λN/λ2時,需要同時保持λ2和λN不變.具體的步驟為：先把λ2所對應(yīng)的特征向量分量分為i個等分區(qū)間,再把λN所對應(yīng)的特征向量分量分為i個等分區(qū)間,找出P2和PN中同時落入等分區(qū)間的分量,將這些分量對應(yīng)的節(jié)點合并,最后利用(11)式更新合并后的Laplacian矩陣,便可以得到約簡后的網(wǎng)絡(luò).

圖1表明,采用譜粗?；枷氚淹獠窟B接相同的節(jié)點合并,網(wǎng)絡(luò)的第二小特征值λ2不變,即約簡后網(wǎng)絡(luò)的同步能力不發(fā)生改變.

ISCG方法是譜粗粒化方法的改進算法[19],也是通過合并特征向量P2中相同或相近的分量達到約簡網(wǎng)絡(luò)的目的.但與SCG算法不同的是,ISCG算法不是把特征向量分量等間距平分,而是采用分裂聚類的方法對節(jié)點進行分類.具體操作為,當(dāng)要保持λ2不變時,先把λ2所對應(yīng)的特征向量分量從小到大排列,算出兩兩相鄰分量間的距離,找出最大的前-1 個間距,在這-1 個間距設(shè)置分割點,將特征向量分量分裂為個聚類,把屬于同一聚類的節(jié)點合并為一個節(jié)點,最后更新Laplacian矩陣,就得到了節(jié)點數(shù)為的粗?；W(wǎng)絡(luò).同理,當(dāng)要保持λN/λ2不變時,先根據(jù)特征向量分量的間距分別將P2的分量和PN的分量分裂為個聚類,找出同時被分裂到同一聚類里的分量,把分量對應(yīng)的節(jié)點合并,最后按照(11)式來更新合并后網(wǎng)絡(luò)的Laplacian矩陣.ISCG算法的優(yōu)點在于可以將原始網(wǎng)絡(luò)約簡為任意指定規(guī)模的粗?；W(wǎng)絡(luò),復(fù)雜度為O(N2),要低于SCG算法的復(fù)雜度O(N3),并且在特征向量分量分布不均勻時,使用ISCG算法的粗?；Ч黠@優(yōu)于SCG算法[19].

3.2 SCG算法和ISCG算法的局限

SCG算法和ISCG算法在保持網(wǎng)絡(luò)的同步能力時都有著得天獨厚的優(yōu)勢.現(xiàn)實世界中大部分特征向量分量分布非常集中,少數(shù)特征向量分量分布特別分散,對于這種特征向量分量分布不均勻的網(wǎng)絡(luò)采用SCG算法一方面會出現(xiàn)距離很近的特征向量分量被分到兩個聚類里面,另一方面由于少數(shù)特征向量分布較為分散,導(dǎo)致得到的聚類數(shù)隨i變化不大,不容易得到任意規(guī)模的粗粒化網(wǎng)絡(luò)[19].而ISCG方法采用分裂聚類的方式對節(jié)點分類,因此,在特征向量P2的分量極不均勻時,采用ISCG算法約簡網(wǎng)絡(luò)更能保持其同步能力.

圖2 15個節(jié)點并為14個節(jié)點的兩種方案Fig.2.Two schemes of merging 15 nodes into 14 nodes.

這兩種算法分類的方式不同,但都是以特征向量分量的絕對距離作為依據(jù)對節(jié)點分類.如果λ2對應(yīng)的特征向量P2的第i個分量和第j個分量相等,即p2i=p2j,按照SCG算法或ISCG算法把這兩個節(jié)點合并,λ2的值在網(wǎng)絡(luò)約簡前后不發(fā)生改變.而當(dāng)P2的兩個分量有較小的距離時,兩種算法的分類方式都遵循兩個分量間距離越小,被分在一起的幾率越大,而沒有考慮分量間相對距離的因素.如果設(shè)分量p2i與p2j之間的間距為ε,則p2i與p2j間的相對距離就是指ε占 min{|p2i|,|p2j|} 的比例ρ=ε/min{|p2i|,|p2j|}.下面我們通過一個例子說明在分類時只考慮絕對距離是不合理的.

假設(shè)原始網(wǎng)絡(luò)如圖2所示,網(wǎng)絡(luò)的Laplacian矩陣為

其最小非零特征值λ2=0.4130,對應(yīng)的特征向量P2=[-4.19,2.87,-1.92,3.61,-2.80,2.87,-1.14,0.11,1.51,1.00,2.80,-3.85,1.71,0.70,-3.27]T,P2的第9個與第10個分量分別是1.51和1.00,相差0.51；第12個與第15個分量分別是 -3.85 和 -3.27 相差0.58.如果以絕對距離作為合并節(jié)點的依據(jù),則合并節(jié)點9和10后λ2的變化量會更小.實際上,由(11)式得到合并節(jié)點9和10后的Laplacian矩陣1為

根據(jù)以上的討論,我們提出約簡后網(wǎng)絡(luò)λ2的變化量與所合并節(jié)點對應(yīng)的特征向量分量間相對距離的關(guān)系.

定理1：在進行譜粗?；^程合并兩個節(jié)點時,如果同一個特征值對應(yīng)的兩個特征向量分量p2i和p2j的間距ε遠遠小于 min{|p2i|,|p2j|},則合并節(jié)點i和節(jié)點j后網(wǎng)絡(luò)特征值的變化量δ與p2i和p2j間的相對距離ε/min{|p2i|,|p2j|} 成正比.

證明：假設(shè)λ2對應(yīng)的兩個正的特征向量分量分別為為p2i與p2j(p2i＜p2j),第j個分量與第i個分量之間的距離為ε,即p2j=p2i+ε,且ε?p2i.合并節(jié)點i和節(jié)點j后λ2的改變量設(shè)為δ,寫出原始網(wǎng)絡(luò)Laplacian矩陣的特征方程

把(13)式的第i個等式和第j個等式兩邊相加得到

因為分量之間的距離ε?p2i,所以可以忽略ε的大小,把合并后得到新節(jié)點所對應(yīng)的特征向量分量近似為p2i.按照(11)式求出合并后網(wǎng)絡(luò)的Laplacian矩陣并寫出特征方程

(15)式的第i個等式為

由(14)式和(16)式聯(lián)立可以得到

(17)式表明,約簡網(wǎng)絡(luò)后λ2的改變量δ不僅與特征向量分量間的絕對距離ε有關(guān),還與特征向量分量p2i的大小有關(guān).在ε相對于p2i足夠小時,δ與絕對距離占 min{p2i,p2j} 的比率ρ=ε/min{p2i,p2j}成正比例關(guān)系.同理,可以得到當(dāng)p2i為負值時δ與ε/min{|p2i|,|p2j|}成正比.因此,合并節(jié)點i和j后網(wǎng)絡(luò)特征值的變化量δ與p2i和p2j間的相對距離ε/min{|p2i|,|p2j|}成正比.證畢.

從定理1可知,被合并節(jié)點對應(yīng)的特性向量分量間的相對距離會直接影響合并后特征值的變化量,從而影響到粗?；男Ч?因此,在對特征向量分量進行分類時,應(yīng)該以特征向量間的相對距離為依據(jù).

4 ISCGR算法

與SCG和ISCG算法不同,ISCGR算法以相對距離作為分類依據(jù),從而更合理地對節(jié)點分類,改善了網(wǎng)絡(luò)的粗粒化效果,使所得粗?；W(wǎng)絡(luò)保持同步的能力增強.

在實際操作中,不能直接以ε/min{|p2i|,|p2j|}的大小作為設(shè)置分割點的判斷標(biāo)準(zhǔn),因為接近0的分量不滿足分量間的距離ε遠遠小于min{|p2i|,|p2j|}這一條件,從而ε/min{|p2i|,|pε2j|} 會得出很大的距離比率.這里用來代替ε/min{|p2i|,|p2j|}作為設(shè)置分割點的標(biāo)準(zhǔn),其中是λ2對應(yīng)的所有特征向量分量絕對值的平均值.以代替ε/min{|p2i|,|p2j|}一方面避免了靠近0的分量算出過大的比率值,另一方面此指標(biāo)包含了相對距離的影響因素,比采用絕對距離ε作為分類標(biāo)準(zhǔn)有更好的粗粒化效果.與ISCG算法相比,ISCGR算法在對特征向量分量進行分類時,越靠近0的分量分得越細化,聚類區(qū)間的長度越小,越遠離0的分量分得越粗糙,聚類區(qū)間的長度越大.

ISCGR算法的具體的步驟為：1)把λ2對應(yīng)的特征向量分量從小到大進行排序為計算兩兩相鄰分量之間的距離εi(i=1,2,···,N-1)；2)用這個距離除以對應(yīng)分量絕對值與所有分量絕對值平均值的和,即計算出3)根據(jù)ηi的大小設(shè)置分割點,將分量分裂成若干個聚類；4)把同一聚類中的節(jié)點合并為一個節(jié)點,利用(11)式得到粗?；W(wǎng)絡(luò)的Laplacian矩陣.

我們舉例來說明ISCGR的操作步驟.假設(shè)λ2對應(yīng)的特征向量P2的分量為 {p21,p22···p2N},要將其分為3類.首先把特征向量分量從小到大排列為相鄰分量之間的間距為 {ε1,ε2···εNˉ1},再通過公式計算出{η1,η2···ηNˉ1},選出最大的兩個相對距離記為ηj,ηk(j＜k),ηj對應(yīng)著2j和2,j+1之間的相對距離,ηk是2k和2,k+1之間的相對距離.接著在這兩個間距處設(shè)置分割點,把分量分裂成3類,分別為[21,2j],[2,j+1,2k]和 [2,k+1,2N] .最后將落入同一區(qū)間內(nèi)的點合并為一個節(jié)點,利用(11)式更新合并后的Laplacian矩陣,就可以獲得節(jié)點數(shù)為3的粗?；W(wǎng)絡(luò).ISCGR算法對節(jié)點分類時考慮了特征向量分量間的相對距離,在兩組分量間距相同的情況下,由于靠近0的分量相對距離大,所以會優(yōu)先在靠近0的兩個向量間設(shè)置分割點,把相對距離小的分量所對應(yīng)的節(jié)點合并.由此可見,ISCGR算法在區(qū)分不同節(jié)點的相似程度時更加合理,保證了分在同一聚類的節(jié)點相似程度高于不同聚類的節(jié)點,因此粗?；Ч^ISCG算法更好.

與λ2類似,對于類型II網(wǎng)絡(luò),當(dāng)考慮λN/λ2作為同步能力衡量指標(biāo)時,先用ISCGR算法分別對λN和λ2對應(yīng)的特征向量分量進行分類,將同時分裂在同一聚類的節(jié)點合并為一個節(jié)點,最后更新Laplacian矩陣,得到約簡后的粗粒化網(wǎng)絡(luò).

5 仿真分析

本節(jié)將對一般連續(xù)時間的動態(tài)網(wǎng)絡(luò)模型和27種現(xiàn)實世界網(wǎng)絡(luò)進行數(shù)值仿真,分別應(yīng)用ISCG方法和ISCGR方法對網(wǎng)絡(luò)進行約簡,比較兩種算法對網(wǎng)絡(luò)約簡后同步能力的保持效果.

5.1 模型網(wǎng)絡(luò)仿真

首先對連續(xù)時間動態(tài)網(wǎng)絡(luò)模型進行數(shù)值仿真,這里選取三種典型的網(wǎng)絡(luò)模型,即BA無標(biāo)度網(wǎng)絡(luò)[23]、ER隨機網(wǎng)絡(luò)[24]、和NW小世界網(wǎng)絡(luò)[25,26],分別應(yīng)用ISCG算法和ISCGR算法對其進行約簡,分析比較沒有考慮相對距離和基于相對距離的算法的粗粒化效果.

對于類型Ⅰ網(wǎng)絡(luò),保持同步能力不變只需要保持λ2不變即可.圖3展示了分別采用ISCG算法和ISCGR算法對1000個節(jié)點的BA、ER、NW網(wǎng)絡(luò)約簡后λ2的變化情況.圖3(a)是對1000個節(jié)點的BA網(wǎng)絡(luò)的粗粒化過程仿真,原始網(wǎng)絡(luò)的λ2為2.95.采用ISCG方法將網(wǎng)絡(luò)約簡至200,102,72個節(jié)點時,網(wǎng)絡(luò)的2分別變?yōu)?.96,3.13,3.26,比原網(wǎng)絡(luò)增加了0.34%,6.10%,10.51%；采用ISCGR方法將網(wǎng)絡(luò)約簡至200,102,72個節(jié)點時,網(wǎng)絡(luò)的2為別是2.95,2.95,2.98,變化了0,0,1.02%.由此可見,采用ISCGR算法保持BA網(wǎng)絡(luò)λ2的能力要優(yōu)于ISCG算法.對于圖3(b)1000個節(jié)點的ER隨機網(wǎng)絡(luò)和圖3(c)1000個節(jié)點的NW小世界網(wǎng)絡(luò)也能得出同樣的結(jié)論,即在網(wǎng)絡(luò)約簡至相同的節(jié)點時,采用ISCGR算法λ2值的變化量要小于ISCG算法,這表明采用ISCGR算法保持類型Ⅰ網(wǎng)絡(luò)同步能力的效果要優(yōu)于ISCG算法.

對于類型II網(wǎng)絡(luò),同步能力用λN/λ2衡量.圖4展示了分別采用ISCG算法和ISCGR算法對1000個節(jié)點的BA無標(biāo)度網(wǎng)絡(luò)、ER隨機網(wǎng)絡(luò)、NW小世界網(wǎng)絡(luò)約簡后保持λN/λ2情況的對比.從圖中可以看出,采用這兩種算法對網(wǎng)絡(luò)進行約簡后,λN/λ2都是隨著約簡后網(wǎng)絡(luò)節(jié)點數(shù)的減少而減小,但在相同的情況下,用ISCGR算法得到粗?；W(wǎng)絡(luò)的λN/λ2變化更小,這表明了ISCGR算法保持類型Ⅱ網(wǎng)絡(luò)的同步能力比ISCG算法更強.

圖3 采用ISCG與ISCGR算法獲得譜粗?；W(wǎng)絡(luò)對λ2的保持情況 (a)BA無標(biāo)度網(wǎng)絡(luò)；(b)ER隨機網(wǎng)絡(luò)；(c)NW小世界網(wǎng)絡(luò)Fig.3.The maintaining of λ2obtained by using ISCG and ISCGR algorithms in coarse graining metwork：(a)BA network；(b)ER network；(c)NW network.

由此可見,對于不同類型的網(wǎng)絡(luò)和不同的網(wǎng)絡(luò)模型,采用ISCGR算法約簡網(wǎng)絡(luò)后保持同步的能力都要優(yōu)于ISCG算法.

圖4 采用ISCG算法與ISCGR算法獲得譜粗?；W(wǎng)絡(luò)對 λN/λ2的保持情況 (a)BA無標(biāo)度網(wǎng)絡(luò)；(b)ER隨機網(wǎng)絡(luò)；(c)NW小世界網(wǎng)絡(luò)Fig.4.The maintaining of λN/λ2obtained by using ISCG and ISCGR algorithms in coarse graining metwork：(a)BA network；(b)ER network；(c)NW network.

5.2 實際網(wǎng)絡(luò)仿真

下面應(yīng)用一些真實網(wǎng)絡(luò)進行粗?；^程仿真,進一步比較ISCG算法和ISCGR算法保持實際網(wǎng)絡(luò)同步能力的效果.我們選取了協(xié)作、溝通、計算機、基礎(chǔ)設(shè)施、社會、生物、詞匯和電力等不同領(lǐng)域的網(wǎng)絡(luò)[27-29].這些網(wǎng)絡(luò)的規(guī)模從幾百個到幾千個節(jié)點不等,既包括稀疏網(wǎng)絡(luò)又包括致密網(wǎng)絡(luò).表1給出了這些網(wǎng)絡(luò)的基本數(shù)據(jù)及分別采用ISCG和ISCGR算法約簡到原始節(jié)點數(shù)N的30%,20%,10%,2%時,網(wǎng)絡(luò)Laplacian矩陣L的最小非零特征值λ2的變化量.圖5展示了分別采用ISCG和ISCGR算法對這些實際網(wǎng)絡(luò)約簡后λ2的變化情況,其中圖5(a)是從表1中挑選了一些隨著節(jié)點數(shù)減少,λ2變化比較大的網(wǎng)絡(luò),圖5(b)挑選了一些隨著節(jié)點數(shù)減少,λ2變化不太明顯的網(wǎng)絡(luò).圖5可以看出約簡后網(wǎng)絡(luò)節(jié)點數(shù)越小,λ2的變化量越大,但是在相同的情況下,采用ISCGR方法約簡網(wǎng)絡(luò)后得到的λ2誤差比采用ISCG方法要小.這表明對于實際網(wǎng)絡(luò),采用ISCGR方法比ISCG方法更能保持網(wǎng)絡(luò)的同步能力.

對比表1中平均度和約簡后λ2值變化量的關(guān)系發(fā)現(xiàn),在約簡程度相同時,網(wǎng)絡(luò)的平均度越大,約簡后網(wǎng)絡(luò)λ2的變化量越小,保持同步的能力越強.這是因為網(wǎng)絡(luò)的度越大,越接近于全局耦合網(wǎng)絡(luò),網(wǎng)絡(luò)中外部連接相同或相似的節(jié)點越多,所以合并這些節(jié)點后對網(wǎng)絡(luò)的特征值影響不大；而平均度越小,網(wǎng)絡(luò)越稀疏,網(wǎng)絡(luò)中外部連接相同或相似的節(jié)點越少,約簡后網(wǎng)絡(luò)的特征值變化量就越大.

圖5 分別采用ISCG與ISCGR算法對實際網(wǎng)絡(luò)進行粗?；蟊３?λ2情況的對比圖Fig.5.The maintaining of λ2obtained by using ISCG and ISCGR algorithms for real-world networks in coarse graining network.

表1 分別采用ISCG和ISCGR算法對實際網(wǎng)絡(luò)約簡后 λ2的保持情況統(tǒng)計表Table 1.The Statistics table of maintaining λ2 obtained by using ISCG and ISCGR algorithms for some real-world networks in coarse graining network.

另外,表1的數(shù)據(jù)表明,ISCGR算法對互聯(lián)網(wǎng)、生物、社交、合作等網(wǎng)絡(luò)的同步保持能力更強一些,對電力、化學(xué)等網(wǎng)絡(luò)的同步保持能力則弱一些.這是因為互聯(lián)網(wǎng)[30]具有模塊性,生物網(wǎng)絡(luò)(如新陳代謝網(wǎng)絡(luò))中的拓撲結(jié)構(gòu)是按等級組織起來的[31],社交網(wǎng)絡(luò)與合作網(wǎng)絡(luò)都具有“物以類聚,人以群分”的特點[32],即這類網(wǎng)絡(luò)都具有高聚類的特性,網(wǎng)絡(luò)中包含大量外部連接相同或相似的節(jié)點,所以ISCGR算法對這類網(wǎng)絡(luò)的約簡效果更好.相反,電力網(wǎng)絡(luò)、化學(xué)網(wǎng)絡(luò)中的節(jié)點大都是鏈狀式排列,這類網(wǎng)絡(luò)聚類特性不明顯,外部連接相同的節(jié)點很少,所以采用SCG算法對網(wǎng)絡(luò)約簡到一定程度時很難保持網(wǎng)絡(luò)的同步能力.

6 結(jié) 論

小規(guī)模網(wǎng)絡(luò)中的一些性質(zhì)不能直接應(yīng)用在大規(guī)模網(wǎng)絡(luò)中,所以復(fù)雜網(wǎng)絡(luò)的約簡成為了復(fù)雜網(wǎng)絡(luò)理論中的重要課題.通過對網(wǎng)絡(luò)約簡,不僅可以把小規(guī)模網(wǎng)絡(luò)中已經(jīng)研究過的性質(zhì)應(yīng)用到大規(guī)模網(wǎng)絡(luò)中,且簡化了分析和計算.SCG算法是一種保持類型I和類型II復(fù)雜網(wǎng)絡(luò)同步能力不變的約簡方法.本文在原始譜粗粒化方法基礎(chǔ)上提出了一種基于相對距離的譜粗?；椒?使應(yīng)用特征向量分量分類時比原算法更加合理,約簡后的網(wǎng)絡(luò)保持同步的能力得到增強,為大型網(wǎng)絡(luò)的譜粗?；峁┝艘环N更加精準(zhǔn)的約簡算法；并通過對3種經(jīng)典網(wǎng)絡(luò)模型和27種實際網(wǎng)絡(luò)的仿真分析表明,ISCGR算法比原算法粗?；Ч?進一步發(fā)現(xiàn)SCG算法對具有明顯聚類結(jié)構(gòu)的實際網(wǎng)絡(luò)(互聯(lián)網(wǎng)、生物、社交、合作等)比模糊聚類結(jié)構(gòu)的實際網(wǎng)絡(luò)(電力、化學(xué)等)更容易保持粗?；W(wǎng)絡(luò)的同步能力.

需要指出的是,SCG算法僅考慮了保持網(wǎng)絡(luò)的同步能力不變對網(wǎng)絡(luò)進行約簡,所得粗粒化網(wǎng)絡(luò)的其他動態(tài)特性或拓撲結(jié)構(gòu)卻不一定和原始網(wǎng)絡(luò)相同或相近.SCG算法除了能保持同步能力之外,是否還能保持約簡后網(wǎng)絡(luò)的其他動力學(xué)特性,例如可控性、一致性、穩(wěn)定性等? 是否還能保持約簡后網(wǎng)絡(luò)的小世界特性、度的冪律特性等網(wǎng)絡(luò)拓撲性質(zhì)? 譜粗?；蟮木W(wǎng)絡(luò)還有哪些性質(zhì)保留了下來,其他性質(zhì)發(fā)生了什么改變? 有沒有一種約簡方法可以兼并保持多種性質(zhì)不變? 這些問題都是值得我們進一步研究和思考的.網(wǎng)絡(luò)的約簡問題還有太多的未知,這些未知也吸引著我們不斷去探索.