上傳人：1***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：劉**（實名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時間：2023-09-30 格式：DOCX 頁數(shù)：9 大?。?5.69KB 積分：12 舉報 版權(quán)申訴

網(wǎng)絡(luò)特征譜的拓?fù)湫蕴卣?/p>

1網(wǎng)絡(luò)特征譜密度復(fù)雜網(wǎng)絡(luò)是對復(fù)雜系統(tǒng)結(jié)構(gòu)的數(shù)學(xué)抽象。通過研究復(fù)雜網(wǎng)絡(luò)，我們可以更好地了解自然界和社會中不同系統(tǒng)的結(jié)構(gòu)和動力學(xué)特征。20世紀(jì)60年代初,匈牙利數(shù)學(xué)家P.Erd?s和A.Rényi通過著名的隨機(jī)圖模型,運(yùn)用概率的方法來研究隨機(jī)圖的臨界現(xiàn)象和結(jié)構(gòu)涌現(xiàn),開創(chuàng)了圖論的新方向。在此后的很長一段時間內(nèi),隨機(jī)圖模型一直是復(fù)雜網(wǎng)絡(luò)研究的重點。但隨著因特網(wǎng)和計算機(jī)技術(shù)的不斷發(fā)展,可獲得的實際網(wǎng)絡(luò)數(shù)據(jù)逐漸增加,研究人員發(fā)現(xiàn),實際網(wǎng)絡(luò)的連接概率是相互關(guān)聯(lián)的,而不是像隨機(jī)圖模型那樣相互獨立的。因此,實際網(wǎng)絡(luò)和隨機(jī)圖模型在結(jié)構(gòu)上是有很大區(qū)別的,隨機(jī)圖模型并不能很好地反映實際網(wǎng)絡(luò)的特性。在對大量的數(shù)據(jù)進(jìn)行分析總結(jié)后,D.J.Watts等在1998年提出了“小世界”模型,反映了實際網(wǎng)絡(luò)中普遍存在的小世界特性。隨后,A.L.Barabási等在1999年提出了BA模型,反映了實際網(wǎng)絡(luò)中普遍存在的無標(biāo)度特性。由于小世界和無標(biāo)度特性在物理領(lǐng)域、生物領(lǐng)域和社會領(lǐng)域普遍存在,引起了數(shù)學(xué)、物理、生物和社會等許多學(xué)科研究人員的極大興趣,從而掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮。隨著像因特網(wǎng)和疾病傳播網(wǎng)等實際網(wǎng)絡(luò)對人們?nèi)粘Ｉ畹挠绊懺絹碓酱?促使我們來研究這些網(wǎng)絡(luò)的組織原則、拓?fù)浣Y(jié)構(gòu)與動力學(xué)特性。目前,復(fù)雜網(wǎng)絡(luò)性能指標(biāo)的研究還主要集中在其度分布、群集系數(shù)和平均最短路徑等的模擬與分析上,它們雖然重要但不能全面反映網(wǎng)絡(luò)的結(jié)構(gòu)。然而,網(wǎng)絡(luò)的鄰接矩陣全面刻畫了網(wǎng)絡(luò)中結(jié)點之間的相連關(guān)系,因此網(wǎng)絡(luò)鄰接矩陣的特征譜可以用來比較全面地分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和動力學(xué)特性,并有著很廣泛的應(yīng)用[6,7,8,9,10,11,12,13,14,15]。本文只討論簡單網(wǎng)絡(luò),即無自連線和重復(fù)邊的網(wǎng)絡(luò)。對一個簡單無向網(wǎng)絡(luò)G,它的鄰接矩陣A(G)定義為:如果網(wǎng)絡(luò)中兩結(jié)點i和j有邊相連,則aij=1,否則為0,且aii=0。它的Laplacian矩陣L(G)定義為D-A,其中D是對角線元素為相應(yīng)結(jié)點度數(shù)的對角矩陣,A是G的鄰接矩陣。從定義可以看出,Laplacian矩陣是鄰接矩陣的變形,二者都是對網(wǎng)絡(luò)結(jié)構(gòu)的刻畫。特征譜就是矩陣A或L特征值的集合。本文第2部分將分析3類重要網(wǎng)絡(luò)模型的鄰接矩陣的特征譜密度并介紹特征譜在網(wǎng)絡(luò)的中心性和二分性中的應(yīng)用;第3部分將討論特征譜構(gòu)造的時間序列中存在的標(biāo)度不變性和結(jié)構(gòu)涌現(xiàn);第4部分將闡述網(wǎng)絡(luò)Laplacian矩陣的特征譜和網(wǎng)絡(luò)同步之間的關(guān)系,以及在分析網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)中的應(yīng)用;最后指出了進(jìn)一步研究的方向。2基于k階矩的nmk設(shè)簡單無向網(wǎng)絡(luò)G有N個結(jié)點,由于它的鄰接矩陣A(G)是實對稱矩陣,因此根據(jù)矩陣?yán)碚?它有N個實特征值(重特征值按重數(shù)計算),記為λj,j=1,…,N。借助鄰接矩陣的特征值,可以定義譜密度ρ(λ)和k階矩Mk如下:ρ(λ)=1Νn∑j=1δ(λ-λj)?Μk=∫∞-∞λkρ(λ)dλ(1)進(jìn)一步,由矩陣特征值理論有Μk=1ΝΝ∑j=1(λj)k=1Νtr(Ak)=1Ν∑i1?i2???ikai1i2ai2i3?aiki1(2)因為鄰接矩陣的元素均為0和1,(2)式中最后一個等式說明:如果ai1i2ai2i3…aiki1=1,那么就存在一條長為k的閉合回路使得從結(jié)點i1出發(fā)經(jīng)過k-1個結(jié)點可以返回ii。于是,NMk就表示網(wǎng)絡(luò)中存在的長為k的閉合回路的總數(shù)。當(dāng)k=3時,由于一個三角形中有6條閉合回路,因此NM3/6就是圖中三角形的數(shù)目。而在樹狀網(wǎng)絡(luò)中,從一點出發(fā)只有經(jīng)過偶數(shù)步才能返回同一結(jié)點,故樹狀網(wǎng)絡(luò)譜密度的奇數(shù)階矩為0。2.1譜密度和個數(shù)階矩在隨機(jī)網(wǎng)中,最簡單也是最著名的模型就是以P.Erd?s和A.Rényi命名的ER模型,即:n條邊連接著N個帶標(biāo)號的結(jié)點,而這些邊是從總共N(N-1)/2條可能的邊中隨機(jī)選取的,這樣的N個結(jié)點n條邊的圖總共有CnΝ(Ν-1)/2種,構(gòu)成了一個概率空間,其中每一種圖都是等概率的。另一種等價的定義為:給定N個結(jié)點,每一對結(jié)點以概率p相互連接。這時總邊數(shù)是一個隨機(jī)變量,期望值為pN(N-1)/2。為了便于討論,我們假設(shè)連接概率p滿足pNα=c,其中c為常數(shù)。下面是譜密度和奇數(shù)階矩的模擬結(jié)果。當(dāng)α>1且N→∞時,結(jié)點的平均度數(shù)〈k〉=(N-1)p≈N·p=cN1-α→0,由表1可知,譜密度的奇數(shù)階矩幾乎為0,說明此時網(wǎng)絡(luò)具有樹狀結(jié)構(gòu)。當(dāng)α=1且N→∞時,結(jié)點的平均度數(shù)〈k〉≈pN=c,譜密度如圖1a和圖1b所示。結(jié)合表1可知,若c≤1時,網(wǎng)絡(luò)仍基本上為樹狀結(jié)構(gòu);而c>1時,譜密度的奇數(shù)階矩遠(yuǎn)遠(yuǎn)大于0,說明網(wǎng)絡(luò)的結(jié)構(gòu)發(fā)生了顯著的變化,出現(xiàn)了環(huán)和分支(component),分支也稱為集團(tuán)。當(dāng)0≤α<1且N→∞時,結(jié)點的平均度數(shù)〈k〉≈cN1-α→+∞,由圖1b,網(wǎng)絡(luò)的譜密度接近半圓形分布。2.2ws模型的建立過程研究發(fā)現(xiàn),現(xiàn)實網(wǎng)絡(luò)不僅和隨機(jī)圖模型一樣具有平均路徑小的特點,而且群集系數(shù)比較大,為了解決這個問題,D.J.Watts和S.H.Strogatz引入了小世界網(wǎng)的概念和WS模型。WS模型的生成規(guī)則如下:首先,從編號為1,2,…,N的N個孤立的結(jié)點開始,每個結(jié)點與位于同一側(cè)最相鄰的k/2(k為偶數(shù))個結(jié)點相連,從而形成一個具有N個結(jié)點kN/2條邊的環(huán)形網(wǎng)絡(luò),其中每個結(jié)點的度均為k。然后,再以概率pr為網(wǎng)絡(luò)中的每條邊重新連線,重新連線的另一結(jié)點從N個結(jié)點中隨機(jī)選取。重新連線同樣是按照同一個方向進(jìn)行的,先對與結(jié)點最相鄰的邊進(jìn)行重新連線,N個結(jié)點最相鄰的邊重連完之后,再對次相鄰的邊重新連線,依此類推,直至結(jié)點一側(cè)的所有邊都重連完畢,在重新連線的過程中要保證沒有自連線和重復(fù)邊產(chǎn)生。WS模型的譜密度如圖2所示。當(dāng)pr=0時,WS模型是一個規(guī)則的圓環(huán),由圖2a,譜密度的形狀非常不規(guī)則,由表2,此時它有很大的三階矩。當(dāng)pr=0.01時,由圖2a,譜密度的形狀變得比較光滑了,說明雖然只有少量的隨機(jī)重連邊,但網(wǎng)絡(luò)的結(jié)構(gòu)已經(jīng)發(fā)生了改變,不再是規(guī)則的圓環(huán)。當(dāng)pr=1時,WS模型已經(jīng)是一個完全的隨機(jī)網(wǎng)絡(luò),只是此時結(jié)點的最小度數(shù)不是任意的,而是k/2。從圖2b可知,隨著pr→1,譜密度ρ(λ)逐漸趨向于半圓形分布,但由表2可知,只對較小的pr,仍然有大的三階矩。2.3舊著力點網(wǎng)絡(luò)再密度網(wǎng)絡(luò)ba大量的實證研究表明,許多現(xiàn)實網(wǎng)絡(luò)的度數(shù)分布都是冪律的,具有無標(biāo)度特性。為了探索其形成機(jī)制,人們提出了許多無標(biāo)度網(wǎng)模型。最早的也是最簡單的無標(biāo)度網(wǎng)模型是A.L.Barabási和R.Albert提出的BA模型,由于BA模型不僅度分布具有無標(biāo)度性,而且還體現(xiàn)了現(xiàn)實網(wǎng)絡(luò)的增長和擇優(yōu)機(jī)制,因此得到了廣泛的引用。BA模型的生成規(guī)則為:開始有m0個孤立(或全連通)結(jié)點,然后在每個時間步向網(wǎng)絡(luò)添加一個新結(jié)點和m(≤m0)條邊,使得新結(jié)點與m個網(wǎng)絡(luò)中的舊結(jié)點相連,其中m條邊選取舊結(jié)點是按照單個舊結(jié)點的度數(shù)與所有舊結(jié)點度數(shù)之和的比擇優(yōu)進(jìn)行的。當(dāng)m=m0=1時,BA模型是一棵樹,因此它的譜密度一定是關(guān)于0對稱的。當(dāng)m>1時,如圖3所示,BA模型譜密度的主體部分基本上是關(guān)于0對稱的,呈三角形;而文獻(xiàn)認(rèn)為中部指數(shù)衰減,尾部是冪律分布的。從圖3還可以看出,譜密度在0點附近有最大值,說明存在大量的模較小的特征值,文獻(xiàn)和解釋了這一現(xiàn)象的原因。綜上所述,3個模型的譜密度各不相同,反映了每類網(wǎng)絡(luò)的結(jié)構(gòu)特征。將實際網(wǎng)絡(luò)的譜密度與這3個模型比較,如果相似或相同,便可以認(rèn)為此網(wǎng)絡(luò)具有與模型網(wǎng)絡(luò)類似的結(jié)構(gòu),以便于做更進(jìn)一步的研究。例如,文獻(xiàn)畫了1297個蛋白質(zhì)相互作用網(wǎng)的譜密度(如圖4所示)。從這張譜密度圖可以看出,它基本上與無標(biāo)度網(wǎng)的譜密度相同。主要區(qū)別是它有雙尖峰,這又有點類似于規(guī)則網(wǎng)的譜密度。因此可以初步推斷蛋白質(zhì)相互作用網(wǎng)是無標(biāo)度網(wǎng),但同時有大的群集系數(shù),3類網(wǎng)絡(luò)的基本模型還不能很好說明它的形成機(jī)理。由于基因復(fù)制機(jī)理在生物網(wǎng)絡(luò)形成中扮演著重要角色,值得人們進(jìn)一步探索。2.4網(wǎng)絡(luò)的子圖中心性網(wǎng)絡(luò)的中心性是刻畫網(wǎng)絡(luò)局部結(jié)構(gòu)的一個性質(zhì),它有許多不同的指標(biāo),例如,結(jié)點度中心性(degreecentrality,DC)、介中心性(betweennesscentrality,BC)、特征向量中心性(eigenvectorcentrality,EC)等。在復(fù)雜網(wǎng)絡(luò)的研究中發(fā)現(xiàn),網(wǎng)絡(luò)模體(motif)(或子圖)的數(shù)量在生物和技術(shù)等實際網(wǎng)絡(luò)中常常包含許多重要信息。利用(2)式中網(wǎng)絡(luò)的環(huán)狀子圖與特征譜的關(guān)系,Ernesto等定義了子圖中心性(subgraphcentrality,Cs)來度量網(wǎng)絡(luò)的中心性。由(2)式,令μk(i)=(Ak)ii表示結(jié)點i所在的長為k的閉合回路的個數(shù)。定義結(jié)點i的子圖中心性為Cs(i)=∞∑k=0μk(i)k!。文獻(xiàn)證明了:Cs(i)=Ν∑j=1(νij)2eλj,其中ν1,ν2,…,νN是λ1,λ2,…,λN所對應(yīng)的特征向量所構(gòu)成的向量空間的一組標(biāo)準(zhǔn)正交基,而νij表示νj的第i個元素。因此整個網(wǎng)絡(luò)的子圖中心性可以定義為?Cs?=1ΝΝ∑i=1Cs(i)=1ΝΝ∑i=1eλi(3)子圖中心性是根據(jù)結(jié)點參與子圖的數(shù)目來定義結(jié)點重要性的,由于較小的子圖在網(wǎng)絡(luò)中出現(xiàn)的次數(shù)較多,對較小的子圖賦予了較高的權(quán)重。文獻(xiàn)通過計算比較得:子圖中心性與其它中心性指標(biāo)相比,可以更好地刻畫網(wǎng)絡(luò)的中心性,從而更便于分析網(wǎng)絡(luò)的結(jié)構(gòu)。如果一個沒有自連線的網(wǎng)絡(luò)中不存在長度為奇數(shù)的閉合回路,則這樣的網(wǎng)絡(luò)稱為二分圖。網(wǎng)絡(luò)的二分性是對網(wǎng)絡(luò)與二分圖相似性的表示,它有很多應(yīng)用,例如可以根據(jù)網(wǎng)絡(luò)的二分性來研究疾病的傳播速度等。雖然許多網(wǎng)絡(luò)可以用二分圖近似地表示,但完全是二分圖的實際網(wǎng)絡(luò)并不存在。因此,一般都是通過討論網(wǎng)絡(luò)二分性來對網(wǎng)絡(luò)的特性進(jìn)行分析。特征譜為度量網(wǎng)絡(luò)的二分性提供了一個簡單的工具:子圖中心性〈Cs〉由兩部分組成,一部分是長度為偶數(shù)的閉合回路,另一部分是長度為奇數(shù)的閉合回路,它們可用雙曲函數(shù)來度量,即?Cs?=1ΝΝ∑j=1[cosh(λj)+sinh(λj)]=?Cs?even+?Cs?odd(4)如果網(wǎng)絡(luò)G=(V,E)是二分圖,因為沒有長度為奇數(shù)的閉合回路,所以?Cs?odd=1/ΝΝ∑j=1sinh(λj)=0,則?Cs?=?Cs?even=1ΝΝ∑j=1cosh(λj)于是,長度為偶數(shù)的閉合回路所占的比例可用來度量網(wǎng)絡(luò)的二分性,即β(G)=?Cs?even?Cs?=?Cs?even?Cs?odd+?Cs?even=Ν∑j=1cosh(λj)Ν∑j=1eλj(5)顯然,β(G)≤1。當(dāng)且僅當(dāng)〈Cs〉odd=0時,G是二分圖。因為〈Cs〉odd≥0并且有sinh(λj)≤cosh(λj),所以對任意的β(G)都有12<β(G)≤1。3時間序列的自相似結(jié)構(gòu)網(wǎng)絡(luò)的特征譜是對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的一種壓縮,如何從特征譜中提取信息來研究網(wǎng)絡(luò)的特性是特征譜研究的一個重要方向。下面介紹一種提取特征譜信息的方法:用特征譜構(gòu)造的時間序列來分析網(wǎng)絡(luò)特性。設(shè)有N+1個結(jié)點的簡單無向網(wǎng)絡(luò)G,它的鄰接矩陣A的特征譜記為λ0≥λ1≥λ2≥…≥λN。用相鄰特征值之差來構(gòu)造時間序列{Δλk=λk-λk-1;k=1,2,…,N+1}={λ1-λ0,λ2-λ1,…,λN-λN-1,λ0-λN}其中約定λN+1=λ0。文獻(xiàn)將DE(diffusionentropy)方法和MF-DFA(multifractaldetrendedfluctuation)方法相結(jié)合來分析鄰接矩陣特征譜中的自相似結(jié)構(gòu)和長程相依關(guān)系。MF-DFA方法可用來度量時間序列的長程相依關(guān)系。將特征譜的首尾相接,便可得到所有可能的長度為l的片斷,即{(λm,λm+1,…,λm+l-1);m=0,1,2,…,N}。對每一個長度為l的片斷用階數(shù)為r的多項式進(jìn)行擬合,這個多項式記為λmF。如果時間序列具有長程相依性,則它的方差關(guān)于l將滿足如下的關(guān)系:ν(l,r,q)=1Ν+1Ν∑m=0{1ll∑s=1[λm+s-1-λmF]2}q/2V(l,r,q)=ν(l,r,q)1/q∝lα(q,r)(6)如果α(2,r)=0.5,那么時間序列是不相關(guān)的,即白噪聲;如果α(2,r)<0.5,那么時間序列是負(fù)相關(guān)的,否則,時間序列是正相關(guān)的。DE方法可用來度量時間序列的自相似結(jié)構(gòu)。取向量組{λ1-λ0,λ2-λ1,…,λn-λn-1},{λ2-λ1,λ3-λ2,…,λn+1-λn},…{λ0-λN,λ1-λ0,…,λn-1-λn-2},如果把每個向量看成是一個粒子在n個時間步內(nèi)的運(yùn)行軌道,則每個向量的前n個分量之和就是該粒子到時間n為止的位移,因此上面的向量組可以被看成是一個由N+1個粒子組成的系統(tǒng)的擴(kuò)散過程。取單位長度ε=√Ν+1∑k=1(Δλk)2/(Ν+1),將粒子的位移范圍分成M0個區(qū)間,用Km(n)來表示在時間n時位移進(jìn)入第m個區(qū)間的粒子數(shù)目,則DE(擴(kuò)散熵)定義為S(n)=-Μ0∑m=1Κm(n)Ν+1ln(Κm(n)Ν+1)(7)假設(shè)這個擴(kuò)散過程的概率分布函數(shù)(PDF)滿足p(m,n)=Κm(n)Ν+1=1nδF(mnδ)?m=1?2???Μ0將p(m,n)代入S(n)中,求積分得S(n)=A+δlnn(8)其中A是一個只與PDF有關(guān)的常數(shù)。用DE方法可以得到任何形式PDF的指數(shù)δ的值,但只有在特殊的PDF形式下才能用MF-DFA方法得到指數(shù)δ的值。也就是說,一般情況δ≠α(2,r)。僅對于PDF是高斯(Gaussian)分布,即正態(tài)分布,才有δ=α(2,r)。對于Levy行走過程的PDF,δ=1/[3-2α(2,r)]。因此,結(jié)合使用DE方法和MF-DFA方法可以得到有關(guān)PDF的重要信息。對于ER模型,從圖5a可知,當(dāng)pER<1/N時,α(2,2)=0.5≈δ,因此時間序列是不相關(guān)的。結(jié)合圖5b和表3,當(dāng)pER>1/N時,α(2,2)≈2δ,與pr=1的WS模型一致,因此可以認(rèn)為它們的結(jié)構(gòu)相似。當(dāng)pER=1/N時,α(2,2)≈δ≠0.5,因此可以認(rèn)為所構(gòu)造的時間序列是FBM(FractionalBrownianMotion)噪聲。對于WS模型,從圖6可知,當(dāng)pr>0.32時,α(2,2)≈1,因此網(wǎng)絡(luò)的結(jié)構(gòu)是和pr=1時相似的。對于增長的隨機(jī)網(wǎng)絡(luò)(GRN)模型,即每一步都有一個新結(jié)點加入,并且與網(wǎng)絡(luò)中的一個舊結(jié)點用有向邊相連,下面來討論新結(jié)點與有k條邊的舊結(jié)點相連的概率pk滿足pk∝kθ(0≤θ≤1)的情況。表4說明GRN模型長程相依的指數(shù)范圍在0.74～0.83之間,將DE和MF-DFA方法相結(jié)合可以在大多數(shù)情況下判斷PDF的形式,根據(jù)表4中所得結(jié)果可知大多數(shù)GRN網(wǎng)絡(luò)的特征譜所構(gòu)造的時間序列的PDF服從Gaussian分布。針對中構(gòu)造的特征譜序列,文獻(xiàn)又提出了一個新概念DFM(diffusionfactorialmoment)來分析時間序列,得到了復(fù)雜網(wǎng)絡(luò)特征譜序列的標(biāo)度不變性。根據(jù)p(m,n),首先定義數(shù)量Cq(n)=Μ0∑m=1[p(m,n)]q,稱為PM(probabilitymoment)。將p(m,n)代入,求積分可得lnCq(n)=A+δ(1-q)lnn(9)其中A是一個只與PDF有關(guān)的常數(shù)。當(dāng)δ=0.5時,F(m/nδ)是的m/nδGaussian函數(shù)。而δ≠0.5則可反映擴(kuò)散過程與這個標(biāo)準(zhǔn)擴(kuò)散過程的偏離。但由于假設(shè)p(m,n)≈Κm(n)/∑mΚm(n)會引起波動,可能會極大影響結(jié)果的準(zhǔn)確性,因此,文獻(xiàn)在FM(factorialmoment)的基礎(chǔ)上提出了DFM的概念,定義為DFΜq(n)=Μ0∑m=1Κm(Κm-1)?(Κm-q+1)(10)并且利用文獻(xiàn)中的方法證明了lnDFMq(n)=C+lnCq(n)=B+δ(1-q)lnn(11)對于ER模型,當(dāng)pER<1/N,標(biāo)度指數(shù)δ=0.5,當(dāng)pER≥1/N時,δ均明顯大于0.5,如圖7所示。對于WS模型,除個別點外,pr=1時的δ均明顯大于pr=0的δ值,如圖8a所示。當(dāng)pr∈[0.05,0.2]時,WS模型可以很好地反映實際網(wǎng)絡(luò)的標(biāo)度特性,此時δ∈0.71±0.05,如圖8b所示。因此,可以認(rèn)為pr∈[0.05,0.2]時,δ的值沒有發(fā)生變化。對于GRN模型,在θ=0.33和θ=0.49處δ存在最小值0.53和0.52,當(dāng)θ∈[0.54,1]時,除極少數(shù)點之外,δ>0.7,如圖9所示。文獻(xiàn)還指出,由于復(fù)雜網(wǎng)絡(luò)特征譜的標(biāo)度特性與度分布有所不同,所以可以根據(jù)特征譜的標(biāo)度來對復(fù)雜網(wǎng)絡(luò)進(jìn)行重新分類。4l的特征譜和特征提取設(shè)簡單無向網(wǎng)絡(luò)G有N個結(jié)點,因為它的L矩陣是行和為0的實對稱矩陣,若設(shè)Lij表示L矩陣第i行第j列的元素,則L的二次型可以表示為∑i,j=1ΝLijxiyj=∑i?jconnected(xi-xj)2≥0(12)所以L是半正定矩陣,存在N個非負(fù)的實特征值(重特征值按重數(shù)計算),并且0一定是L的特征值,相應(yīng)的特征向量為常特征向量(即特征向量各分量的值相同)。Laplacian矩陣的特征譜在網(wǎng)絡(luò)同步的穩(wěn)定性分析和研究中有著非常重要的應(yīng)用,文獻(xiàn)對此有詳細(xì)的介紹。如果在網(wǎng)絡(luò)的每個結(jié)點附上一個動力學(xué)系統(tǒng),而讓有邊相連的兩個結(jié)點的動力系統(tǒng)之間存在相互的耦合作用,就形成了一個動力學(xué)網(wǎng)絡(luò)。下面考慮最簡單的情況,即對稱線性耦合時L矩陣特征譜的重要應(yīng)用。設(shè)各結(jié)點有相同的動力系統(tǒng),m維狀態(tài)變量記為{xi,i=1,2,…,N},而耦合H是每個結(jié)點狀態(tài)變量的函數(shù)。假定不考慮耦合時,第i個結(jié)點所滿足的狀態(tài)方程為x˙i=F(xi),則在存在耦合作用的情況下,第i個結(jié)點所滿足的狀態(tài)方程是x˙i=F(xi)-σ∑jLijΗ(xi)(13)其中σ是耦合強(qiáng)度,Lij是矩陣L的元素。為了與文獻(xiàn)中記號保持一致,記L的特征譜為0=r0<r1≤…≤rN-1=rmax。Barahona和Pecora通過分析R?ssler振子的主穩(wěn)定性函數(shù)(對角化后的線性穩(wěn)定性方程)的最大Lyapunov指數(shù)λmax與一般耦合參數(shù)α=σri的關(guān)系,得出了當(dāng)α1<α<α2時,各種情況的λmax均小于0的重要結(jié)論,如圖10所示。因為λmax<0時,同步狀態(tài)趨于穩(wěn)定,所以線性穩(wěn)定同步狀態(tài)存在的條件可以表示為{σr1>α1σrmax<α2即rmaxr1<α2α1≡β(14)其中β的大小由F和H確定。汪小帆和陳關(guān)榮通過構(gòu)造Lyapunov函數(shù),證明了一個很有用的引理:設(shè)有N×N階對角陣D>0及兩個常數(shù)dˉ>0?τ>0,使得關(guān)系式[DF(s(t))+dH]TD+D[DF(s(t))+dH]≤-τIn對于d≤dˉ成立,其中In是N×N階單位陣,s(t)是網(wǎng)絡(luò)在t很大時達(dá)到的同步狀態(tài)。如果σr1≥-dˉ(15)那么同步狀態(tài)穩(wěn)定。表面上看,(14)和(15)兩個結(jié)論似乎是矛盾的,但實際上并不是。Pecora等人研究的是同步穩(wěn)定區(qū)域有界情況下同步的穩(wěn)定條件,而汪小帆等人研究的則是同步穩(wěn)定區(qū)域無界的情況下同步的穩(wěn)定條件,兩者相結(jié)合才能完整描述網(wǎng)絡(luò)同步的穩(wěn)定性。文獻(xiàn)和還利用上面的兩個結(jié)論分別研究了小世界網(wǎng)和無標(biāo)度網(wǎng)的精確同步性,研究的結(jié)果表明小世界網(wǎng)和無標(biāo)度網(wǎng)的同步穩(wěn)定性要好于最近鄰耦合的規(guī)則網(wǎng)絡(luò),對這一現(xiàn)象的普遍解釋是由于這兩種網(wǎng)絡(luò)的平均最短路徑小,使得振子間的信息交流更為有效。網(wǎng)絡(luò)同步研究的最終目標(biāo)是要理解網(wǎng)絡(luò)結(jié)構(gòu)如何影響它的同步能力。因為在最簡單的情況下,網(wǎng)絡(luò)的同步能力是由特征比R(即中的rmax/r1)來度量的,所以周濤等構(gòu)造了一個確定性的網(wǎng)絡(luò)模型CDCs(crosseddoublecycles)來討論網(wǎng)絡(luò)的結(jié)構(gòu)與R的關(guān)系。由圖11可知CDCs的平均最短路徑Lˉ和特征比R間滿足冪律關(guān)系R∝Lˉ1.5。這說明網(wǎng)絡(luò)的平均最短路徑是影響網(wǎng)絡(luò)同步能力的重要因素。由于L矩陣是網(wǎng)絡(luò)結(jié)構(gòu)的反映,因此L的特征譜和相應(yīng)的特征向量在分析網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)中也有重要的應(yīng)用。如果網(wǎng)絡(luò)是連通的,那