趙虎

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

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

趙虎

（青海師范大學(xué) 計算機學(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），通過設(shè)計一種能夠真實反映網(wǎng)絡(luò)增長演變特點的最優(yōu)節(jié)點分層編號方法，結(jié)合代數(shù)化簡，找出了能夠快速計算GDURT網(wǎng)絡(luò)的拉普拉斯特征值和特征向量遞推關(guān)系式，并對GDURT網(wǎng)絡(luò)的拉普拉斯譜性質(zhì)做了分析。

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

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

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

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

1　GDURT演化模型及其拓撲性質(zhì)

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

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

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

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

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

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

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

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

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

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

2.1拉普拉斯特征值

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2拉普拉斯特征向量

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

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

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

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

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

3　結(jié)　論

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

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

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

［1］戴汝為.開展“系統(tǒng)復(fù)雜性”研究任重而道遠［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é)進展，2007，27（3）：239-443.

［4］白勇，陸一南.復(fù)雜網(wǎng)絡(luò)在傳統(tǒng)經(jīng)濟系統(tǒng)上的模型研究［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稿件編號：201506176

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

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