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

劉遠(yuǎn)超，趙海興，梁 靜

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

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

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

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

1 DURT的生成模型

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

圖1 DURT生成過程的前4步

圖1中，每一步中的白色的頂點(diǎn)即為新生成的頂點(diǎn)。

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

因?yàn)檫@個(gè)網(wǎng)絡(luò)是個(gè)樹，于是

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

2 推廣的拉普拉斯矩陣

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

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

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

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

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

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

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

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

式子（10）是一個(gè)很重要的遞推關(guān)系式，因?yàn)槲覀兏鶕?jù)這個(gè)式子由每一步的特征值都可以直接推出下一步的特征值。

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

證明：

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

定理2：DURT的鄰接矩陣也滿足遞歸關(guān)系，并且特征值關(guān)于點(diǎn)對(duì)稱。

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

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

即鄰接矩陣的特征值關(guān)于零點(diǎn)對(duì)稱（如圖2所示）。

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

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

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

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

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

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

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

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

當(dāng)t=1時(shí)的4個(gè)特征值

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

當(dāng)k=-1時(shí)，即負(fù)的無符號(hào)拉普拉斯矩陣，由定理1可知，此時(shí)的特征值為0和-2，我們利用式子（10）代入0和-2：

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

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

證明：由二部圖（樹是一種特殊的二部圖）的拉普拉斯矩陣特征值與無符號(hào)拉普拉斯矩陣的特征值是一致的就很容易的聯(lián)想到這一點(diǎn)了。因?yàn)楫?dāng)k取負(fù)值的時(shí)候就是負(fù)的推廣的拉普拉斯矩陣，因此對(duì)于k取負(fù)值的時(shí)候的特征值進(jìn)行分析，然后再取相反數(shù)就是推廣的無符號(hào)拉普拉斯矩陣的特征值。所以由上面普通拉普拉斯矩陣的特征值和無符號(hào)拉普拉斯矩陣特征值的關(guān)系進(jìn)行同樣的分析即可得到這個(gè)結(jié)果。

3 結(jié) 論

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

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

參考文獻(xiàn)：

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

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

[3]方錦清，汪小帆，鄭志剛，等.電子物理學(xué):一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)Ⅱ[J].中國學(xué)術(shù)期刊文摘，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演化模型的拓?fù)湫再|(zhì)[J].電子設(shè)計(jì)工程，2013（12）:177-180.

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

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

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

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

[11]吳翠芳.關(guān)于圖的譜和拉普拉斯譜[D].大連：大連理工大學(xué)，2005.

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

[13]馮瑤.關(guān)于無符號(hào)拉普拉斯譜的研究[D].長(zhǎng)沙：湖南師范大學(xué)，2014.

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

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

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

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