小世界網(wǎng)絡(luò)模型分析和算法模擬

葛偉倫，房丙午

當(dāng)前對(duì)復(fù)雜網(wǎng)絡(luò)的研究引起了各國(guó)學(xué)者的高度關(guān)注和重視，復(fù)雜網(wǎng)絡(luò)是對(duì)現(xiàn)實(shí)世界復(fù)雜系統(tǒng)的抽象和概括，該網(wǎng)絡(luò)是由大量節(jié)點(diǎn)相互連接而成，網(wǎng)絡(luò)規(guī)模大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜且動(dòng)態(tài)變化.現(xiàn)實(shí)生活中的人際關(guān)系網(wǎng)、因特網(wǎng)、萬(wàn)維網(wǎng)、電子郵件網(wǎng)、食物鏈網(wǎng)等都屬于復(fù)雜網(wǎng)絡(luò).把各種類型的復(fù)雜網(wǎng)絡(luò)抽象成具體模型是研究復(fù)雜網(wǎng)絡(luò)最好的方式，近年提出的小世界網(wǎng)絡(luò)模型能真實(shí)深刻地揭示復(fù)雜網(wǎng)絡(luò)背后隱藏的客觀規(guī)律和屬性特征［1-2］.

1　小世界網(wǎng)絡(luò)模型

1998年Watts、Strogat提出的WS小世界網(wǎng)絡(luò)模型和Newman、Watts提出的改進(jìn)NW小世界網(wǎng)絡(luò)模型能真實(shí)反映復(fù)雜網(wǎng)絡(luò)的特征與規(guī)律［3-4］.WS小世界網(wǎng)絡(luò)模型建模過程：從某個(gè)含有N個(gè)節(jié)點(diǎn)的規(guī)則環(huán)狀網(wǎng)開始，m為節(jié)點(diǎn)的度且為偶數(shù)，每個(gè)節(jié)點(diǎn)都與它左右鄰接的各m/2個(gè)節(jié)點(diǎn)相連，然后進(jìn)行隨機(jī)化重連，將邊的一個(gè)端點(diǎn)保持不變，另一個(gè)端點(diǎn)隨機(jī)選擇規(guī)則網(wǎng)中的另一個(gè)節(jié)點(diǎn)進(jìn)行連接，滿足節(jié)點(diǎn)之間只有一條邊，并去除自連接.在WS小世界網(wǎng)絡(luò)模型中，p=0對(duì)應(yīng)于完全規(guī)則網(wǎng)，p=1則對(duì)應(yīng)于完全隨機(jī)網(wǎng)，通過調(diào)節(jié)p的值可以控制從完全規(guī)則網(wǎng)到完全隨機(jī)網(wǎng)的變化，如圖1所示.

圖1　隨機(jī)化重連

Newman和Watts進(jìn)一步提出了NW小世界網(wǎng)絡(luò)模型，該模型用隨機(jī)化加邊取代WS模型的隨機(jī)化重連，避免了構(gòu)造過程孤立節(jié)點(diǎn)的產(chǎn)生.NW小世界網(wǎng)絡(luò)模型建模過程：從某個(gè)含有N個(gè)節(jié)點(diǎn)的規(guī)則環(huán)狀網(wǎng)開始，m為節(jié)點(diǎn)的度且為偶數(shù)，每個(gè)節(jié)點(diǎn)都與它左右鄰接的各m/2個(gè)節(jié)點(diǎn)相連，然后進(jìn)行隨機(jī)化加邊，以概率 p在隨機(jī)選取的一對(duì)節(jié)點(diǎn)之間加上一條邊，滿足節(jié)點(diǎn)之間只有一條邊，并去除自連接.NW小世界網(wǎng)絡(luò)模型中，p=0對(duì)應(yīng)于完全規(guī)則網(wǎng)，p=1是規(guī)則網(wǎng)和隨機(jī)網(wǎng)的疊加，如圖2所示.

圖2　隨機(jī)化加邊

2　小世界網(wǎng)絡(luò)特征統(tǒng)計(jì)量分析［5-6］

2.1　最短路徑平均長(zhǎng)度

最短路徑平均長(zhǎng)度是小世界網(wǎng)絡(luò)重要的特征值，這里最短路徑指的是從一節(jié)點(diǎn)到另一節(jié)點(diǎn)經(jīng)過的邊的最小數(shù)目，整個(gè)網(wǎng)絡(luò)最短路徑平均長(zhǎng)度為所有節(jié)點(diǎn)最短路徑長(zhǎng)度的平均值.設(shè)N為節(jié)點(diǎn)數(shù)，di,j為兩個(gè)不同節(jié)點(diǎn)間的最短路徑長(zhǎng)度，最短路徑平均長(zhǎng)度Lavg的計(jì)算公式為：

2.2　集聚系數(shù)

集聚系數(shù)是反映小世界網(wǎng)絡(luò)集團(tuán)化程度的特征量，集團(tuán)中的成員相互緊密聯(lián)系，依賴性強(qiáng).節(jié)點(diǎn)i的集聚系數(shù)能表示網(wǎng)絡(luò)中與該節(jié)點(diǎn)直接相連接的其他節(jié)點(diǎn)之間的連接緊密度，ki表示與節(jié)點(diǎn)i直接連接的節(jié)點(diǎn)數(shù)，ei表示與節(jié)點(diǎn)i相連接的節(jié)點(diǎn)間實(shí)際存在的連接邊，ki(ki-1)/2表達(dá)式為ki個(gè)節(jié)點(diǎn)間理論上存在的最大連接邊，則節(jié)點(diǎn)i的集聚系數(shù)Ci表示為：

則整個(gè)網(wǎng)絡(luò)的集聚系數(shù)C定義為所有節(jié)點(diǎn)集聚系數(shù)的平均值，表示為：

3　小世界網(wǎng)絡(luò)模型的算法模擬和分析［7-8］

3.1　算法描述

根據(jù)上文分析，以WS小世界網(wǎng)絡(luò)模型為例設(shè)計(jì)算法實(shí)現(xiàn)模擬，首先假設(shè)一個(gè)環(huán)狀規(guī)則網(wǎng)絡(luò)有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)與最近鄰的k個(gè)節(jié)點(diǎn)相連，本次模擬網(wǎng)絡(luò)規(guī)模較小，設(shè)置N=20，k=4，不改變邊和節(jié)點(diǎn)的數(shù)目.重連概率用隨機(jī)函數(shù)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)θ來(lái)表示，θ=rand（），假設(shè)隨機(jī)化重連的概率為0.1，當(dāng)產(chǎn)生的隨機(jī)數(shù)θ＜0.1就進(jìn)行重連，否則不重連；重連過程中隨機(jī)選擇重連對(duì)端節(jié)點(diǎn)，通過隨機(jī)函數(shù)產(chǎn)生一個(gè)在1到N范圍內(nèi)的隨機(jī)整數(shù)m，表達(dá)式為1+int（rand（）*（N-1）），m 代表隨機(jī)重連的節(jié)點(diǎn)編號(hào)，若m恰好等于原節(jié)點(diǎn)編號(hào)，就重新產(chǎn)生一次，即再產(chǎn)生一個(gè)隨機(jī)數(shù).算法如下.

首先，隨機(jī)選擇一個(gè)節(jié)點(diǎn)，當(dāng)θ＜0.1時(shí)按順時(shí)針方向把連接它和它最近的那個(gè)節(jié)點(diǎn)的邊重新連接到環(huán)狀網(wǎng)上的其他對(duì)端節(jié)點(diǎn)，對(duì)端節(jié)點(diǎn)編號(hào)隨機(jī)產(chǎn)生，θ＞=0.1不進(jìn)行重連.

然后，同樣按順時(shí)針方向把連接它和它第二近的那個(gè)點(diǎn)的邊以隨機(jī)概率θ是否大于0.1判斷是否重新連接到環(huán)狀網(wǎng)上的其他對(duì)端節(jié)點(diǎn)，重復(fù)此過程直到此節(jié)點(diǎn)的所有邊都按隨機(jī)概率θ大小重新遍歷一遍.

最后，輪換到下一個(gè)節(jié)點(diǎn)重復(fù)（1）和（2）步驟，直至N個(gè)節(jié)點(diǎn)都按相同方式遍歷所有節(jié)點(diǎn)結(jié)束.

3.2　算法代碼實(shí)現(xiàn)

（1）通過以下算法代碼生成規(guī)則環(huán)狀網(wǎng)，如圖3所示，矩陣中“1”表示有邊連接兩個(gè)不同節(jié)點(diǎn)，”0”表示無(wú)邊連接節(jié)點(diǎn).

//以下代碼實(shí)現(xiàn)規(guī)則邊

//以下代碼實(shí)現(xiàn)規(guī)則矩陣

圖3　N=20，k=4規(guī)則環(huán)狀網(wǎng)

（2）通過以下算法代碼使用隨機(jī)化重連生成小世界網(wǎng)絡(luò)模型，如圖4所示.觀察矩陣，可看出其中一些邊在滿足概率p條件下已經(jīng)重新連接，不過因?yàn)橹剡B的概率（p＜0.1）不大，所以很多邊保持不變，這使得每個(gè)節(jié)點(diǎn)與其周圍鄰居節(jié)點(diǎn)關(guān)系較規(guī)則網(wǎng)絡(luò)變化不大，聚類系數(shù)仍然保持在一個(gè)較大的數(shù)值，但因?yàn)樯闪艘恍╅L(zhǎng)路徑加強(qiáng)了遠(yuǎn)距離節(jié)點(diǎn)的連接，從而使得整個(gè)小世界網(wǎng)絡(luò)最短路徑平均長(zhǎng)度明顯減小.

圖4　N=20小世界網(wǎng)絡(luò)模型

（3）通過以下算法代碼統(tǒng)計(jì)小世界網(wǎng)絡(luò)模型最短路徑平均長(zhǎng)度.

（4）通過以下算法代碼統(tǒng)計(jì)小世界網(wǎng)絡(luò)模型聚類系數(shù)值.

3.3　統(tǒng)計(jì)數(shù)據(jù)分析

本次網(wǎng)絡(luò)規(guī)模較大，取節(jié)點(diǎn)數(shù)N=1000，每個(gè)節(jié)點(diǎn)的度k=20，依據(jù)上面統(tǒng)計(jì)特征值代碼計(jì)算規(guī)則環(huán)狀網(wǎng)的最短路徑平均長(zhǎng)度L=50.45045，聚類系數(shù)C=0.6666667.現(xiàn)在以15個(gè)不同的概率P從小到大進(jìn)行隨機(jī)化重連構(gòu)建WS小世界網(wǎng)絡(luò)模型，依據(jù)上文算法計(jì)算最短路徑平均長(zhǎng)度和聚類系數(shù)值，對(duì)每次取的概率P模擬運(yùn)算20組數(shù)據(jù)求出統(tǒng)計(jì)量平均值，概率P、平均聚類系數(shù)avsc、最短路徑平均長(zhǎng)度avsl如表1所示.可以看出隨著隨機(jī)化重連概率P的增加，連接節(jié)點(diǎn)的長(zhǎng)路徑增多，使最短路徑平均長(zhǎng)度從44.83816急劇減小4.413377，但聚類系數(shù)緩慢變小，變化幅度從0.6663419緩慢減小到0.4872532，完全符合復(fù)雜網(wǎng)絡(luò)的小世界特性和高聚類特性.

對(duì)最短路徑平均長(zhǎng)度和聚類系數(shù)進(jìn)行歸一化處理，獲得的統(tǒng)計(jì)結(jié)果如圖5所示，圖中L（P）和C（P）表示以不同的概率 p得到的小世界網(wǎng)絡(luò)平均最短路徑長(zhǎng)度和聚類系數(shù)，L（0）和C（0）表示規(guī)則環(huán)狀網(wǎng)的最短路徑長(zhǎng)度和聚類系數(shù)，用L（0）和C（0）對(duì)L（P）和C（P）進(jìn)行歸一化處理.展示了最短路徑長(zhǎng)度和聚類系數(shù)隨概率P變化的曲線圖.可以得出這樣結(jié)論：在概率P處于0.01～0.02附近，最短路徑平均長(zhǎng)度已經(jīng)很小，但聚類系數(shù)仍然很大，符合小世界網(wǎng)絡(luò)特征，現(xiàn)實(shí)世界中很多復(fù)雜網(wǎng)絡(luò)系統(tǒng)從誕生、形成、發(fā)展和消失和算法模擬生成的小世界網(wǎng)絡(luò)特征和規(guī)律完全吻合［9］.

表1　P和avsc、avsl的平均值

圖5　最短路徑平均長(zhǎng)度和聚類系數(shù)隨P變化情況

4　結(jié)語(yǔ)

對(duì)WS和NW小世界網(wǎng)絡(luò)模型建模過程進(jìn)行分析，并闡述了最短路徑平均長(zhǎng)度和集聚系數(shù)特征值的意義，基于一個(gè)規(guī)則環(huán)狀網(wǎng)設(shè)計(jì)算法和代碼模擬了小世界網(wǎng)絡(luò)模型的形成，并解決了重連概率θ和對(duì)端節(jié)點(diǎn)選擇的隨機(jī)產(chǎn)生問題；并設(shè)計(jì)和運(yùn)行代碼獲得最短路徑平均長(zhǎng)度和集聚系數(shù)特征值的統(tǒng)計(jì)數(shù)據(jù)，驗(yàn)證和分析了小世界網(wǎng)絡(luò)的內(nèi)在特性，使模擬大規(guī)模的小世界網(wǎng)絡(luò)成為可能.

參考文獻(xiàn)：

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

［2］周濤，張子柯，等.復(fù)雜網(wǎng)絡(luò)研究的機(jī)遇和挑戰(zhàn)［J］.電子科技大學(xué)學(xué)報(bào)，2014，43（1）：1-5

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

［4］郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò)［M］.上海：上?？萍冀逃霭嫔?，2010.

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

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

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

［8］楊曉光，朱保平.基于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法［J］.南京理工大學(xué)學(xué)報(bào)，2016，40（3）：267-271.

［9］肖維民，張賽.k錯(cuò)線性復(fù)雜度的分布研究［J］.吉林師范大學(xué)學(xué)報(bào)，2016（2）.