葛偉倫

摘要：該文首先闡述了復(fù)雜網(wǎng)絡(luò)最短路徑平均距離、度值和集聚系數(shù)屬性意義，并推導(dǎo)出相應(yīng)的計算公式。概況了隨機(jī)化加邊優(yōu)于隨機(jī)化重連構(gòu)造小世界網(wǎng)絡(luò)模型的合理性。通過MATLAB設(shè)計仿真實驗，通過得到的統(tǒng)計圖分析了小世界網(wǎng)絡(luò)的特征和變化規(guī)律，為理解實際網(wǎng)絡(luò)的運(yùn)行機(jī)理及監(jiān)督、維護(hù)和控制網(wǎng)絡(luò)運(yùn)行提供參考數(shù)據(jù)。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；度；集聚系數(shù)；最短路徑平均距離；MATLAB

中圖分類號： TP393 文獻(xiàn)標(biāo)志碼：A 文章編號：1009-3044（2016）16-0052-02

當(dāng)前對復(fù)雜網(wǎng)絡(luò)的研究引起了相關(guān)領(lǐng)域?qū)W者和專家的高度關(guān)注和重視，該網(wǎng)絡(luò)是由大量節(jié)點(diǎn)相互連接而成，網(wǎng)絡(luò)規(guī)模大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜且動態(tài)變化。現(xiàn)實生活中的人際關(guān)系網(wǎng)、組織結(jié)構(gòu)網(wǎng)絡(luò)、車輛交通網(wǎng)絡(luò)、計算機(jī)網(wǎng)絡(luò)、生物學(xué)中的神經(jīng)網(wǎng)絡(luò)、細(xì)胞網(wǎng)絡(luò)等都屬于復(fù)雜網(wǎng)絡(luò)，人、車、細(xì)胞、計算機(jī)、神經(jīng)元可抽象成點(diǎn)，點(diǎn)之間的依賴關(guān)系、共存性、相互作用、連接性可抽象成邊。把各種類型的復(fù)雜網(wǎng)絡(luò)抽象成具體模型是探索和研究復(fù)雜網(wǎng)絡(luò)最好的方式，近年來提出的小世界網(wǎng)絡(luò)模型深刻揭示了復(fù)雜網(wǎng)絡(luò)背后隱藏的客觀規(guī)律和屬性特征。

1 復(fù)雜網(wǎng)絡(luò)統(tǒng)計量屬性[1-2]

1.1 最短路徑平均距離

復(fù)雜網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)的最短路徑距離Si，j指從節(jié)點(diǎn)i到j(luò)的多條冗余路徑中選擇一條包含邊數(shù)目最少的路徑，即最短路徑上邊的數(shù)目稱為i到j(luò)的最短距離。整個網(wǎng)絡(luò)最短路徑平均距離為所有節(jié)點(diǎn)對最短路徑距離的平均值，設(shè)N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目，則網(wǎng)絡(luò)最短路徑平均距離Savg用公式表示：

2 網(wǎng)絡(luò)模型[3]

對網(wǎng)絡(luò)的探索經(jīng)歷了從規(guī)則網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)到復(fù)雜網(wǎng)絡(luò)模型的發(fā)展歷程。規(guī)則網(wǎng)絡(luò)模型節(jié)點(diǎn)之間按照有規(guī)律的方式連接，形成規(guī)則圖，具有對稱性，任一節(jié)點(diǎn)的相鄰邊數(shù)都相同，規(guī)則網(wǎng)絡(luò)是一種理想和假設(shè)的網(wǎng)絡(luò)構(gòu)造，不能表示真實動態(tài)的網(wǎng)絡(luò)。隨機(jī)網(wǎng)絡(luò)模型是節(jié)點(diǎn)之間以完全隨機(jī)的方式進(jìn)行連接，形成隨機(jī)圖，是復(fù)雜網(wǎng)絡(luò)的一個極端，是由匈牙利著名的兩位數(shù)學(xué)家保羅·愛爾德和阿爾弗雷德·萊利在1960年提出，此模型一直被認(rèn)為是刻畫現(xiàn)實世界網(wǎng)絡(luò)最形象的模型。但在近年來的研究中測得的實驗數(shù)據(jù)與隨機(jī)圖模型統(tǒng)計的數(shù)據(jù)背離較大，并不能真實代表復(fù)雜網(wǎng)絡(luò)。直到1998年Watts和Strogatz提出的WS小世界網(wǎng)絡(luò)模型和后來Newman和Watts提出的改進(jìn)NW小世界網(wǎng)絡(luò)模型才真實反映復(fù)雜網(wǎng)絡(luò)的特征和規(guī)律。

2.1 WS和NW小世界模型構(gòu)造過程[4-5]

從一個含有N個節(jié)點(diǎn)的規(guī)則環(huán)狀網(wǎng)絡(luò)開始，每個節(jié)點(diǎn)都與它最近鄰的左右各m/2個結(jié)點(diǎn)連接，連出m條邊，m為偶數(shù)，m也是節(jié)點(diǎn)的度數(shù)。

1）隨機(jī)化重連：以概率p，一般取p=0.1隨機(jī)地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的一個節(jié)點(diǎn)保持不變，對端節(jié)點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的另一個節(jié)點(diǎn)。并規(guī)定任意兩個節(jié)點(diǎn)之間至多只能有一條邊，并去除自連接，構(gòu)造出WS小世界網(wǎng)絡(luò)模型。改變p值，即可實現(xiàn)從規(guī)則網(wǎng)絡(luò)（p=0）向隨機(jī)網(wǎng)絡(luò)（p=1）轉(zhuǎn)換。

2）隨機(jī)化加邊：以概率p，一般取p=0.1在隨機(jī)選取的一對節(jié)點(diǎn)之間加上一條邊。并規(guī)定任意兩個節(jié)點(diǎn)之間至多只能有一條邊，并去除自連接，構(gòu)造出NW小世界網(wǎng)絡(luò)模型。改變p值可以實現(xiàn)從規(guī)則網(wǎng)絡(luò)（p=0）向隨機(jī)網(wǎng)絡(luò)（p=1）轉(zhuǎn)換。

2.2 小世界模型構(gòu)造過程分析

NW模型是通過用“隨機(jī)化加邊”取代WS小世界網(wǎng)絡(luò)模型構(gòu)造中的“隨機(jī)化重連”，由于WS小世界模型構(gòu)造中的隨機(jī)化重連會破壞原網(wǎng)絡(luò)的連通性和產(chǎn)生孤立節(jié)點(diǎn)，所以N小世界模型更符合復(fù)雜網(wǎng)絡(luò)真實情況。

小世界網(wǎng)絡(luò)模型是處于0

3 仿真實驗設(shè)計和分析[6]

3.1 實驗設(shè)計

本文對小世界網(wǎng)絡(luò)選用隨機(jī)化加邊構(gòu)造算法來實現(xiàn)，使用MATLAB進(jìn)行仿真實驗，驗證小世界網(wǎng)絡(luò)的統(tǒng)計量屬性及變化規(guī)律。用概率p=0.1來決定一對節(jié)點(diǎn)是否加邊來構(gòu)造規(guī)則網(wǎng)絡(luò)向NW小世界網(wǎng)絡(luò)的轉(zhuǎn)換，用隨機(jī)函

數(shù)rand（）來產(chǎn)生一個隨機(jī)值，當(dāng)≤0.1，兩個節(jié)點(diǎn)隨機(jī)加邊，對兩個節(jié)點(diǎn)的選擇可由int（Nrand（）+1）來決定，記為μ，表示節(jié)點(diǎn)編號，1≤μ≤N，int為向下取整函數(shù)，運(yùn)算兩次隨機(jī)產(chǎn)生一對節(jié)點(diǎn)編號，按產(chǎn)生的編號連接實現(xiàn)隨機(jī)化加邊。實驗數(shù)據(jù)樣本設(shè)置為N=5000，邊數(shù)K=10000。分別對NW小世界網(wǎng)絡(luò)模型的平均路徑長度、度值和集聚系數(shù)進(jìn)行統(tǒng)計分析，產(chǎn)生的統(tǒng)計圖如下所示。

3.2 WS模型度分布分析

如圖1所示，對于0

3.3 WS模型最短路徑距離分析

如圖2所示，任意兩個節(jié)點(diǎn)之間的最短距離不超過6，距離為7的節(jié)點(diǎn)對數(shù)為0，符合六度理論。由實驗統(tǒng)計得到的網(wǎng)絡(luò)平均最短路徑距離約為2.021，較小。由于對于0

3.4 WS模型集聚系數(shù)分析

如圖3所示，各個節(jié)點(diǎn)的集聚系數(shù)較大但變化幅度不大，由實驗統(tǒng)計得到的集聚系數(shù)約為0.562。因為對于p=0的規(guī)則網(wǎng)絡(luò)，集聚系數(shù)R=3（K-2）/4（K-1），對于0

4 結(jié)束語

本文對復(fù)雜網(wǎng)絡(luò)的幾個重要屬性進(jìn)行歸納，并推導(dǎo)出屬性值的計算公式。分析了能代表復(fù)雜網(wǎng)絡(luò)的WS和NW小世界網(wǎng)絡(luò)模型構(gòu)造過程。通過MATLAB設(shè)計了仿真實驗，基于統(tǒng)計數(shù)據(jù)和統(tǒng)計圖剖析了復(fù)雜網(wǎng)絡(luò)屬性值的特征和隱藏的變化規(guī)律，為我們認(rèn)識實際的網(wǎng)絡(luò)及監(jiān)控、維護(hù)、管理和控制網(wǎng)絡(luò)正常運(yùn)行提供重要的參考數(shù)據(jù)。

參考文獻(xiàn)：

[1] 王小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[2] 程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（1）：57-66.

[3] 郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò)[M].上海：上海科技教育出版社，2010.

[4] 劉常昱，胡曉峰，司光亞，等.基于小世界網(wǎng)絡(luò)的輿論傳播模型研究 [J].系統(tǒng)仿真學(xué)報，2006，18（12）：3608-3611.

[5] 李果，高建民，高智勇，等.基于小世界網(wǎng)絡(luò)的復(fù)雜系統(tǒng)故障傳播模型[J].西安交通大學(xué)學(xué)報， 2007，41（3）：334-338.

[6] 王波，王萬良.WS和NW兩種小世界網(wǎng)絡(luò)模型的建模及仿真研究[J].浙江工業(yè)大學(xué)學(xué)報，2009，37（2）：179-188.