基于相對距離的復雜網絡譜粗?；椒?

楊青林 王立夫 李歡 余牧舟

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

1 引 言

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

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

2 同步能力的刻畫

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

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

對角元為

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

其中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)式是一個關于λk的N維微分方程組,展開后可以寫成

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

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

3 網絡同步的SCG算法和ISCG算法

3.1 SCG方法與ISCG方法的原理

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

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

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

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

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

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

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

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

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

3.2 SCG算法和ISCG算法的局限

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

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

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

假設原始網絡如圖2所示,網絡的Laplacian矩陣為

其最小非零特征值λ2=0.4130,對應的特征向量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ù)以上的討論,我們提出約簡后網絡λ2的變化量與所合并節(jié)點對應的特征向量分量間相對距離的關系.

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

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

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

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

(15)式的第i個等式為

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

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

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

4 ISCGR算法

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

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

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

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

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

5 仿真分析

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

5.1 模型網絡仿真

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

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

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

圖3 采用ISCG與ISCGR算法獲得譜粗?；W絡對λ2的保持情況 (a)BA無標度網絡；(b)ER隨機網絡；(c)NW小世界網絡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.

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

圖4 采用ISCG算法與ISCGR算法獲得譜粗?；W絡對 λN/λ2的保持情況 (a)BA無標度網絡；(b)ER隨機網絡；(c)NW小世界網絡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 實際網絡仿真

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

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

圖5 分別采用ISCG與ISCGR算法對實際網絡進行粗粒化后保持 λ2情況的對比圖Fig.5.The maintaining of λ2obtained by using ISCG and ISCGR algorithms for real-world networks in coarse graining network.

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

6 結 論

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

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