廣義確定性均勻遞歸樹網(wǎng)絡(luò)的拉普拉斯譜

趙虎

（青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧　810008）

廣義確定性均勻遞歸樹網(wǎng)絡(luò)的拉普拉斯譜

趙虎

（青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧810008）

在復(fù)雜網(wǎng)絡(luò)的模型構(gòu)建與性質(zhì)研究領(lǐng)域中，確定性均勻遞歸樹網(wǎng)絡(luò)模型DURT（Deterministic Uniform Recursive Tree）得到了廣泛應(yīng)用。在DURT網(wǎng)絡(luò)模型的基礎(chǔ)上提出一種適用范圍更廣的廣義確定性均勻遞歸樹演化模型GDURT（Generalized Deterministic Uniform Recursive Tree），通過(guò)設(shè)計(jì)一種能夠真實(shí)反映網(wǎng)絡(luò)增長(zhǎng)演變特點(diǎn)的最優(yōu)節(jié)點(diǎn)分層編號(hào)方法，結(jié)合代數(shù)化簡(jiǎn)，找出了能夠快速計(jì)算GDURT網(wǎng)絡(luò)的拉普拉斯特征值和特征向量遞推關(guān)系式，并對(duì)GDURT網(wǎng)絡(luò)的拉普拉斯譜性質(zhì)做了分析。

復(fù)雜網(wǎng)絡(luò)；演化模型；確定性均勻遞歸樹；廣義；節(jié)點(diǎn)分層；拉普拉斯譜

復(fù)雜系統(tǒng)在現(xiàn)實(shí)世界中普遍存在，受制于其龐大的系統(tǒng)規(guī)模和各項(xiàng)系統(tǒng)要素之間的復(fù)雜關(guān)系，人們對(duì)復(fù)雜系統(tǒng)的結(jié)構(gòu)、性質(zhì)以及二者之間的相互作用機(jī)理的了解十分有限［1］。而確定性模型的建模和性質(zhì)研究在復(fù)雜系統(tǒng)研究領(lǐng)域中充當(dāng)著十分重要的角色。

在復(fù)雜系統(tǒng)建模研究中，確定性模型的主要優(yōu)勢(shì)在于它們的拓?fù)鋵傩钥梢杂梅治龅姆椒ㄟM(jìn)行精確計(jì)算，其鄰接矩陣和拉普拉斯（Laplacian）矩陣的譜性質(zhì)可以對(duì)網(wǎng)絡(luò)的全局結(jié)構(gòu)進(jìn)行全面而準(zhǔn)確的度量，任何局部性質(zhì)的改變都能通過(guò)譜的變化體現(xiàn)出來(lái)。在確定性模型建模研究中，均勻遞歸樹（URT）模型在流行病傳播、中世紀(jì)家族宗譜樹、鏈鎖信、金字塔營(yíng)銷網(wǎng)等領(lǐng)域的研究中得到了成功的運(yùn)用［2-3］，并逐步延伸到經(jīng)濟(jì)學(xué)領(lǐng)域中［4］。2008年，章忠志等人在復(fù)雜網(wǎng)絡(luò)的視角下對(duì)確定性均勻遞歸樹模型（DURT）作了詳盡的分析，準(zhǔn)確計(jì)算得出了確定性均勻遞歸樹的度分布、平均路徑長(zhǎng)度、介數(shù)分布、度相關(guān)性，等拓?fù)鋵傩?，并且得出了其Laplacian矩陣的特征值和特征向量的遞推關(guān)系［5］。2012年，陸哲明等人在DURT模型的基礎(chǔ)上構(gòu)造出一個(gè)小世界網(wǎng)絡(luò)two-tree network［6］，并對(duì)其主要的幾個(gè)拓?fù)鋵傩宰髁松钊胙芯俊?/p>

在以上研究結(jié)果的基礎(chǔ)上，對(duì)文獻(xiàn)［5］中的確定性均勻遞歸樹網(wǎng)絡(luò)模型作了推廣，提出了一種推廣的確定性均勻遞歸樹網(wǎng)絡(luò)模型GDURT（Generalized Deterministic Uniform Recursive Tree），賦予該模型一種更加復(fù)雜的演化模式，以期使其具有與現(xiàn)實(shí)復(fù)雜系統(tǒng)更為接近的特征。通過(guò)對(duì)GDURT模型在不同時(shí)步下的拉普拉斯矩陣結(jié)構(gòu)變化規(guī)律分析的角度入手，運(yùn)用代數(shù)方法，尋找一種最優(yōu)的分層節(jié)點(diǎn)編號(hào)規(guī)則，大大簡(jiǎn)化矩陣的運(yùn)算，從而給出了其拉普拉斯特征值和特征向量的遞推關(guān)系，并對(duì)其譜性質(zhì)作了分析。其中所提出的最優(yōu)分層節(jié)點(diǎn)編號(hào)方法不但適用于傳統(tǒng)均勻遞歸樹網(wǎng)絡(luò)模型，對(duì)確定性類樹復(fù)雜超網(wǎng)絡(luò)的拉普拉斯譜分析也同樣適用。

1　GDURT演化模型及其拓?fù)湫再|(zhì)

推廣的確定性均勻遞歸樹（GDURT）是通過(guò)一個(gè)逐次迭代的過(guò)程建立的。用t表示網(wǎng)絡(luò)構(gòu)建的時(shí)步數(shù)，用ut表示經(jīng)過(guò)個(gè)t時(shí)步后建立的GDURT網(wǎng)絡(luò)，則網(wǎng)絡(luò)的構(gòu)建過(guò)程為：當(dāng)t=0時(shí)，U0由一個(gè)孤立點(diǎn)構(gòu)成；當(dāng)t≥1時(shí)，Ut通過(guò)在Ut-1網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)上粘接一條長(zhǎng)為l（l≥1）的路構(gòu)成；這一過(guò)程不斷重復(fù)進(jìn)行。GDURT網(wǎng)絡(luò)模型的構(gòu)建過(guò)程由圖1所示。

圖1　GDURT網(wǎng)絡(luò)模型構(gòu)建過(guò)程Fig.1　Construction process of GDURT network model

令Ut表示t（t≥0）時(shí)步得到的GDURT網(wǎng)絡(luò)，Nt表示t（t≥0）時(shí)步網(wǎng)絡(luò)Ut的節(jié)點(diǎn)總數(shù)，并且令ne（t）和nv（t）分別表示在t時(shí)步新加入的節(jié)點(diǎn)數(shù)和邊數(shù)。已知nv（0）=N0=1，根據(jù)模型迭代過(guò)程可知：

度分布是研究網(wǎng)絡(luò)拓?fù)涮匦缘囊豁?xiàng)重要參數(shù)。網(wǎng)絡(luò)節(jié)點(diǎn)i的度是指節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的個(gè)數(shù)。網(wǎng)絡(luò)的累積度分布Pcum（k）則是指在網(wǎng)絡(luò)中任意選取一個(gè)節(jié)點(diǎn)，其度均大于或等于k的概率［3］。網(wǎng)絡(luò)的平均路徑長(zhǎng)度dˉt是指網(wǎng)絡(luò)在t時(shí)步時(shí)所有節(jié)點(diǎn)對(duì)之間最短路徑長(zhǎng)度的平均值。在作者前期研究中得到了GDURT網(wǎng)絡(luò)的累積度分布和平均路徑長(zhǎng)度如式（3）、（4）所示。

這意味著GDURT網(wǎng)絡(luò)的累積度分布隨著節(jié)點(diǎn)度k呈指數(shù)規(guī)模遞減，是一個(gè)指數(shù)類型的網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)規(guī)模無(wú)限增大時(shí)，其平均路徑長(zhǎng)度是按照網(wǎng)絡(luò)規(guī)模Nt的對(duì)數(shù)關(guān)系遞增的。網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)急劇增多時(shí)其平均路徑長(zhǎng)度增速平緩，具有明顯的小世界網(wǎng)絡(luò)特點(diǎn)［7］。

GDURT網(wǎng)絡(luò)演化過(guò)程中的度相關(guān)性knn（k）近似為關(guān)于k的線性關(guān)系，說(shuō)明該網(wǎng)絡(luò)模型是協(xié)調(diào)的［8］，在每一個(gè)時(shí)步，新加入到網(wǎng)絡(luò)中的節(jié)點(diǎn)優(yōu)先與度較大或具有相同度的節(jié)點(diǎn)連接。

2　GDURT網(wǎng)絡(luò)的拉普拉斯特征值和特征向量

令表Vt示網(wǎng)絡(luò)Ut的節(jié)點(diǎn)集合，即：Vt=｛v1，v2，…v（1+l）t｝。網(wǎng)絡(luò)Ut的鄰接矩陣定義為一個(gè)（1+l）t×（1+l）t矩陣At=（aij），其中當(dāng)vi和vj相鄰時(shí)aij=1；否則aij=0。令dvi表示點(diǎn)vi的度，令Dt=diag（dv1，dv2，…dv（1+l）t）為網(wǎng)絡(luò)Ut的度對(duì)角矩陣。則網(wǎng)絡(luò)Ut的拉普拉斯矩陣定義為：Ut的特征多項(xiàng)式Pt（ut，λ）定義為：

由定義可知Lt是一個(gè)實(shí)對(duì)稱矩陣，所以（1+l）t其個(gè)特征值均為實(shí)數(shù)，假定它們按升序排列：

λ1≤λ2≤L λ（1+l）t。由于Ut是樹，所以λi=-λ（1+l）t-i+1。對(duì)于一般網(wǎng)絡(luò)，計(jì)算其拉普拉斯特征值及關(guān)于特征值的特征向量是NP-困難的［8］，但對(duì)于結(jié)構(gòu)較為特殊的網(wǎng)絡(luò)，只要給節(jié)點(diǎn)施以合理的編號(hào)，并適當(dāng)?shù)剡\(yùn)用代數(shù)化簡(jiǎn)，便可大大簡(jiǎn)化矩陣運(yùn)算，準(zhǔn)確求出其特征值和特征向量的分布情況。

2.1拉普拉斯特征值

為了便于矩陣和行列式化簡(jiǎn)及計(jì)算，通過(guò)對(duì)GDURT模型演化過(guò)程的分析，可設(shè)計(jì)一種針對(duì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的分層編號(hào)方法，使得編號(hào)順序按照網(wǎng)絡(luò)增長(zhǎng)過(guò)程中節(jié)點(diǎn)增加的先后次序排列，并使結(jié)構(gòu)特點(diǎn)相似的節(jié)點(diǎn)位于同一分層中。假設(shè)當(dāng)l=2時(shí)，分別對(duì)t=2和t=3時(shí)步的網(wǎng)絡(luò)實(shí)施節(jié)點(diǎn)分層編號(hào)的過(guò)程如圖2所示。

圖2　當(dāng)l=2時(shí)，對(duì)t=2，t=3時(shí)步網(wǎng)絡(luò)中的節(jié)點(diǎn)實(shí)施分層編號(hào)Fig.2　Hierarchical numbering to nodes of the network wherel=2 and t=2，t=3 respectively

為便于討論，可將演化過(guò)程中t-1時(shí)步得到的網(wǎng)絡(luò)中的節(jié)點(diǎn)稱作“舊節(jié)點(diǎn)”，將t時(shí)步得到的網(wǎng)絡(luò)中新加入的節(jié)點(diǎn)稱作“新節(jié)點(diǎn)”，采用分層編號(hào)方法可以使得t時(shí)步網(wǎng)絡(luò)中的Nt-1個(gè)舊節(jié)點(diǎn)只與個(gè)Nt-1新增節(jié)點(diǎn)相鄰，且這些相鄰的新增節(jié)點(diǎn)都位于同一層中；對(duì)于新增加的Nt-Nt-1=（1+l）t-（1+l）t-1個(gè)節(jié)點(diǎn)，其最外層節(jié)點(diǎn)的度均為1，中間各層的節(jié)點(diǎn)度均為2，由此可知，按照分層編號(hào)后得到的網(wǎng)絡(luò)Ut的鄰接矩陣具有如下結(jié)構(gòu)特點(diǎn)：

式（7）中，At-1為網(wǎng)絡(luò)Ut-1的鄰接矩陣，It-1為（1+l）t-1階單位矩陣。由于采用節(jié)點(diǎn)分層編號(hào)，網(wǎng)絡(luò)Ut的舊節(jié)點(diǎn)只與（1+l）t-1個(gè)新節(jié)點(diǎn)相鄰，新增最外層節(jié)點(diǎn)也只與（1+l）t-1個(gè)其他新節(jié)點(diǎn)相鄰，故式（7）中第一行、第一列、最后一行和最后一列中分別只有一個(gè)分塊矩陣It-1；此外，其余新增中間層節(jié)點(diǎn)的度均為2，使得式（7）中除第一行、第一列、最后一行和最后一列的其余各行、各列均含有兩個(gè)分塊矩陣It-1，其余位置上均為0。

對(duì)網(wǎng)絡(luò)Ut的度對(duì)角矩陣Dt，需同樣遵守上述節(jié)點(diǎn)編號(hào)規(guī)則，不難看出GDURT網(wǎng)絡(luò)在t時(shí)步的拉普拉斯矩陣Lt為：

進(jìn)而可得出GDURT網(wǎng)絡(luò)在t時(shí)步的拉普拉斯特征多項(xiàng)式Pt（Ut，λ）：

式（9）中S=det（λ-1）It-1-Dt-1+At-1，也即t-1時(shí)步的網(wǎng)絡(luò)Ut-1的特征多項(xiàng)式。

運(yùn)用拉普拉斯展開定理［9］對(duì)式（9）進(jìn)行化簡(jiǎn)。先由式（9）的第l+1列乘以-1/（λ-1），加到第l列上，再按照第l+1行展開，再以第l列乘以-（λ-2）-1/（λ-1），加到第l-1列上，并按照第l行展開……，依此進(jìn)行，直到行列式化為最簡(jiǎn)形式，可得：

式（10）等式的系數(shù)為l個(gè)（1+l）t-1階行列式的乘積，其中符號(hào)last表示系數(shù)中第l個(gè)系數(shù)行列式的值。若令α=（1+l）t-1，并作如下符號(hào)定義：

已知對(duì)于t-1時(shí)步的網(wǎng)絡(luò)有（1+l）t-1個(gè)特征值，而t時(shí)步有（1+l）t=（1+l）t-1g（1+l）個(gè)特征值；假設(shè)網(wǎng)絡(luò)在t-1時(shí)步的特征值用集合△t-1=，，L，｝表示，并假定這些特征值按照升序排列：則（10）式可寫為：

由式（11）可看出：對(duì)于t-1時(shí)步網(wǎng)絡(luò)Ut-1的任意一個(gè)特征值，方程λ-1-=的解恰好為t時(shí)步網(wǎng)絡(luò)中與特征值對(duì)應(yīng)的1+l個(gè)新特征值。由之前關(guān)于符號(hào)kl的定義以及式（11）可知，方程λ-1-=的實(shí)數(shù)解恰好為1+l個(gè)。為便于討論，不妨假設(shè)l-1，在這種情形下，式（11）變形為式（12）：

已知t-1時(shí)步網(wǎng)絡(luò)的拉普拉斯特征多項(xiàng)式具有如下形式：

其中qi代表多項(xiàng)式系數(shù)。將帶入式（13），可以看出形如的項(xiàng)只能出現(xiàn)在項(xiàng)中，且該項(xiàng)系數(shù)為1。即，1是多項(xiàng)式Pt（Ut，λ）的常數(shù)項(xiàng)，且拉普拉斯特征值中不包含1。

已知樹的拉普拉斯特征值均大于或等于0，很容易觀察出式（14）、（15）均為單調(diào)遞增函數(shù)，且式（14）總是小于1的，而式（15）總是大于或等于2的，因此，對(duì)于t-1時(shí)步的任意一個(gè)特征值，<永遠(yuǎn)成立。

當(dāng)t=1，2，3時(shí)的特征值如圖3所示。

圖3　當(dāng)l=1，t=1，2，3時(shí)網(wǎng)絡(luò)的拉普拉斯特征值分布Fig.3　Laplacian eigenvalue distribution of network where l=1 andt=1，2，t=3 respectively

當(dāng)l取較大的值時(shí)，其f（λ）的表達(dá)式將更加復(fù)雜，但仍為一個(gè)最高次為1+l次的多項(xiàng)式，通過(guò)其拉普拉斯特征值的遞推關(guān)系計(jì)算任意時(shí)步的特征值均可在關(guān)于1+l的多項(xiàng)式時(shí)間內(nèi)完成。

2.2拉普拉斯特征向量

與特征值的計(jì)算類似，推廣的確定性均勻遞歸樹網(wǎng)絡(luò)的拉普拉斯特征向量之間也存在著遞推關(guān)系。假設(shè)l=1、λti為t時(shí)步網(wǎng)絡(luò)Ut的任意一個(gè)特征值，并假設(shè)與特征值λti對(duì)應(yīng)的特征向量為vti，則有如下關(guān)系式成立：

其中v1和v2為向量vti的兩個(gè)2t-1階分量，均為階單位矩陣。將式（16）中的向量v1和v2看作未知數(shù)展開線性方程組，可得如下關(guān)系式：

由式（12），（14），（16）和（18）可知，若將特征值λti代入方程中，則有

已知網(wǎng)絡(luò)在時(shí)t=1，l=1GDURT網(wǎng)絡(luò)的特征向量為（1，1）T和（1，-1）T，根據(jù)式（19）便可遞推出任意時(shí)步網(wǎng)絡(luò)的拉普拉斯特征向量，其結(jié)果與文獻(xiàn)［5］中的特例結(jié)論完全一致。

當(dāng)l取不同值時(shí)，其拉普拉斯特征向量的遞推關(guān)系與此類似。由式（19）可知，任一時(shí)步下關(guān)于網(wǎng)絡(luò)的某一個(gè)拉普拉斯特征向量，其第一分量總是由上一時(shí)步網(wǎng)絡(luò)中的對(duì)應(yīng)特征向量組成，利用這一現(xiàn)象可進(jìn)一步減少特征向量的計(jì)算時(shí)間。

3　結(jié)　論

傳統(tǒng)的遞歸樹（URT）和均勻遞歸樹（DURT）網(wǎng)絡(luò)演化模型的提出，為復(fù)雜網(wǎng)絡(luò)確定性演化模型的構(gòu)建及其相關(guān)性質(zhì)研究研究奠定了堅(jiān)實(shí)的基礎(chǔ)，但是相對(duì)過(guò)于簡(jiǎn)單的演化過(guò)程得該模型的應(yīng)用受到了一定的局限［3］。文中所討論的推廣確定性均勻遞歸樹模型（GDURT）可應(yīng)用于與URT網(wǎng)絡(luò)類似的仿真模擬實(shí)驗(yàn)或?qū)嶋H模型的研究中，并具有更強(qiáng)的靈活度和適應(yīng)性。

通過(guò)設(shè)計(jì)一種能夠真實(shí)反映網(wǎng)絡(luò)增長(zhǎng)演變特點(diǎn)的最優(yōu)分層節(jié)點(diǎn)編號(hào)方法，可有效減少原本NP-難的拉普拉斯特征值計(jì)算過(guò)程的復(fù)雜度；通過(guò)找出不同時(shí)步網(wǎng)絡(luò)的拉普拉斯特征值的遞推關(guān)系公式，以網(wǎng)絡(luò)初始狀態(tài)為起點(diǎn)，可計(jì)算出所有不同增長(zhǎng)模式下，GDURT網(wǎng)絡(luò)的拉普拉斯特征值，其計(jì)算復(fù)雜度為關(guān)于網(wǎng)絡(luò)規(guī)模Nt的多項(xiàng)式時(shí)間；根據(jù)遞推關(guān)系可以發(fā)現(xiàn)GDURT網(wǎng)絡(luò)的拉普拉斯特征值分布存在如下規(guī)律性：對(duì)于t時(shí)步的網(wǎng)絡(luò)Ut，其特征值共有個(gè)（1+l）t，且特征值中不包含1，其中的（1+l）t-1個(gè)特征值與t-1時(shí)步的網(wǎng)絡(luò)Ut-1的特征值完全相同，無(wú)需迭代計(jì)算。由某一時(shí)步的任意一個(gè)特征值均可遞推計(jì)算出下一時(shí)步的1+l個(gè)特征值，且特征值的排序關(guān)系可以保持，所有的特征值都是互不相同的。

在此基礎(chǔ)上進(jìn)一步得出了GDURT網(wǎng)絡(luò)的拉普拉斯特征向量的遞推關(guān)系，準(zhǔn)確找到了其特征向量分量與前一時(shí)步特征向量之間的關(guān)系，從而可以計(jì)算出所有不同增長(zhǎng)模式下GDURT網(wǎng)絡(luò)的拉普拉斯特征向量；并且發(fā)現(xiàn)了每一時(shí)步下，均存在任一特征向量的第一分量均恰好來(lái)自于前一時(shí)步對(duì)應(yīng)的特征向量的特殊性質(zhì)，利用這些性質(zhì)可進(jìn)一步縮減特征向量的計(jì)算時(shí)間。

［1］戴汝為.開展“系統(tǒng)復(fù)雜性”研究任重而道遠(yuǎn)［J］．復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2004，1（3）：l-3．

［2］Borner K，Sanyal S，Vespignani A.Network science［J］.Annual Review of Information Science and Technology，2007，41：537-607.

［3］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學(xué)：網(wǎng)絡(luò)科學(xué)（上）［J］.物理學(xué)進(jìn)展，2007，27（3）：239-443.

［4］白勇，陸一南.復(fù)雜網(wǎng)絡(luò)在傳統(tǒng)經(jīng)濟(jì)系統(tǒng)上的模型研究［J］.計(jì)算機(jī)科學(xué)，2013，40（6）：265-267.

［5］Zhang Z Z，Zhou S G，Qi Y.Topologies and Laplacian spectra of a deterministic uniform recursive tree［J］.The European Physical Journal B，2008，63：507-513.

［6］Lu Z M，Guo S Z.A small-world network derived from the deterministic uniform recursive tree［J］.Physica A：Statis-tical Mechanics and Its Applications，2012，391，87-92.

［7］Lancaster P，Tismenetsky M.The Theory of Matrices with Applications［M］.Academic Press，New York，1985.

［8］章忠志.復(fù)雜網(wǎng)絡(luò)的演化模型研究［D］.大連：大連理工大學(xué)，2006.

［9］Comellas F，Ozon J，Peters J G.Deterministic small-world communication networks［J］.Information Processing Letters，2000（76）：83-90.

Laplacian spectra of the generalized deterministic uniform recursive tree networks

ZHAO Hu
（The Computer College of Qinghai Normal University，Xining 810008，China）

The DURT（Deterministic Uniform Recursive Tree）networks model got a wide range of applications in the field of modeling and properties researching of complex networks.The GDURT（Generalized Deterministic Uniform Recursive Tree）evolution model is put forward on the basis of DURT network model.The complete recursive relations of Laplacian spectra （eigenvalues）and their corresponding eigenvectors are determined by the algebraic reduction and a special optimal layered method for nodes which can rapidly reflect the evolution characteristics of the networks.Some analysis is made to reveal the main characteristics of Laplacian spectra of GDURT networks.

complex networks；evolving model；uniform recursive tree；generalized；nodes layered；laplacian spectra

TP393.0

A

1674－6236（2016）03-0121-04

2015-06-17稿件編號(hào)：201506176

國(guó)家自然科學(xué)基金（61164005）。

趙 虎（1972—），男，青海西寧人，碩士，副教授。研究方向：復(fù)雜超網(wǎng)絡(luò)模型構(gòu)建與性質(zhì)研究。