施艷昭

(安徽電子信息職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)管理系，安徽 蚌埠233000)

0 引 言

復(fù)雜網(wǎng)絡(luò)的核心問題是研究其動(dòng)態(tài)行為如何受到基礎(chǔ)拓?fù)涮卣鞯挠绊?，而?fù)雜網(wǎng)絡(luò)的最重要屬性之一是平均路徑長(zhǎng)度，它描述了所有頂點(diǎn)對(duì)之間最短路徑的平均長(zhǎng)度。平均路徑長(zhǎng)度在許多與現(xiàn)實(shí)生活網(wǎng)絡(luò)有關(guān)的領(lǐng)域中都是相關(guān)的，例如疾病的傳播或建筑設(shè)計(jì)中的路線[1-2]。但是，計(jì)算龐大復(fù)雜網(wǎng)絡(luò)的平均路徑長(zhǎng)度仍然是一項(xiàng)艱巨的任務(wù)，推導(dǎo)出平均路徑長(zhǎng)度的解析式仍然具有挑戰(zhàn)性。研究首先闡述了兩種基于邊迭代復(fù)雜網(wǎng)絡(luò)模型的構(gòu)建機(jī)理，然后著重分析最短路徑長(zhǎng)度并獲得相應(yīng)的分析結(jié)論。

1 邊迭代復(fù)雜網(wǎng)絡(luò)的構(gòu)建

為了方便起見，后文將Farey圖(Farey Graph，F(xiàn)G)表示為F(t)，其中t是指FG遞歸生成的步驟。FG的定義如下所示：假設(shè)有頂點(diǎn)集V(t)和邊集E(t)，F(xiàn)arey圖F(t)=(V(t),E(t))，t≥0的構(gòu)造步驟如下所示[3]：對(duì)于t=0，F(xiàn)(0)有兩個(gè)初始頂點(diǎn)和一條邊。對(duì)于t>0，通過在步驟t-1引入的每個(gè)邊上添加一個(gè)與該邊的端點(diǎn)相鄰的新頂點(diǎn)，便能從F(t-1)中得到F(t)。圖1顯示了從t=0到t=1的生成步驟：兩個(gè)初始頂點(diǎn)是FG的中心節(jié)點(diǎn)，F(xiàn)G是通過將新頂點(diǎn)添加到活動(dòng)邊來構(gòu)造的，然后將新頂點(diǎn)連接到活動(dòng)邊的兩個(gè)末端頂點(diǎn)。

圖1 FG構(gòu)造過程

如果改變FG的構(gòu)建機(jī)制，可以推導(dǎo)出Edge Iterations Network(EIN)網(wǎng)絡(luò)[4]。用Ni(t)表示EIN網(wǎng)絡(luò)，其構(gòu)造方式如下：對(duì)于t=0，N(0)是一個(gè)三角形，三個(gè)節(jié)點(diǎn)相互連接。對(duì)于t>0，通過在步驟t-1中創(chuàng)建的圖中的每個(gè)邊添加一個(gè)新頂點(diǎn)并將其連接到邊的兩個(gè)節(jié)點(diǎn)上[5]。圖2顯示了從t=0到t=2的生成步驟。EIN從三角形的三個(gè)邊開始構(gòu)建，而FG從單個(gè)邊開始進(jìn)行構(gòu)建。因此，F(xiàn)G等價(jià)于EIN的三分之一。EIN從三角形的三個(gè)邊緣開始，而FG從單個(gè)邊緣生成。 因此，F(xiàn)G是等效EIN的三分之一。如圖3所示，通過合并三個(gè)FG(F1(t)、F2(t)以及F3(t))，便能得到一個(gè)EIN。

2 平均路徑長(zhǎng)度分析

2.1 FG平均路徑長(zhǎng)度分析

在步驟t中，新添加到FG圖的邊的數(shù)量為ΔnFG,t=2t-1，此時(shí)FG頂點(diǎn)數(shù)量為

nFG,t=2t+1

(1)

圖2 EIN構(gòu)造過程

圖3 由FG合并得到EIN過程

(2)

接下來，有

(3)

以及

(4)

(5)

(6)

對(duì)于以下的迭代式

(7)

將初始條件D0=2代入上式，得到

DFG,t+1=

(8)

因此，F(xiàn)G的平均路徑長(zhǎng)度為

dFG,t=

(9)

圖4顯示了平均路徑長(zhǎng)度與網(wǎng)絡(luò)頂點(diǎn)數(shù)量的關(guān)系。

圖4 FG平均路徑長(zhǎng)度與網(wǎng)絡(luò)頂點(diǎn)數(shù)量的關(guān)系

2.2 EIN平均路徑長(zhǎng)度分析

EIN中頂點(diǎn)的數(shù)量可以表示為

nEIN,t=3×2t+3

(10)

如圖5所示，通過將G(t)中的頂點(diǎn)Xt和G(k)中的頂點(diǎn)Yk合并成為頂點(diǎn)Z，能得到網(wǎng)絡(luò)Gtk。

(11)

圖5 頂點(diǎn)合并

(12)

(13)

因此，網(wǎng)絡(luò)Gtk的總最短路徑如下所示：

(14)

基于上面的邊和頂點(diǎn)聚合的兩種模式，并假設(shè)在EIN中最短路徑的總和為DEIN,t，因此有：

(15)

DEIN,t==DFG,t+1+DFG,t+2+(nFG,t+1-2)×

(16)

將初始值DEIN,0=6帶入(16)，能得到

DEIN,t=3×[(2t+1)×22t+2t]

(17)

因此，EIN的平均路徑長(zhǎng)度為：

(18)

圖6 邊合并

圖7顯示了平均路徑長(zhǎng)度與網(wǎng)絡(luò)頂點(diǎn)數(shù)量的關(guān)系。

圖7 EIN平均路徑長(zhǎng)度與網(wǎng)絡(luò)頂點(diǎn)數(shù)量的關(guān)系

3 結(jié) 論

基于邊迭代的網(wǎng)絡(luò)具有相似但不完全相同的構(gòu)建機(jī)制，因此不同的邊迭代網(wǎng)絡(luò)具有不同的拓?fù)涮匦?。以FG和EIN網(wǎng)絡(luò)為研究對(duì)象，分析和對(duì)比了基于邊迭代網(wǎng)絡(luò)的平均路徑長(zhǎng)度。由研究結(jié)果可知， FG和EIN的平均路徑長(zhǎng)度會(huì)隨著網(wǎng)絡(luò)頂點(diǎn)數(shù)量呈現(xiàn)對(duì)數(shù)式的增長(zhǎng)。