確定性層次網(wǎng)絡(luò)建模方法及特性分析

李 鍇， 吳 緯， 劉福勝

(1.陸軍裝甲兵學(xué)院裝備保障與再制造系， 北京 100072； 2. 北京特種車輛研究所， 北京 100072)

近年來，利用復(fù)雜網(wǎng)絡(luò)理論研究現(xiàn)實(shí)世界中的復(fù)雜巨系統(tǒng)是研究熱點(diǎn)之一[1-3]，如武器裝備體系網(wǎng)絡(luò)[4]、生物網(wǎng)絡(luò)[5]和郵件網(wǎng)絡(luò)[6]等。構(gòu)建符合復(fù)雜巨系統(tǒng)的網(wǎng)絡(luò)模型是問題研究的關(guān)鍵，現(xiàn)階段的主要網(wǎng)絡(luò)模型有ER隨機(jī)網(wǎng)絡(luò)模型[7]、WS小世界網(wǎng)絡(luò)模型[8]和BA無標(biāo)度網(wǎng)絡(luò)模型[9]等。小世界效應(yīng)和無標(biāo)度特性為許多實(shí)際復(fù)雜網(wǎng)絡(luò)共同的全局拓?fù)涮匦?，但全局拓?fù)涮匦韵嗨频膹?fù)雜網(wǎng)絡(luò)往往具備不同的局部拓?fù)涮匦裕虼朔治鲅芯烤W(wǎng)絡(luò)局部拓?fù)涮匦砸彩种匾?。模塊(module)是指由少部分網(wǎng)絡(luò)節(jié)點(diǎn)按照一定拓?fù)浣Y(jié)構(gòu)組成、并在網(wǎng)絡(luò)中復(fù)制出現(xiàn)的節(jié)點(diǎn)組合[10]。從本質(zhì)上來講，模塊是在網(wǎng)絡(luò)中大量重復(fù)出現(xiàn)的、具有特定拓?fù)浣Y(jié)構(gòu)的小規(guī)模子圖(如食物鏈網(wǎng)[11]和交通網(wǎng)[12]等均發(fā)現(xiàn)模塊的存在)，這些子圖從局部層面上描述了網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)的連接方式。因此，雖然網(wǎng)絡(luò)模塊往往具備不同的局部拓?fù)浣Y(jié)構(gòu)，但網(wǎng)絡(luò)模型在整體層面上表現(xiàn)出一致的層次模塊性(hierarchical modularity)。

構(gòu)建確定性層次網(wǎng)絡(luò)(Deterministic Hierarchical Network,DHN)模型的方法有多種[13]，而層次網(wǎng)絡(luò)模型大都是針對特定應(yīng)用背景而提出的，如：RAVASZ等[10]對復(fù)雜網(wǎng)絡(luò)中的層次模塊性進(jìn)行了分析，說明無標(biāo)度特性和層次模塊性是許多實(shí)際復(fù)雜網(wǎng)絡(luò)的基本特性；WANG等[14]構(gòu)建了具備“局部偏好連接”特性的層次網(wǎng)絡(luò)模型，并分析了其無標(biāo)度特性和層次模塊性，證明該模型具備合理性；袁銘[15]對層次網(wǎng)絡(luò)中的級聯(lián)效應(yīng)進(jìn)行了分析，在不完全信息和負(fù)載重分配的模式下，對復(fù)雜網(wǎng)絡(luò)的可靠性進(jìn)行了研究，并對層次網(wǎng)絡(luò)的可靠性優(yōu)化提出了合理建議；DONG等[16]建立了樹狀加權(quán)層次網(wǎng)絡(luò)模型，并對社交網(wǎng)絡(luò)進(jìn)行進(jìn)一步分析，計(jì)算結(jié)果說明社交網(wǎng)絡(luò)具備小世界效應(yīng)和無標(biāo)度特性。

武器裝備體系網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)代表裝備實(shí)體，網(wǎng)絡(luò)鏈路表示裝備實(shí)體間物質(zhì)流、能量流和信息流的交換，以及裝備實(shí)體彼此之間指揮控制和協(xié)同保障等多種復(fù)雜關(guān)系[4]。在體系對抗過程中，武器裝備體系需要持續(xù)的信息獲取和快捷的信息傳輸，同時(shí)指揮控制系統(tǒng)作為體系網(wǎng)絡(luò)中的“神經(jīng)中樞”負(fù)責(zé)一系列作戰(zhàn)任務(wù)，該類節(jié)點(diǎn)作為“偏好連接”的目標(biāo)節(jié)點(diǎn)成為體系網(wǎng)絡(luò)中的Hub節(jié)點(diǎn)，這說明武器裝備體系網(wǎng)絡(luò)具備小世界效應(yīng)和無標(biāo)度特性。分析武器裝備體系網(wǎng)絡(luò)層次模塊性，可以將體系網(wǎng)絡(luò)自上而下分為體系層、系統(tǒng)層、平臺層和單元層，從而可以準(zhǔn)確表示體系網(wǎng)絡(luò)中不同層次結(jié)構(gòu)的交互關(guān)系。由低層次向高層次逐步聚合時(shí)，往往會(huì)發(fā)生宏觀特性的變化。

為進(jìn)一步分析武器裝備體系網(wǎng)絡(luò)的拓?fù)涮匦?，?gòu)建滿足體系網(wǎng)絡(luò)特性的理論模型，CHEN等[17]提出了網(wǎng)絡(luò)模塊尺寸為2的樹狀DHN模型的構(gòu)建方法，但該方法對應(yīng)的層次網(wǎng)絡(luò)模型缺乏普遍性，不能對一般情形下的層次網(wǎng)絡(luò)模型進(jìn)行研究。基于此，筆者構(gòu)建以任意正整數(shù)m(m>1)為網(wǎng)絡(luò)模塊尺寸的DHN模型，并對該模型的小世界效應(yīng)、無標(biāo)度特性和層次模塊性進(jìn)行理論分析和數(shù)值仿真證明。

1 DHN模型的構(gòu)建及拓?fù)涮卣?/h2>

1.1 DHN模型的構(gòu)建

對于實(shí)際復(fù)雜網(wǎng)絡(luò)，“增長”(growth)和“偏好連接”(preferential attachment)是2個(gè)非常重要的特性。當(dāng)網(wǎng)絡(luò)中出現(xiàn)“馬太效應(yīng)”時(shí)，其度分布函數(shù)會(huì)表現(xiàn)出明顯的冪律特征[18]，層次網(wǎng)絡(luò)模型主要通過網(wǎng)絡(luò)模塊復(fù)制并迭代的方式構(gòu)成，利用網(wǎng)絡(luò)模塊結(jié)構(gòu)識別網(wǎng)絡(luò)局部連接模式，可以對復(fù)雜網(wǎng)絡(luò)模型進(jìn)行簡化，容易對網(wǎng)絡(luò)的全局拓?fù)涮匦约皠?dòng)態(tài)演化性作進(jìn)一步分析。綜合以上分析，本文DHN(n,m)模型構(gòu)建方法如下：

1) 初始時(shí)刻。規(guī)定網(wǎng)絡(luò)層數(shù)n=0，網(wǎng)絡(luò)中僅存在一個(gè)孤立節(jié)點(diǎn)，定義為DHN模型的根節(jié)點(diǎn)。

2) 網(wǎng)絡(luò)增長。逐層增加網(wǎng)絡(luò)節(jié)點(diǎn)，第n(n>0)層中的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目為mn，其中m為網(wǎng)絡(luò)模塊尺寸，滿足m>1。

3) 偏好連接。第n(n>0)層中所有節(jié)點(diǎn)的度值為n，分別連接每個(gè)節(jié)點(diǎn)對應(yīng)的第0至n-1層中的n個(gè)父節(jié)點(diǎn)。

在DHN(n,m)模型中，網(wǎng)絡(luò)模塊通過復(fù)制并迭代的方式彼此相互連接，“偏好連接”的目標(biāo)節(jié)點(diǎn)為自身對應(yīng)的父節(jié)點(diǎn)，網(wǎng)絡(luò)模型中每次迭代的新增鏈路數(shù)目與新增節(jié)點(diǎn)的層級數(shù)相關(guān)，并不是固定的常數(shù)。

圖1為n=4，m=3時(shí)的DHN(n,m)模型拓?fù)浣Y(jié)構(gòu)圖。圖中：節(jié)點(diǎn)的顏色共有5種，表示網(wǎng)絡(luò)的層為n+1=5層；DHN(n,m)模型中的根節(jié)點(diǎn)作為整個(gè)網(wǎng)絡(luò)的連接中心點(diǎn)，除根節(jié)點(diǎn)后的剩余子網(wǎng)絡(luò)可近似分為3部分，表明每個(gè)網(wǎng)絡(luò)模塊中父節(jié)點(diǎn)包含的子節(jié)點(diǎn)數(shù)為3。

1.2 DHN模型的拓?fù)涮卣?/h3>

假定DHN(n,m)模型的層數(shù)為n+1，網(wǎng)絡(luò)模型中第n層的節(jié)點(diǎn)數(shù)mn，各層節(jié)點(diǎn)數(shù)目滿足等比數(shù)列，則DHN(n,m)模型中的節(jié)點(diǎn)總數(shù)

(1)

網(wǎng)絡(luò)中的鏈路總數(shù)E滿足

(2)

化簡后可得

(3)

網(wǎng)絡(luò)模型中節(jié)點(diǎn)的平均度值

(4)

對于DHN(n,m)模型中第i(0≤i≤n)層中的第j(1≤j≤mi)個(gè)節(jié)點(diǎn)vi-j，其度值ki-j滿足

ki-j=kout+kin，

(5)

式中：kout為節(jié)點(diǎn)vi-j作為子節(jié)點(diǎn)時(shí)連接父節(jié)點(diǎn)的數(shù)目，kin為節(jié)點(diǎn)vi-j作為父節(jié)點(diǎn)時(shí)連接子節(jié)點(diǎn)的數(shù)目，即

(6)

聯(lián)立式(5)、(6)可得

(7)

在DHN(n,m)模型中，對于i=0層的根節(jié)點(diǎn)和i=n層的葉節(jié)點(diǎn)，ki-j分別取

(8)

kmin=n。

(9)

2 小世界效應(yīng)分析

WATTS等[8]在規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上，通過“隨機(jī)重連”鏈路方式得到WS小世界網(wǎng)絡(luò)模型，他們發(fā)現(xiàn)：盡管復(fù)雜網(wǎng)絡(luò)本身包含較大的網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，但網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)之間的路徑長度相對較小。小世界效應(yīng)主要包含較小的平均路徑長度L和較大的平均聚類系數(shù)C兩個(gè)特征，本節(jié)分別對這2個(gè)特征進(jìn)行分析。

1) 平均路徑長度L

在DHN(n,m)模型中，節(jié)點(diǎn)vi-j與模型中剩余節(jié)點(diǎn)的路徑長度之和

(10)

其中：第1項(xiàng)表示vi-j的鄰居節(jié)點(diǎn)與vi-j直接連接，路徑長度為1；第2項(xiàng)表示對于非鄰居的其他任意節(jié)點(diǎn)，都通過根節(jié)點(diǎn)與vi-j連接，路徑長度為2。

將式(10)化簡可得

(11)

對整個(gè)DHN(n,m)模型進(jìn)行分析，則平均路徑長度

(12)

當(dāng)網(wǎng)絡(luò)層數(shù)n→+∞時(shí)，平均路徑長度L≈2，說明網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)均通過根節(jié)點(diǎn)進(jìn)行相互連接。

圖2為3種網(wǎng)絡(luò)模型中L與N的關(guān)系曲線?？梢钥闯觯篧S網(wǎng)絡(luò)和BA網(wǎng)絡(luò)模型的路徑長度L隨節(jié)點(diǎn)總數(shù)N增加而逐漸增大，DHN(n,m)模型則滿足L→2。DHN(n,m)模型具備較小的平均路徑長度，說明在網(wǎng)絡(luò)連通性和網(wǎng)絡(luò)效率方面比WS網(wǎng)絡(luò)和BA網(wǎng)絡(luò)模型更好。

2) 平均聚類系數(shù)C

1) 節(jié)點(diǎn)vi-j的父節(jié)點(diǎn)之間直接相連：

2) 節(jié)點(diǎn)vi-j的父節(jié)點(diǎn)與子節(jié)點(diǎn)直接相連：

3) 節(jié)點(diǎn)vi-j的子節(jié)點(diǎn)彼此相連：

其中E3中不包括第i層節(jié)點(diǎn)與第i+1層節(jié)點(diǎn)之間的鏈路。

節(jié)點(diǎn)vi-j的聚類系數(shù)

2mi(1-m)(1-mn-i)+2[(m-1)(n-1)-

m]mn-i+1+2m2}/[ki-j(ki-j-1)(m-1)2],

(13)

DHN(n,m)模型的聚類系數(shù)為所有節(jié)點(diǎn)聚類系數(shù)的平均值，即

(14)

圖3為3種網(wǎng)絡(luò)模型中C與N的關(guān)系曲線?？梢钥闯觯号cWS網(wǎng)絡(luò)和BA網(wǎng)絡(luò)模型相比，DHN(n,m)模型中的C明顯較大；BA網(wǎng)絡(luò)模型中的C隨N增大而減小，WS網(wǎng)絡(luò)和DHN(n,m)模型中的C與N則不具備相關(guān)性；當(dāng)N→104時(shí)，DHN(n,m)模型的聚類系數(shù)滿足C≈1，說明DHN(n,m)模型中節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)構(gòu)成緊密的團(tuán)簇形式，三角拓?fù)浣Y(jié)構(gòu)在網(wǎng)絡(luò)中的比重較大，整個(gè)網(wǎng)絡(luò)模型具備嚴(yán)密的組織結(jié)構(gòu)。

綜合分析DHN(n,m)模型的平均路徑長度和平均聚類系數(shù)的理論計(jì)算與數(shù)值仿真結(jié)果，充分說明DHN(n,m)模型具備小世界效應(yīng)。

3 無標(biāo)度特性分析

無標(biāo)度特性是許多實(shí)際復(fù)雜網(wǎng)絡(luò)具備的共同特性，主要是指網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的鏈路數(shù)很少，存在少量的Hub節(jié)點(diǎn)但擁有大量的鏈路，度分布表現(xiàn)為冪律分布的形式，即p(k)～k-γ。BARABASI等[9]證明BA網(wǎng)絡(luò)模型度分布滿足p(k)=2m2k-3，符合冪律分布規(guī)律。

對于DHN(n,m)模型，節(jié)點(diǎn)vi-j的度ki-j與節(jié)點(diǎn)的位置i有關(guān)，任意選取一個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)位于第i層的概率

(15)

DHN(n,m)模型的度分布函數(shù)p(k)應(yīng)滿足以下2個(gè)條件：

聯(lián)立式(1)、(15)，可得

(16)

需要構(gòu)建p(k)，使得p(k)=p(i)成立，則由條件2)可得

(17)

聯(lián)立式(16)、(17)得到

(18)

對式(18)進(jìn)行歸一性分析，則有

(19)

由式(19)可知：p(k)滿足歸一性。

對于DHN(n,m)模型，度分布函數(shù)

(20)

說明DHN(n,m)模型滿足無標(biāo)度特性。

圖4為DHN(n,m)模型和BA模型的p(k)計(jì)算結(jié)果?？梢钥闯觯涸陔p對數(shù)坐標(biāo)系下，當(dāng)k>30時(shí)，DHN(n,m)模型的p(k)曲線近似為一條斜率為負(fù)值的直線，但BA網(wǎng)絡(luò)模型對應(yīng)直線斜率的絕對值更大。這是因?yàn)椋築A網(wǎng)絡(luò)模型的度分布滿足p(k)～k-3，而DHN(n,m)模型的度分布為p(k)∝k-1，2種網(wǎng)絡(luò)模型的度分布指數(shù)存在差異性。

圖5為不同參數(shù)下DHN(n,m)模型的p(k)計(jì)算結(jié)果?？梢钥闯觯涸陔p對數(shù)坐標(biāo)系下，當(dāng)DHN(n,m)模型的網(wǎng)絡(luò)參數(shù)n和m不同時(shí)，對應(yīng)的p(k)曲線幾乎完全重合，且當(dāng)n→+∞時(shí)，p(k)曲線可近似為一條斜率等于-1的直線。這說明網(wǎng)絡(luò)參數(shù)n和m與網(wǎng)絡(luò)模型的無標(biāo)度特性不具備相關(guān)性，而是網(wǎng)絡(luò)模型自身的拓?fù)涮匦浴?/p>

4 層次模塊性分析

RAVASZ等[10]通過分析發(fā)現(xiàn)：復(fù)雜網(wǎng)絡(luò)中層次模塊性的重要特征是聚-度關(guān)聯(lián)性(clustering-degree correlations)滿足冪律分布。通常用C(k)表示度值為k的所有節(jié)點(diǎn)的平均聚類系數(shù)，C(k)與k滿足C(k)～k-α，其中α為分布指數(shù)。在理論網(wǎng)絡(luò)模型中，ER隨機(jī)網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)的度分布函數(shù)p(k)滿足泊松分布，整個(gè)網(wǎng)絡(luò)表現(xiàn)為均勻網(wǎng)絡(luò)的形式，C(k)與度值k無相關(guān)性；BA無標(biāo)度網(wǎng)絡(luò)度分布函數(shù)p(k)滿足冪律分布，但C(k)→0，不滿足C(k)～k-α[10]。

對于DHN(n,m)模型，聯(lián)立式(7)、(13)可得

(21)

當(dāng)n→+∞時(shí)，則有

(22)

此時(shí)，式(21)中第2項(xiàng)近似等于0，得到

(23)

由式(23)可知：對于任意節(jié)點(diǎn)vi-j，其度值ki-j與其系數(shù)Ci-j滿足冪律分布。因此，可得C(k)∝k-1,說明DHN(n,m)模型具備層次模塊性。

圖6為DHN(n,m)模型中聚-度曲線?？梢钥闯觯?/p>

1)對于不同網(wǎng)絡(luò)參數(shù)n和m，C(k)曲線基本都表現(xiàn)為斜率近似等于-1的直線，說明DHN(n,m)模型具備層次模塊性，網(wǎng)絡(luò)參數(shù)n和m與C(k)不具備相關(guān)性；2)C(k)，說明節(jié)點(diǎn)聚類系數(shù)C(k)隨節(jié)點(diǎn)度值k的增大而減小，度值很小的節(jié)點(diǎn)具備較大的聚類系數(shù)并屬于不同的網(wǎng)絡(luò)模塊，而Hub節(jié)點(diǎn)的聚類系數(shù)較小，僅發(fā)揮連接網(wǎng)絡(luò)模塊的作用。在DHN(n,m)模型中，網(wǎng)絡(luò)模塊內(nèi)部連接緊密，而模塊彼此之間松散關(guān)聯(lián)，從而通過復(fù)制迭代構(gòu)成更大的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

5 結(jié)論

筆者基于“增長”和“偏好連接”的復(fù)雜網(wǎng)絡(luò)特性，通過網(wǎng)絡(luò)模塊復(fù)制并逐步迭代的方式，提出符合一般情形下的DHN(n,m)模型構(gòu)建方法，并通過理論分析和數(shù)值仿真證明該網(wǎng)絡(luò)模型滿足小世界效應(yīng)、無標(biāo)度特性和層次模塊性。結(jié)果說明：DHN(n,m)模型的網(wǎng)絡(luò)連通性優(yōu)于WS小世界模型和BA無標(biāo)度模型；度分布函數(shù)p(k)和聚-度C(k)曲線在雙對數(shù)坐標(biāo)系下集中體現(xiàn)為斜率等于-1的直線，說明DHN(n,m)模型的無標(biāo)度特性和層次模塊性與網(wǎng)絡(luò)參數(shù)不具備相關(guān)性。

對于網(wǎng)絡(luò)理論模型本身，DHN(n,m)模型中的“偏好連接”針對全局網(wǎng)絡(luò)中的父節(jié)點(diǎn)，下一步可分析局部“偏好連接”增長方式對網(wǎng)絡(luò)拓?fù)涮匦缘挠绊?，同時(shí)引入“隨機(jī)重連”和“隨機(jī)增邊”方法，構(gòu)建更加復(fù)雜的層次網(wǎng)絡(luò)模型。