廣義確定性均勻遞歸樹網絡的拉普拉斯譜

趙虎

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

廣義確定性均勻遞歸樹網絡的拉普拉斯譜

趙虎

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

在復雜網絡的模型構建與性質研究領域中，確定性均勻遞歸樹網絡模型DURT（Deterministic Uniform Recursive Tree）得到了廣泛應用。在DURT網絡模型的基礎上提出一種適用范圍更廣的廣義確定性均勻遞歸樹演化模型GDURT（Generalized Deterministic Uniform Recursive Tree），通過設計一種能夠真實反映網絡增長演變特點的最優節點分層編號方法，結合代數化簡，找出了能夠快速計算GDURT網絡的拉普拉斯特征值和特征向量遞推關系式，并對GDURT網絡的拉普拉斯譜性質做了分析。

復雜網絡；演化模型；確定性均勻遞歸樹；廣義；節點分層；拉普拉斯譜

復雜系統在現實世界中普遍存在，受制于其龐大的系統規模和各項系統要素之間的復雜關系，人們對復雜系統的結構、性質以及二者之間的相互作用機理的了解十分有限［1］。而確定性模型的建模和性質研究在復雜系統研究領域中充當著十分重要的角色。

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

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

1　GDURT演化模型及其拓撲性質

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

圖1　GDURT網絡模型構建過程Fig.1　Construction process of GDURT network model

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

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

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

GDURT網絡演化過程中的度相關性knn（k）近似為關于k的線性關系，說明該網絡模型是協調的［8］，在每一個時步，新加入到網絡中的節點優先與度較大或具有相同度的節點連接。

2　GDURT網絡的拉普拉斯特征值和特征向量

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

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

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

2.1拉普拉斯特征值

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

圖2　當l=2時，對t=2，t=3時步網絡中的節點實施分層編號Fig.2　Hierarchical numbering to nodes of the network wherel=2 and t=2，t=3 respectively

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

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

對網絡Ut的度對角矩陣Dt，需同樣遵守上述節點編號規則，不難看出GDURT網絡在t時步的拉普拉斯矩陣Lt為：

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

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

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

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

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

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

已知t-1時步網絡的拉普拉斯特征多項式具有如下形式：

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

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

當t=1，2，3時的特征值如圖3所示。

圖3　當l=1，t=1，2，3時網絡的拉普拉斯特征值分布Fig.3　Laplacian eigenvalue distribution of network where l=1 andt=1，2，t=3 respectively

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

2.2拉普拉斯特征向量

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

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

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

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

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

3　結　論

傳統的遞歸樹（URT）和均勻遞歸樹（DURT）網絡演化模型的提出，為復雜網絡確定性演化模型的構建及其相關性質研究研究奠定了堅實的基礎，但是相對過于簡單的演化過程得該模型的應用受到了一定的局限［3］。文中所討論的推廣確定性均勻遞歸樹模型（GDURT）可應用于與URT網絡類似的仿真模擬實驗或實際模型的研究中，并具有更強的靈活度和適應性。

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

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

［1］戴汝為.開展“系統復雜性”研究任重而道遠［J］．復雜系統與復雜性科學，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］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學：網絡科學（上）［J］.物理學進展，2007，27（3）：239-443.

［4］白勇，陸一南.復雜網絡在傳統經濟系統上的模型研究［J］.計算機科學，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］章忠志.復雜網絡的演化模型研究［D］.大連：大連理工大學，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

國家自然科學基金（61164005）。

趙 虎（1972—），男，青海西寧人，碩士，副教授。研究方向：復雜超網絡模型構建與性質研究。