ORF  >> Vol. 9 No. 4 (November 2019)

    一種改進的多局域世界網絡模型
    An Improved Multi-Local-World Network Model

  • 全文下載: PDF(472KB) HTML   XML   PP.285-291   DOI: 10.12677/ORF.2019.94033  
  • 下載量: 124  瀏覽量: 815  

作者:  

張璐璐:中央民族大學,北京

關鍵詞:
多局域世界網絡模型不等性競爭性Multi-Local-World Network Model Inequality Competitiveness

摘要:

本文在多局域世界網絡模型的基礎之上,引入了局域網間的不等性,競爭性,構建了改進的多局域世界網絡模型,并對該模型的度分布進行分析。該模型網絡度分布服從冪律分布,網絡為無標度網絡。

On the basis of Multi-Local-World network model, this paper introduces the inequality and com-petitiveness among local networks, constructs an improved Multi-Local-World model, and analyses the degree distribution of the model. The network degree distribution of the model obeys power-law distribution, and the network is scale-free network.

1. 引言

近年來,復雜網絡的研究受到學者的關注。復雜網絡的理論與模型也得到了極大的豐富。大家結合自己的研究領域,研究對象的特征,對相關模型進行改進。Chen [1] 為了研究Internet網中拓撲特性產生的機理,建立了多局域世界演化模型,在該模型中,整個網絡由多個獨立的局域網組成,網絡的演化就如新節點的加入,邊的增加,邊的刪減都在局域網中進行,僅對該局域網中節點的度產生影響,對其他局域網節點沒有太大影響;后來學者們又根據研究所需對該模型進行改進,田思 [2] 根據現實網絡的局域性及聯系的強弱,將權重引入到多局域世界模型之中,構造了加權多局域世界演化模型;李曉 [3] 將局域性與賦權性加入到全局無權網絡,構造了多局域加權n網絡,并進行仿真模擬,研究模型的拓撲性質。

現實生活中的大多數網絡雖然包含多個局域網,但局域網卻不像多局域世界網絡模型 [4] 中的局域網那樣均勻,它們有著不同數量的節點,不同數量的邊,甚至局域網之間還存在著競爭關系。如國際對外直接投資網絡,可以根據國家所處地區將整個投資網絡分成不同的區域(局域網),且每個區域中的國家數量不同,各個區域中國家間投資關系聯系的緊密程度不同,即每個區域規模不同;由于各個區域發展程度不同,對外政策,開放程度不同,所以每個區域增加新投資關系的可能性也不同,即區域之間存在競爭關系,所以在運用多局域世界網絡模型取刻畫投資網絡時,會發現存在很多局限。本文嘗試在多局域世界網絡模型的基礎之上,引入局域網間的不等性,競爭性,構造改進的多局域世界網絡演化模型,并對該模型的度分布進行研究。

2. 模型建立與分析

2.1. 改進的多局域世界模型(IMLW)

多局域世界網絡的初始條件是有著m個擁有 m 0 個節點和 e 0 條邊的局域網絡,且這m個局域網之間節點數,邊數都相同,局域網間也不存在競爭關系。但對于現實生活中的許多網絡而言,它雖然也包括多個起始的網絡,但它們之間并不是均等的,這些網絡有著不同的節點數和邊數,對新節點有著不同的吸引力,也就是說,局域網絡之間存在著競爭。那么,為了使得模型更貼合現實生活中的網絡,需要對多局域世界網絡進行改進,使得改進的網絡模型更加確切的解釋真實網絡的結構特征的產生機理。

初始條件:起始為m個獨立的局域網,每個網絡有 m i 個節點和 條邊( i = 1 , 2 , ? , m ),(記 M = i = 1 m m i ,即初始網絡中總共有M個節點),且局域網之間存在著競爭,賦予每個局域網 Ω p 一個參數,表明該局域網競爭系數 r p ( p = 1 , 2 , ? , m ) ,接下來每一個時間步長內,都進行如下的操作:

1) 以概率 p 1 增加一個新節點到一個選定的局域網中,且與該局域網中的節點建立 n 1 條邊。首先需要選定一個局域網Ωp,其概率為 r p q = 1 m r q (2.11),接下來新節點與該網絡節點i連接的概率為按照度擇優的原則

(2.12)

2) 以概率 p 2 增加 n 2 條邊到選定的局域網中。首先需要選首先按照2.11式選定一個局域網 Ω p ,隨機

選擇該網絡中的一個節點,概率為 1 N Ω p ( t ) ,接下來按2.12式選定另一個節點,重復上述過程次。

3) 以概率 p 3 在選定的局域網中去掉 n 3 條邊。首先需要選定一個局域網 Ω p ,根據反擇優原則,那么一個局域網的競爭力越低被選擇的概率就越大。選定局域網Ωp的概率為 1 ? r p q = 1 m r q ,接下來隨機選擇一個節點,概率為 1 N Ω p ( t ) ,然后反擇優選擇另一節點,其概率為

( k i ) = 1 N Ω p ( t ) ? 1 ( 1 ? ( k i ) ) = 1 N Ω p ( t ) ? 1 ( 1 ? k i j Ω p k j )

4) 以概率 p 4 選定一個局域網,讓其與其它局域網建立 n 4 條長程邊。首先按照2.11選定一個局域網Ωr,然后在該網絡中按照2.12式選定一個節點,再按2.11式選擇一個局域網Ωp,并在該局域網中按2.12式選擇一個節點與之前節點相連,重復上述過程 n 4 次。

5) 終止條件,運行N步。

其中 p 1 + p 2 + p 3 + p 4 = 1 ,改進的多局域世界網絡模型最終生成的網絡為m個大小不均的局域網,每個局域網中的節點數,邊數都不等。局域網間緊密程度,節點數,邊數差距的取決于初始網絡中各局域網的競爭力 r p ( p = 1 , 2 , ? , m ) ,競爭系數越大的局域網,在整個演變過程中增加節點,邊的幾率越大,最終的局域網規模越大,節點間的聯系越密切。若 r p ( p = 1 , 2 , ? , m ) 中存在某一個局域網的競爭系數遠遠大于其它局域網的競爭系數,那么最終的網絡由一個規模較大的局域網和幾個規模較小的局域網構成。

2.2. 度分布分析

接下來采用解析方法中的平均場理論來求解改進多局域世界網絡模型的度分布,具體計算過程如下:

1) 增加一個帶有 n 1 條邊的節點到一個選定的局域網Ωp中。

( ? k i ? t ) 1 = n 1 p 1 r p q = 1 m r q k i j Ω p k j (2.13)

2) 增加 n 2 條邊到選定的局域網中。

( ? k i ? t ) 2 = n 2 p 2 r p q = 1 m r q [ 1 N Ω p ( t ) + ( 1 ? 1 N Ω p ( t ) ) k i j Ω p k j ] (2.14)

3) 在選定的局域網中去掉 n 3 條邊。

( ? k i ? t ) 3 = ? n 3 p 3 ( 1 ? r p q = 1 m r q ) [ 1 N Ω p ( t ) + ( 1 ? 1 N Ω p ( t ) ) 1 N Ω p ( t ) ? 1 ( 1 ? k i j Ω p s j ) ] (2.15)

4) 選定一個局域網,讓其與其它局域網建立 n 4 條長程邊。

( ? k i ? t ) 4 = n 4 p 4 ( r p q = 1 m r q k i j Ω p k j + r j q = 1 m r q k i j Ω p k j ) (2.16)

經過t個時間步長后,整個網絡中增加的節點數為 Δ ( N ( t ) ) = p 1 t ,局域網中增加的節點數與局域網的競爭系數成正比,局域網的競爭系數越大,增加的節點數就越多。局域網Ωp增加的節點數為 r p q = 1 m r q Δ ( N ( t ) ) = r p q = 1 m r q p 1 t ,每個局域網中的節點數應當是初始時刻局域網所含的節點數加上增加的節點數,局域網Ωp中的節點數目為

N Ω p ( t ) = m p + r p q = 1 m r q p 1 t (2.17)

當時間t無限大時,可以忽略 m p 的影響,則 N Ω p ( t ) = r p q = 1 m r q p 1 t (2.18)

經過t個時刻后,節點的總度增加了 Δ k = 2 t ( n 1 p 1 + n 2 p 2 ? n 3 p 3 + n 4 p 4 ) ,令 c = 2 ( n 1 p 1 + n 2 p 2 ? n 3 p 3 + n 4 p 4 ) ,則 Δ k = c t ,局域網增加度與局域網的競爭系數成正比,局域網 Ω p 增加度 Δ k Ω p = c t r p q = 1 m r q ,局域網Ωp中的度等于初始時刻局域網中的度與t個時刻增加的度之和,故 k Ω p = c t r p q = 1 m r q + 2 e p ,當時間t無限大時, k Ω p = c t r p q = 1 m r q (2.19)

則度對時間的變化率為

? k i ? t = ( ? k i ? t ) 1 + ( ? k i ? t ) 2 + ( ? k i ? t ) 3 + ( ? k i ? t ) 4 = n 1 p 1 r p q = 1 m r q k i j Ω p k j + n 2 p 2 r p q = 1 m r q [ 1 N Ω p ( t ) + ( 1 ? 1 N Ω p ( t ) ) k i j Ω p k j ] ? ? ? n 3 p 3 ( 1 ? r p q = 1 m r q ) [ 1 N Ω p ( t ) + ( 1 ? 1 N Ω p ( t ) ) 1 N Ω p ( t ) ? 1 ( 1 ? k i j Ω p k j ) ] ? ? + n 4 p 4 [ r p q = 1 m r q k i j Ω p k j + r j q = 1 m r q k i j Ω p k j ]

= n 1 p 1 c ? k i t + n 2 p 2 p 1 ? 1 t + n 2 p 2 c ? k i t ? n 2 p 2 ? q = 1 m r q r p c p 1 ? k i t 2 + n 3 p 3 p 1 ? 1 t ? n 3 p 3 ? q = 1 m r q r p p 1 ? 1 t ? ? + n 3 p 3 ? q = 1 m r q ? r p q = 1 m r q + n 3 p 3 ? q = 1 m r q ? r p c r p k i t + n 3 p 3 ? ( q = 1 m r q ? r p ) ? q = 1 m r q p 1 r p t ( p 1 r p t ? q = 1 m r q ) ? ? + n 3 p 3 ? ( q = 1 m r q ? r p ) ? ( q = 1 m r q ) 2 c p 1 r p t ( p 1 r p t ? q = 1 m r q ) ? k i t + 2 n 4 p 4 c ? k i t = n 1 p 1 c ? k i t + n 2 p 2 c ? k i t + n 3 p 3 ? q = 1 m r q ? r p c r p k i t + 2 n 4 p 4 c ? k i t ? ? + n 2 p 2 p 1 ? 1 t + n 3 p 3 p 1 ? 1 t ? n 3 p 3 ? q = 1 m r q r p p 1 ? 1 t (2.20)

a = n 1 p 1 c + n 2 p 2 c + q = 1 m r q ? r p c r p + 2 n 4 p 4 c b = n 2 p 2 p 1 + n 3 p 3 p 1 ? n 3 p 3 ? q = 1 m r q r p p 1

將a和b代入(2.20)式,并化簡可以得到

? k i ? t = a ? k i t + b ? 1 t

由初始條件為 k i ( t i ) = n 1 可得

k i ( t ) = t i t a ? k i t + b ? 1 t d t = ( n 1 + b a ) ( t t i ) a ? a b

由于服從 [ 0 , M + t ] 的均勻分布,則 P i ( t i ) = 1 M + t

F ( k ) = P ( k i ( t ) < k ) = P ( t i > ( k + b a ) ? 1 a ( n 1 + b a ) 1 a t ) = 1 ? t M + t ( s + b a ) ? ( 1 a + 1 ) ( n 1 + b a ) 1 a

則度的密度分布函數 P ( k ) = ? F ( k ) ? k = t a ( M + t ) ( n 1 + b a ) 1 a ( k + b a ) ? ( 1 a + 1 )

由此可知該網絡模型的度服從冪律分布,為無標度網絡,其中

1 a = 1 n 1 p 1 c + n 2 p 2 c + q = 1 m r q ? r p c r p + 2 n 4 p 4 c = 2 ( n 1 p 1 + n 2 p 2 ? n 3 p 3 + 2 n 4 p 4 ) r p n 1 p 1 r p + n 2 p 2 r p + q = 1 m r q ? r p + 2 n 4 p 4 r p r p ( p = 1 , 2 , ? , m ) 的取值影響著冪指數的值,當 r p ( p = 1 , 2 , ? , m ) 取值均相同時,冪指數的值介于1~2之間。

3. 仿真模擬

我們運用MATLAB進行仿真模擬,繪制出有著 m = 5 個獨立局域網, p 1 = 0.3 p 2 = 0.4 p 3 = 0.2 p 4 = 0.1 n 1 = 3 n 2 = 5 n 3 = 4 n 4 = 3 t = 2000 ,多局域世界網絡模型中每個局域網中節點數邊數相同為 n 0 = 8 , e 0 = 15 改進多局域世界網絡模型中各局域網的節點數、邊數、競爭系數定義為 m 1 = 10 , e 1 = 19 m 2 = 9 , e 2 = 18 m 3 = 8 , e 3 = 15 m 4 = 7 , e 4 = 14 m 5 = 6 , e 5 = 13 r 1 = 1 r 2 = 2 r 3 = 3 r 4 = 4 r 5 = 5 ,繪制出兩個模型的網絡的度在對數坐標系中的分布情況,如圖1圖2所示,比較圖1圖2可以看出多局域世界網絡模型的度分布比較均勻,網絡中節點度的最大度僅為10,最大度與最小度的差距較小,而在改進的多局域世界網絡模型中,度分布比較分散,最大度接近100。相比較而言,改進的多局域世界網絡模型更加貼合現實生活中的網絡。

Figure 1. MLW degree distribution

圖1. 多局域世界網絡模型度分布

Figure 2. IMLW degree distribution

圖2. 改進多局域世界網絡度分布

4. 小結

本文在多局域世界演化模型的基礎之上,將局域網之間的不等性、競爭性引入到模型之中,建立了改進的多局域世界網絡模型,并運用平均場理論對改進多局域世界網絡模型的度分布進行求解,改進模型度服從冪律分布,冪指數的大小與每個局域網的競爭系數有很大關系。最后進行仿真模擬,改進模型網絡度的分布與原模型度分布相比度的分布更不均勻,更加貼合現實生活中的網絡,實用性更強。

彩3d复式玩法介绍

文章引用:
張璐璐. 一種改進的多局域世界網絡模型[J]. 運籌與模糊學, 2019, 9(4): 285-291. https://doi.org/10.12677/ORF.2019.94033

參考文獻

[1] Chen, G., Fan, Z.P., Li, X. (2005) Modeling the complex Internet topology. In: Vattay, G. and Ocarev, L.K, Eds., Complex Dynamics in Communication Network, Springer-Verlag, Berlin.
[2] 田思, 李慧嘉, 趙岳. 一種新型多局域世界網絡模型分析[J]. 計算機應用研究, 2013, 30(3): 869-872.
[3] 李曉. 基于雙向擇優機制的多局域加權網絡研究[D]: [碩士學位論文]. 濟南: 山東師范大學, 2012.
[4] 汪小帆. 復雜網絡理論及其應用[M]. 北京: 清華大學出版社, 2005.