確定性均勻遞歸樹的譜分析

劉遠超，趙海興，梁 靜

（1.青海師范大學數(shù)學與統(tǒng)計學院，青海西寧810008；2.青海師范大學計算機學院，青海西寧810008）

均勻遞歸樹（Uniform Recursive Tree，URT）是隨機圖中一種很重要的模型。隨著URT模型在中世紀家族宗譜以及流行疾病傳播等領域中的應用[1-3]，人們又提出了確定性均勻遞歸樹（Deterministic Uniform Recursive Tree，DURT）的模型，對 DURT 的網(wǎng)絡特性的研究已經(jīng)有了很多的結果[4-9]。這些結果從多個方面展示了DURT的網(wǎng)絡特性，例如度分布、平均路徑長度、介數(shù)分布以及度相關性等。

對于DURT的譜的研究也同樣有大量的結果[4-5，10]。其中在文獻[4]中提出，DURT的拉普拉斯矩陣的特征值隨生成過程呈現(xiàn)出迭代的關系?；谶@個結果，我們提出了推廣的拉普拉斯矩陣Lk=kD-A，通過對推廣的拉普拉斯矩陣的特征值進行分析，我們發(fā)現(xiàn)DURT的拉普拉斯矩陣特征值的迭代關系也同樣適用于鄰接矩陣的特征值。同時對無符號拉普拉斯矩陣做同樣的推廣，對其特征值分析也發(fā)現(xiàn)了同樣的迭代關系，并且對于相同的，推廣的無符號拉普拉斯矩陣的特征值與推廣的拉普拉斯矩陣的特征值是一致的，這些結果與二部圖（樹）的拉普拉斯矩陣的特征值與無符號拉普拉斯矩陣特征值是一致的結論是相吻合的。

文中通過構造推廣的拉普拉斯矩陣，并對其特征值進行分析得到的這些結果，對我們進一步了解DURT生成過程中特征值的變化提供一些幫助。

1 DURT的生成模型

DURT是一個通過逐次迭代的過程產(chǎn)生的.我們用t表示網(wǎng)絡的生成的步數(shù)，用Ut表示經(jīng)過t步之后生成的DURT模型。于是DURT的生成過程為：當t=0時，U0是由兩個頂點以及與之相連的一條邊構成；當t≥1時，Ut通過在Ut-1的基礎上的每一個頂點產(chǎn)生一條邊以及與這條邊相連的一個新頂點，前四步的生成過程如圖1所示。

圖1 DURT生成過程的前4步

圖1中，每一步中的白色的頂點即為新生成的頂點。

用nt表示第t步中頂點的數(shù)目，用mt表示第t步中邊的數(shù)目，那么顯然有

因為這個網(wǎng)絡是個樹，于是

在這個網(wǎng)絡中頂點的最大度是t+1，并且是第0步中就存在的那兩個頂點。

2 推廣的拉普拉斯矩陣

文中是基于文獻[4]的基礎上做的進一步的研究，文獻[4]提出DURT的拉普拉斯矩陣的特征值隨生成過程呈現(xiàn)出迭代關系。于是我們設想DURT的拉普拉斯矩陣為什么會存在遞歸關系，它的拉普拉斯矩陣有何特別之處。于是我們構造了推廣的拉普拉斯矩陣Lk=kD-A，并對推廣的拉普拉斯矩陣的特征值進行分析。

圖的拉普拉斯矩陣和無符號拉普拉斯矩陣的譜的研究已經(jīng)有了大量的結果[10-15]，本文未說明的符號和專用名詞參考文獻[16]。

我們用At表示DURT第t步的鄰接矩陣，那么鄰接矩陣滿足下面的遞歸關系：

這里的每一個塊都是2t×2t的矩陣，It-1是一個單位矩陣。

這里N1=(x-k)It-1-kDt-1+At-1，N2=f(x)It-1-kDt-1+At-1以及。

根據(jù)等式（6）我們可以得到：

根據(jù)這個遞歸關系式，我們可以得到下面的遞歸關系式：

因此我們可以從式子（9）中由第t步的特征值推出第t+1步的特征值：

式子（10）是一個很重要的遞推關系式，因為我們根據(jù)這個式子由每一步的特征值都可以直接推出下一步的特征值。

定理1：推廣的拉普拉斯矩陣的第步的特征值為λ1=k-1和λ2=k+1。

證明：

所以第0步的特征值是λ1=k-1和λ2=k+1。

定理2：DURT的鄰接矩陣也滿足遞歸關系，并且特征值關于點對稱。

證明：當k=0時，推廣的拉普拉斯矩陣就是-A，由定理1，-A的兩個特征值是±1，因此A的兩個特征值也是±1。于是根據(jù)等式（10）我們可以得到第1步中的4個特征值

顯然有x1=-x4，x2=-x3。從而我們可以根據(jù)式子（10）推出DURT的鄰接矩陣的第t步的特征值有以下性質(zhì)：

即鄰接矩陣的特征值關于零點對稱（如圖2所示）。

圖2 當t=0,1,2時網(wǎng)絡的鄰接矩陣的特征值分布

當k=1時，即拉普拉斯矩陣。第0步的兩個特征值由定理1可知是1和2。并且根據(jù)式子（10），我們把0和2代入之后發(fā)現(xiàn)0所迭代出的兩個特征值是0和2，所以0和2是DURT生成過程中每一步的拉普拉斯矩陣的特征值。同時由于每一步中都有0和2，所以第t步中的特征值將全部出現(xiàn)在第t+1步中。

定理3∶0和2是DURT每一步的拉普拉斯矩陣的特征值，并且第t步中的特征值將全部出現(xiàn)在第t+1步中，且出現(xiàn)的位置是奇數(shù)位置（特征值按照遞增排序）。

證明：由于第0步的特征值是0和2，并且0所迭代出的兩個特征值是0和2，所以0和2是每一步中的特征值。

假定由第0步的特征值0在第t+1步所迭代出的所有特征值記為Tt+1，那么第1步中的特征值0在第t+1步中所迭代出的特征值就是Tt，所以第t步中的特征值將全部出現(xiàn)在第t+1步中，如圖3所示。

圖3 當t=0,1,2時網(wǎng)絡的拉普拉斯矩陣的特征值分布

對于它們出現(xiàn)的位置我們由數(shù)學歸納法證明：

根據(jù)式子（10），我們由數(shù)學歸納法：

當t=1時的4個特征值

假設當t=n-1時也成立，即第t=n-1步中的奇數(shù)位置的特征值與第t=n-2步中的特征值完全相同，所以在第t=n步中，由第t=n-1步中的奇數(shù)位置的特征值所迭代出的特征值與第t=n-1步中的特征值完全相同。根據(jù)式子（10），第t=n-1步中的每一個特征值所迭代出的兩個特征值中一個嚴格小于1，另一個嚴格大于1。且由可知λ越大，x1的值也就越大，從而第t=n-1步中的2n個特征值所迭代出的第t=n步中的前2n個特征值的位置就是第t=n-1步中的2n個特征值的位置。同理，第t=n步中的后2n個特征值也是第t=n-1步中特征值的位置，所以當t=n時，定理是成立的。

當k=-1時，即負的無符號拉普拉斯矩陣，由定理1可知，此時的特征值為0和-2，我們利用式子（10）代入0和-2：

此時的結果與k-1時恰好是相反數(shù)的關系，且為負的無符號拉普拉斯矩陣的特征值，故無符號拉普拉斯矩陣的特征值與拉普拉斯矩陣的特征值是一致的，所以我們的推廣滿足二部圖（樹）的拉普拉斯矩陣與無符號拉普拉斯矩陣的特征值是一致的這一定理。

定理4：DURT的推廣的拉普拉斯矩陣的特征值與推廣的無符號拉普拉斯矩陣的特征值是一致的。

證明：由二部圖（樹是一種特殊的二部圖）的拉普拉斯矩陣特征值與無符號拉普拉斯矩陣的特征值是一致的就很容易的聯(lián)想到這一點了。因為當k取負值的時候就是負的推廣的拉普拉斯矩陣，因此對于k取負值的時候的特征值進行分析，然后再取相反數(shù)就是推廣的無符號拉普拉斯矩陣的特征值。所以由上面普通拉普拉斯矩陣的特征值和無符號拉普拉斯矩陣特征值的關系進行同樣的分析即可得到這個結果。

3 結 論

基于DURT的拉普拉斯矩陣的特征值的迭代關系，我們通過構造推廣的拉普拉斯矩陣（無符號拉普拉斯矩陣），并且通過同樣的方法進行分析，我們發(fā)現(xiàn)DURT的鄰接矩陣也存在同樣的遞歸關系，這是本文的一個核心部分，同時根據(jù)推廣的拉普拉斯矩陣的特征值分析，也驗證了樹（DURT本身就是一棵樹）的拉普拉斯矩陣特征值與無符號拉普拉斯矩陣的特征值是一致的。

文中基于DURT的模型而構造了推廣的拉普拉斯矩陣，在未來的研究中，我們期待利用推廣的拉普拉斯矩陣這一工具，在更多的模型中挖掘出更多的網(wǎng)絡性質(zhì)以及代數(shù)性質(zhì)。

參考文獻：

[1]B?rner K，Sanyal S，Vespignani A.Network science[J].Annual Review of Information Science&Technology，2007，41（1）:537-607.

[2]方錦清，汪小帆，鄭志剛，等.電子物理學:一門嶄新的交叉科學:網(wǎng)絡科學[J].中國學術期刊文摘，2008（3）:3.

[3]方錦清，汪小帆，鄭志剛，等.電子物理學:一門嶄新的交叉科學:網(wǎng)絡科學Ⅱ[J].中國學術期刊文摘，2008（7）:3.

[4]Zhang Z，Zhou S，Yi Q，et al.Topologies and Laplacian spectra ofa deterministic uniform recursive tree[J].The European Physical Journal B，2008，63（4）:507-513.

[5]Sun W，Xuan T，Qin S.Laplacian spectrum of a family of recursive trees and its applications in network coherence[J].Journal of Statistical Mechanics Theory&Experiment，2016，2016（6）:063205.

[6]趙虎，趙海興.GDURT演化模型的拓撲性質(zhì)[J].電子設計工程，2013（12）:177-180.

[7]張科.兩種確定性小世界網(wǎng)絡模型的研究[D].西寧：青海師范大學，2014.

[8]章忠志，周水庚，方錦清.復雜網(wǎng)絡確定性模型研究的最新進展[J].復雜系統(tǒng)與復雜性科學，2008，5（4）:29-46.

[9]趙二嶺.幾類確定性網(wǎng)絡模型的特性研究[D].西寧：青海師范大學，2013.

[10]趙虎，王麗萍.分層編號法計算GDURT模型的拉普拉斯譜[J].青海師范大學學報（自科版），2015，31（1）:15-20.

[11]吳翠芳.關于圖的譜和拉普拉斯譜[D].大連：大連理工大學，2005.

[12]李發(fā)旭，衛(wèi)良.復雜網(wǎng)絡的拉普拉斯和無符號拉普拉斯特征譜分析[J].青海師范大學學報:自然科學版，2016（4）:20-26.

[13]馮瑤.關于無符號拉普拉斯譜的研究[D].長沙：湖南師范大學，2014.

[14]曾沁雪.圖的無符號拉普拉斯譜的若干結果[D].上海：華東師范大學，2012.

[15]王冬冬.圖的無符號拉普拉斯譜和距離譜的研究[D].上海：華東理工大學，2015.

[16]Bondy J A，Murty U S R.Graph Theory and Applications[J].1976.

[17]趙玉厚，楊喜崗，楊忠，等.熱分析特征值對蠕墨鑄鐵蠕化率的影響[J].西安工業(yè)大學報，2015（8）:642-647.