基于邊迭代的復雜網(wǎng)絡平均路徑長度分析研究①

施艷昭

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

0 引 言

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

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

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

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

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

2 平均路徑長度分析

2.1 FG平均路徑長度分析

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

nFG,t=2t+1

(1)

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

圖3 由FG合并得到EIN過程

(2)

接下來，有

(3)

以及

(4)

(5)

(6)

對于以下的迭代式

(7)

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

DFG,t+1=

(8)

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

dFG,t=

(9)

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

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

2.2 EIN平均路徑長度分析

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

nEIN,t=3×2t+3

(10)

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

(11)

圖5 頂點合并

(12)

(13)

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

(14)

基于上面的邊和頂點聚合的兩種模式，并假設在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的平均路徑長度為：

(18)

圖6 邊合并

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

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

3 結(jié) 論

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