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

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

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

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

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

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

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

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

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

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

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

2 確定性超網(wǎng)絡(luò)拓?fù)涮匦?/h2>

研究超網(wǎng)絡(luò)拓?fù)涮匦缘淖罱K目標(biāo)是了解和掌握拓?fù)涮匦允侨绾斡绊懗W(wǎng)絡(luò)結(jié)構(gòu)、功能及動力學(xué)行為的。只有對超網(wǎng)絡(luò)的拓?fù)涮匦杂星逦鞔_的認(rèn)識，才能更深入地探究超網(wǎng)絡(luò)結(jié)構(gòu)與功能，以及其與超網(wǎng)絡(luò)動力學(xué)行為之間的關(guān)系。該文對新構(gòu)建出的一類確定性超網(wǎng)絡(luò)的平均超度、超度分布、平均距離和直徑等幾個主要拓?fù)鋮?shù)進(jìn)行了理論解析，并分析了網(wǎng)絡(luò)的結(jié)構(gòu)特性，這些工作有助于更好地理解一些真實(shí)世界網(wǎng)絡(luò)的復(fù)雜性和多樣性。

2.1 平均超度

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

每個時步，超網(wǎng)絡(luò)中節(jié)點(diǎn)的增加數(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)絡(luò)中包含的總節(jié)點(diǎn)數(shù)為N(t)=ht+1，超邊數(shù)為E(t)=

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

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

2.2 超度分布

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

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

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

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

2.3 平均距離和直徑

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

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

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

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

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

圖2 確定性小世界超網(wǎng)絡(luò)自相似結(jié)構(gòu)示意圖

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

根據(jù)超網(wǎng)絡(luò)的構(gòu)造方式和結(jié)構(gòu)的自相似，可得到如下關(guān)系式：

因此，xt滿足如下的遞歸關(guān)系：

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

將式（12）代入式（7），計(jì)算可得：

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 確定性小世界超網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)號過程

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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