一類確定性小世界超網(wǎng)絡特性分析

李發(fā)旭，衛(wèi) 良

（1.青海師范大學計算機學院，青海西寧 810008；2.青海師范大學數(shù)學與統(tǒng)計學院，青海西寧 810008；3.青海師范大學藏語智能信息處理及應用國家重點實驗室，青海西寧 810008）

現(xiàn)實世界中，用超圖表示的超網(wǎng)絡更有利于刻畫真實網(wǎng)絡的某些性質[1-2]。為了深入理解網(wǎng)絡的結構與功能、行為之間的關系，學者們建立了多類超網(wǎng)絡模型[3-10]。其中，隨機演化模型雖能反映現(xiàn)實網(wǎng)絡的某些特性，但無法清晰地描述網(wǎng)絡的形成、節(jié)點間的相互作用。因此，確定性網(wǎng)絡模型引起了學者們的興趣[11-15]。目前，基于超圖結構的確定性超網(wǎng)絡的研究成果相對較少[16-19]。該文基于超圖理論構建了一類新的確定性超網(wǎng)絡模型，分析了幾個主要的拓撲特性，并給出了該模型的拉普拉斯譜的遞推關系式。

1 確定性超網(wǎng)絡建模

為了研究復雜網(wǎng)絡的演化過程和結構特性，研究者們提出了各種各樣的解決不同實際網(wǎng)絡問題的超網(wǎng)絡模型，并在此基礎上進一步研究了這些網(wǎng)絡的特性。該文提出了一種通過節(jié)點反復迭代而生成的確定性超網(wǎng)絡模型，下面給出此超網(wǎng)絡模型的演化和生成機制。

設t為超網(wǎng)絡演化的時步數(shù)，Nh,t表示t時步生成的確定性超網(wǎng)絡，則模型構建過程如下：

1）當t=0 時，設初始超網(wǎng)絡Nh,0有h≥2 個節(jié)點，以及一條包含h個節(jié)點的超邊；

2）當t≥1 時，在Nh,t-1中的每個節(jié)點新生成一條超邊，每條新生成的超邊中都新增h-1 個新節(jié)點；

3）不斷重復2），可得到t時步的確定性超網(wǎng)絡Nh,t。確定性超網(wǎng)絡模型構建過程如圖1 所示，其中h=3。

圖1 確定性超網(wǎng)絡模型構建過程

從圖1 可以觀察到，t=2 時步生成的確定性超網(wǎng)絡Nh,2是通過將Nh,1中的每個節(jié)點用Nh,0超網(wǎng)絡結構替換得到的。因此，在t≥1 時步時，只需將超網(wǎng)絡Nh,t-1中的每個節(jié)點用Nh,0網(wǎng)絡的結構替換，即可得到t時步的確定性超網(wǎng)絡Nh,t。從網(wǎng)絡構造演化過程可以看出，該超網(wǎng)絡結構具有自相似特性。

2 確定性超網(wǎng)絡拓撲特性

研究超網(wǎng)絡拓撲特性的最終目標是了解和掌握拓撲特性是如何影響超網(wǎng)絡結構、功能及動力學行為的。只有對超網(wǎng)絡的拓撲特性有清晰而明確的認識，才能更深入地探究超網(wǎng)絡結構與功能，以及其與超網(wǎng)絡動力學行為之間的關系。該文對新構建出的一類確定性超網(wǎng)絡的平均超度、超度分布、平均距離和直徑等幾個主要拓撲參數(shù)進行了理論解析，并分析了網(wǎng)絡的結構特性，這些工作有助于更好地理解一些真實世界網(wǎng)絡的復雜性和多樣性。

2.1 平均超度

節(jié)點超度是指與該節(jié)點關聯(lián)的超邊數(shù)目，節(jié)點的超度越大說明該節(jié)點越居于網(wǎng)絡的中心位置，其在網(wǎng)絡中的影響力就越大[3]。平均超度是指網(wǎng)絡中所有節(jié)點的超度的平均值，可以反映超網(wǎng)絡的稠密程度。

每個時步，超網(wǎng)絡中節(jié)點的增加數(shù)和超邊的增加數(shù)分別為ΔN(t)=N(t)-N(t-1)=h[ΔN(t-1)]和ΔE(t)=E(t)-E(t-1)=h[ΔE(t-1)]。

已知N(0)=h,ΔN(1)=h(h-1),E(0)=h和ΔE(1)=h，則ΔN(t)=ht(h-1),ΔE(t)=ht。因此，t時步超網(wǎng)絡中包含的總節(jié)點數(shù)為N(t)=ht+1，超邊數(shù)為E(t)=

因此，超網(wǎng)絡中節(jié)點的平均超度為：

由（1）式可知，當t→∞時，=1，說明此類確定性超網(wǎng)絡是非常稀疏的。

2.2 超度分布

超網(wǎng)絡的超度分布是指在超網(wǎng)絡中任意選取一節(jié)點，其超度為k的概率。超網(wǎng)絡的類型不同，其超度分布也各不相同。

設ti時刻加入超網(wǎng)絡中的節(jié)點v在t時步的超度為kv(t)，根據(jù)超網(wǎng)絡的迭代規(guī)則可知kv(t+1)=kv(t)+1，所以kv(t+1)=(t-ti)+1。

在t時步，初始時刻的h個節(jié)點的超度為kv(t)=t+1。顯然，此類超網(wǎng)絡的超度分布是離散的，分別為1,2,…,t-1,t,t+1，其對應的節(jié)點數(shù)分別為ht(h-1),ht-1(h-1),…,h2(h-1),h(h-1),h。因此，超網(wǎng)絡的超度分布為：

這意味著超度分布P(k)隨著超度k的增加呈指數(shù)形式衰減，因此，此類超網(wǎng)絡是一個指數(shù)網(wǎng)絡。

2.3 平均距離和直徑

平均距離定義為超網(wǎng)絡中所有節(jié)點之間最短距離的平均值，用來反映超網(wǎng)絡中信息的傳輸性能和傳輸效率。網(wǎng)絡的平均距離越小，則傳輸性能越好，傳輸效率則越高。大多數(shù)真實網(wǎng)絡都具有較小的平均距離。

設dt表示t時步超網(wǎng)絡的平均距離，則有：

其中，Dsum(t)表示t時步超網(wǎng)絡中所有節(jié)點之間的最短距離之和，如下：

其中，dij(t)表示t時步超網(wǎng)絡中節(jié)點vi和vj之間的最短距離。

根據(jù)超網(wǎng)絡模型構建過程可知，超網(wǎng)絡具有自相似結構。觀察圖1 的演化過程可以發(fā)現(xiàn)，t+1 時步的超網(wǎng)絡Nh,t+1是通過把網(wǎng)絡結構Nh,t拷貝h份，然后分別將每個拷貝Nh,t中超度最大的節(jié)點依次粘接到Nh,0中的h個初始節(jié)點v1,v2,…,vh上得到的，這h個拷貝分別標記為，如圖2 所示。

圖2 確定性小世界超網(wǎng)絡自相似結構示意圖

根據(jù)該超網(wǎng)絡的自相似特性，可以得到如下遞推關系：

根據(jù)超網(wǎng)絡的構造方式和結構的自相似，可得到如下關系式：

因此，xt滿足如下的遞歸關系：

由于x0=h-1，解式（11）得：

將式（12）代入式（7），計算可得：

將式（12）代入式（8），可得：

將式（13）、式（14）代入式（9），解得：

將式（16）代入式（3）可得t時步超網(wǎng)絡的平均距離為：

超網(wǎng)絡的直徑是指網(wǎng)絡中任意兩節(jié)點間距離的最大值。設Diam(t)表示t時步超網(wǎng)絡的直徑。由超網(wǎng)絡的生成機制可知，初始超網(wǎng)絡的直徑Diam(0)=1。當t≥1 時，超網(wǎng)絡Nh,t的直徑由t時步加入到網(wǎng)絡中的新節(jié)點之間的距離決定。t時步，超網(wǎng)絡中任意新節(jié)點之間的最大距離至多是Diam(t-1)+2。因此，t時步超網(wǎng)絡的直徑則滿足Diam(t)=Diam(t-1)+2=2(t-1)+1+2。

t時步時，超網(wǎng)絡的規(guī)模N(t)=ht+1，所以超網(wǎng)絡的直徑為：

觀察式（18）可以發(fā)現(xiàn)，此類超網(wǎng)絡的直徑將隨著超網(wǎng)絡的規(guī)模增大而增大，并呈現(xiàn)對數(shù)形式的增長。

3 確定性小世界超網(wǎng)絡的拉普拉斯譜

一般來說，超網(wǎng)絡的譜性質可以很好地反映其局部結構性質，以及其在超網(wǎng)絡上的動力學行為。下面分析確定性小世界超網(wǎng)絡的拉普拉斯譜的一些性質。

設Vt={v1,v2,…,vn}為超網(wǎng)絡Nh,t的節(jié)點集合。t時步超網(wǎng)絡Nh,t的鄰接矩陣記為A=(aij)n×n，是一個n階方陣，若節(jié)點vi和vj相鄰則aij=1，否則aij=0 。令Dt=diag(deg(v1),deg(v2),…,deg(vn))為Nh,t的度對角矩陣，其中deg(vi)=為節(jié)點vi的度。超網(wǎng)絡Nh,t的拉普拉斯矩陣定義為Lt=Dt-At，則多項式定義為Φ(Nh,t,μ)=det(μIt-Lt)，其中μ為Nh,t的拉普拉斯特征值，It為ht+1階的單位矩陣。

為了分析該文模型構建的超網(wǎng)絡的譜性質，提出一種有效的節(jié)點標號方法，將節(jié)點按特定的規(guī)則進行標號，這種標號規(guī)則有助于生成特殊結構的鄰接矩陣，以便于計算超網(wǎng)絡的特征值。該文提出的節(jié)點標號規(guī)則如下：

1）超網(wǎng)絡Nh,0中初始的h個節(jié)點的標號分別為1,2,…,h；

2）在隨后的每個時步，超網(wǎng)絡中每條新生成超邊中新增節(jié)點的標號由舊節(jié)點的標號i(i=1,2,…,h)及迭代時步?jīng)Q定，新增節(jié)點對應的標號分別為i+ht,i+2ht,…,i+(h+1)ht。

上述標號規(guī)則可保證超網(wǎng)絡中每個節(jié)點都具有唯一的標號。對于該文提出的超網(wǎng)絡演化模型，在t=2 和t=3 時步時，節(jié)點的標號過程如圖3 所示，其中h=3。

圖3 確定性小世界超網(wǎng)絡節(jié)點標號過程

由該文提出的超網(wǎng)絡的構造規(guī)則可知，每個時步由每個舊節(jié)點新生成的超邊中新增的節(jié)點只與當前超邊中的舊節(jié)點相鄰，根據(jù)該文給出的節(jié)點標號方法，可以方便地獲得這種相鄰關系。即標號為i+ht,i+2ht,…,i+(h-1)ht的h-1 個新節(jié)點只與標號為i(i=1,2,3,…,ht)的舊節(jié)點相鄰。標號為i的舊節(jié)點上新生成的超邊中的h-1 個標號分別為i+ht,i+2ht,…,i+(h-1)ht的新增節(jié)點之間彼此相鄰，而新生成的不同超邊中的新節(jié)點之間則不相鄰。t時步超網(wǎng)絡中的ht個舊節(jié)點的度均在t-1 時步的基礎上增加h-1，而新增的ht(h-1) 個節(jié)點的度均為h-1。根據(jù)以上分析，可得t時步此類超網(wǎng)絡Nh,t的鄰接矩陣At和度對角矩陣Dt分別為：

其中，At-1表示t-1 時步超網(wǎng)絡的鄰接矩陣，It-1為ht階的單位矩陣，元素對應的是t時步超網(wǎng)絡中某一新超邊中新增的節(jié)點間相鄰關系，或是與t-1 時步網(wǎng)絡中節(jié)點的相鄰關系。根據(jù)Nh,t構造過程和特定的節(jié)點標號規(guī)則可知，矩陣At可以看成是一個h×h的塊矩陣，且每個塊又是一個ht×ht的方陣。

根據(jù)拉普拉斯矩陣的定義Lt=Dt-At，此類超網(wǎng)絡Nh,t的拉普拉斯矩陣Lt可表示為：

因此，t時步超網(wǎng)絡Nh,t的拉普拉斯特征多項式可表示為：

其中，S=It-1(μ-h+1)。

進一步對Φ(Nh,t,μ)化簡，可得：

于是，超網(wǎng)絡拉普拉斯矩陣特征多項式可寫成如下遞推關系：

觀察式（25）可以發(fā)現(xiàn)，t時步超網(wǎng)絡有ht+1個特征值，其中有一個重數(shù)為ht(h-2)的特征根h，而其余的2ht個特征值則可通過t-1 時步超網(wǎng)絡的特征值計算得到。注意到Φ(Nh,t-1,μ) 是一個ht次多項式，多項式最高次項的系數(shù)為1，所以1 是多項式的常數(shù)項，由此可知，拉普拉斯的特征值中不包含1。

從式（28）不等式可以發(fā)現(xiàn)，所有特征值均大于或等于0，且特征值h的重數(shù)隨迭代時步數(shù)的增加呈指數(shù)形式增加。

4 結束語

該文結合復雜超網(wǎng)絡在模型構建領域的研究，提出了一種新的生成確定性超網(wǎng)絡模型的機制。這種新機制即通過節(jié)點迭代的方式，在每個時步，超網(wǎng)絡中的每個節(jié)點新生成一條超邊，每條新生成的超邊中都新增h-1 個新節(jié)點，從而生成一個新型的確定性超網(wǎng)絡模型。該文解析了此類確定性超網(wǎng)絡的平均超度、超度分布、平均距離和直徑等主要拓撲參數(shù)。分析結果表明，該確定性超網(wǎng)絡是一個稀疏的網(wǎng)絡，超度分布服從指數(shù)分布，超網(wǎng)絡的平均距離和直徑都隨著超網(wǎng)絡規(guī)模的增大呈對數(shù)形式增長，同時也反映出該超網(wǎng)絡具有小世界特性。此外，該文還采用一種有效的節(jié)點標號方法，理論推導出拉普拉斯特征值的遞推關系式。利用此遞推關系可以發(fā)現(xiàn)確定性小世界超網(wǎng)絡的拉普拉斯特征值分布有如下規(guī)律：t時步的超網(wǎng)絡拉普拉斯特征值中不含值為1 的特征值，存在一個重數(shù)為ht(h-2)的特征值h，其他特征值可利用遞推關系式計算得到。顯然，文中提出的節(jié)點標號方法有效地降低了計算超網(wǎng)絡拉普拉斯特征值的時間復雜度。研究結果也揭示出此類超網(wǎng)絡的復雜性特征，這種具有自相似特性的網(wǎng)絡也表現(xiàn)出了小世界特性，這些研究結果有助于更好地了解實際網(wǎng)絡的復雜性和多樣性。在后續(xù)的研究中，研究者可將研究重點放在改進超網(wǎng)絡的生成機制，新構建確定性無標度超網(wǎng)絡模型并分析其拓撲性質、網(wǎng)絡動力學行為等方面。