一種新型直聯(lián)小世界網(wǎng)絡(luò)模型

林 濤, 高建華, 伏 雪, 馬 燕, 林 艷

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234; 2.奧克蘭大學(xué) 信息系統(tǒng)系,奧克蘭 92019; 3.賓夕法尼亞州立大學(xué) 信息科學(xué)與技術(shù)學(xué)院,賓夕法尼亞州 16802)

?

一種新型直聯(lián)小世界網(wǎng)絡(luò)模型

林 濤1,3, 高建華1, 伏 雪1, 馬 燕1, 林 艷2

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234; 2.奧克蘭大學(xué) 信息系統(tǒng)系,奧克蘭 92019; 3.賓夕法尼亞州立大學(xué) 信息科學(xué)與技術(shù)學(xué)院,賓夕法尼亞州 16802)

現(xiàn)有計(jì)算機(jī)網(wǎng)絡(luò)存在一定程度冗余和效率低等問(wèn)題,提出一種新的直聯(lián)小世界(DSW)網(wǎng)絡(luò)模型以優(yōu)化網(wǎng)絡(luò).首先將節(jié)點(diǎn)構(gòu)成正則網(wǎng)絡(luò),然后取任意節(jié)點(diǎn)重畫,通過(guò)迭代生成DSW網(wǎng)絡(luò).在該模型下,平均距離和聚集系數(shù)與原網(wǎng)絡(luò)相同,但是網(wǎng)絡(luò)的跳數(shù)等性能有所改變.實(shí)驗(yàn)證明,DSW網(wǎng)絡(luò)的度數(shù)、平均度中心性以及平均最近距離中心性均低于原有小世界(SW)網(wǎng)絡(luò).表明DSW網(wǎng)絡(luò)兩節(jié)點(diǎn)的緊密程度高于SW網(wǎng)絡(luò).該模型不僅可以有效應(yīng)用于社區(qū)信息的傳播,還可以用于流行病傳播的研究.

小世界網(wǎng)絡(luò); 復(fù)雜網(wǎng)絡(luò); 節(jié)點(diǎn)中心性; 網(wǎng)絡(luò)可靠性; 網(wǎng)絡(luò)優(yōu)化

0 引 言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)明與大規(guī)模應(yīng)用,人們之間的距離越來(lái)越近.同時(shí),另一方面,現(xiàn)有的計(jì)算機(jī)網(wǎng)絡(luò)存在一定程度冗余和效率低等問(wèn)題.因此,引入小世界(SW)網(wǎng)絡(luò)為模型,以嘗試優(yōu)化現(xiàn)有的計(jì)算機(jī)網(wǎng)絡(luò),在網(wǎng)絡(luò)信息傳遞方面尤其重要[1].

在網(wǎng)絡(luò)理論中,SW網(wǎng)絡(luò)是一類特殊的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu),在這種網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)并不互相連接,但絕大部分節(jié)點(diǎn)經(jīng)過(guò)少數(shù)幾步就可到達(dá)[2].

本文作者構(gòu)造一種新型SW模型:直聯(lián)小世界網(wǎng)絡(luò)(DSW).在該模型下,平均距離和聚集系數(shù)與原網(wǎng)絡(luò)相同,但是網(wǎng)絡(luò)的跳數(shù)等性能有所改變.

本文以實(shí)例說(shuō)明DSW網(wǎng)絡(luò)在現(xiàn)實(shí)生活中有廣泛應(yīng)用.不僅可以有效應(yīng)用于社區(qū)信息的傳播,而且可以用于流行病傳播的研究.一方面,可以通過(guò)人為構(gòu)建DSW網(wǎng)絡(luò),在不顯著增加成本的前提下,快速傳播社區(qū)信息.另一方面,可以通過(guò)人為破壞DSW網(wǎng)絡(luò)迅速降低流行病的傳播.

章節(jié)安排如下:第1部分介紹SW網(wǎng)絡(luò)的基本概念.第2部分,論述DSW網(wǎng)絡(luò)的算法和實(shí)例.第3部分,實(shí)驗(yàn)以及結(jié)果分析.最后是結(jié)語(yǔ)與展望.

1 SW網(wǎng)絡(luò)介紹

這個(gè)世界能有多小？數(shù)千年前的哲學(xué)家就在思考這個(gè)問(wèn)題.20世紀(jì)末,隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)明與大規(guī)模應(yīng)用,全球信息傳播方式發(fā)生翻天覆地變化.同時(shí),由于計(jì)算機(jī)網(wǎng)絡(luò)的冗余以及效率低(比如:使用大部分的即時(shí)聊天軟件時(shí),即使兩個(gè)人在同一幢大樓,聊天信息一般也需要經(jīng)過(guò)ISP服務(wù)器),因而需要優(yōu)化網(wǎng)絡(luò)[3].

優(yōu)化網(wǎng)絡(luò)的一個(gè)思路是減少路由次數(shù).路由(routing)就是通過(guò)互聯(lián)網(wǎng)把信息從源地址傳輸?shù)侥康牡刂穂4].路由發(fā)生在OSI網(wǎng)絡(luò)參考模型中的第三層即網(wǎng)絡(luò)層,已經(jīng)成為互聯(lián)網(wǎng)上尋找路徑的最主要方法[5].

計(jì)算機(jī)網(wǎng)絡(luò)是利用通信設(shè)備和線路將地理位置不同的、功能獨(dú)立的多個(gè)計(jì)算機(jī)系統(tǒng)連接起來(lái),以功能完善的網(wǎng)絡(luò)軟件實(shí)現(xiàn)網(wǎng)絡(luò)的硬件、軟件及資源共享和信息傳遞的系統(tǒng).隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展,出現(xiàn)了很多網(wǎng)絡(luò)模型,用于解決網(wǎng)絡(luò)中存在的效率與資源的關(guān)系,SW網(wǎng)絡(luò)就是一種最新出現(xiàn)的重要網(wǎng)絡(luò)模型[6].

SW是一個(gè)由大量頂點(diǎn)構(gòu)成的圖,其中任意兩點(diǎn)之間的平均路徑長(zhǎng)度比頂點(diǎn)數(shù)量小得多.最早起源于人文科學(xué),20世紀(jì)60年代,美國(guó)哈佛大學(xué)社會(huì)心理學(xué)家斯坦利·米爾格倫實(shí)驗(yàn)發(fā)現(xiàn)世界上任意兩個(gè)人都可以經(jīng)過(guò)最多5個(gè)人而聯(lián)系,即所謂的“六度分割理論”.除了社會(huì)人際網(wǎng)絡(luò)以外,SW的例子在生物學(xué)、物理學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域均有出現(xiàn)[7].許多圖可以用SW作為模型[8].萬(wàn)維網(wǎng)、公路交通網(wǎng)、腦神經(jīng)網(wǎng)絡(luò)和基因網(wǎng)絡(luò)都呈現(xiàn)SW的特征[9].

在計(jì)算機(jī)科學(xué)中,SW最早是由鄧肯·瓦茨(Duncan Watts)和斯蒂文·斯特羅加茨(Steven Strogatz)在1998年引進(jìn)的.將高聚集系數(shù)和低平均路徑長(zhǎng)度作為特征,一般就稱作瓦茲-史楚蓋茲模型(WS模型)[10],這也是最典型的SW的模型.

2 DSW網(wǎng)絡(luò)

本節(jié)提出DSW網(wǎng)絡(luò)的算法和實(shí)例.

2.1 算 法

DSW算法如圖1所示.

該算法的核心是首先將節(jié)點(diǎn)構(gòu)成正則網(wǎng)絡(luò)(第1行),然后取任意節(jié)點(diǎn)重畫(第2、3行),最后迭代k次(第4行).

2.2 DSW實(shí)例

本小節(jié)分別在社區(qū)網(wǎng)絡(luò)和疾病傳播方面給出DSW的兩個(gè)實(shí)例.

2.2.1 社區(qū)網(wǎng)絡(luò)分析

平均距離也稱為特征路徑長(zhǎng)度或平均最短路徑長(zhǎng)度,指的是一個(gè)網(wǎng)絡(luò)中兩點(diǎn)之間最短路徑長(zhǎng)度(或稱距離)的平均值.從一個(gè)節(jié)點(diǎn)Si出發(fā),經(jīng)過(guò)與它相連的節(jié)點(diǎn),逐步“走”到另一個(gè)節(jié)點(diǎn)Sj所經(jīng)過(guò)的路途,稱為兩點(diǎn)間的路徑.其中最短的路徑也稱為兩點(diǎn)間的距離,記作dist(i,j)為:

DSW網(wǎng)絡(luò)可以有效地應(yīng)用于社區(qū)信息的擴(kuò)散.對(duì)于最簡(jiǎn)單的社區(qū),每個(gè)社區(qū)由一個(gè)頂點(diǎn)表示,共有4個(gè)頂點(diǎn).首先,社區(qū)通過(guò)如下方式連接,構(gòu)成正則圖,如圖2所示.

可以求得,其平均距離為1.5,聚集系數(shù)為0.66.

若隨機(jī)將處于對(duì)角線上的兩個(gè)社區(qū)相連,如圖3所示.

則重畫后的社區(qū)的平均距離為1,聚集系數(shù)為0.83.

事實(shí)上,現(xiàn)實(shí)社會(huì)中的隨機(jī)網(wǎng)絡(luò),如圖4所示.

圖2 正則社區(qū)網(wǎng)絡(luò)

圖3 隨機(jī)的社區(qū)網(wǎng)絡(luò)

圖4 現(xiàn)實(shí)社區(qū)網(wǎng)絡(luò)

其平均距離為1,聚集系數(shù)為1.

分析相關(guān)數(shù)據(jù),如表1所列.

表1 各種社區(qū)網(wǎng)絡(luò)參數(shù)比較

由此例可知,對(duì)于一個(gè)存在幾個(gè)社區(qū)的網(wǎng)絡(luò),通過(guò)DSW網(wǎng)絡(luò)可以在不顯著增大聚集系數(shù)的前提下,明顯的降低社區(qū)間信息傳遞的平均距離.

2.2.2 疾病傳播的DSW

以上社區(qū)網(wǎng)絡(luò)實(shí)例雖然簡(jiǎn)單,但是在現(xiàn)實(shí)生活中有其實(shí)際應(yīng)用,不僅可以應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò),也可以應(yīng)用于流行病的傳播.比如某年在中國(guó)出現(xiàn)的H7N9流感.

若以一個(gè)省市代表一個(gè)節(jié)點(diǎn),則其分布正如上例的分析.世衛(wèi)組織強(qiáng)調(diào)H7N9沒有人與人傳播的證據(jù),就是在力圖傳遞這個(gè)信息:此病毒沒有形成DSW網(wǎng)絡(luò).因?yàn)樵贒SW網(wǎng)絡(luò)中,病毒可以迅速傳播.

2.3 DSW動(dòng)態(tài)路由分析

DSW在計(jì)算機(jī)網(wǎng)絡(luò)中有重要應(yīng)用,尤其可以應(yīng)用于動(dòng)態(tài)路由中.本小節(jié)在平均距離和聚集系數(shù)都不變的前提下,分析DSW模型.

根據(jù)2.1節(jié)算法,使用距離向量算法計(jì)算一個(gè)正則網(wǎng)絡(luò)模型的路由表,如圖5所示.

首先,可以計(jì)算網(wǎng)絡(luò)的平均距離,因?yàn)槿魏我粋€(gè)路由器到其他路由器的平均距離為1.8.根據(jù)對(duì)稱原理,整個(gè)網(wǎng)絡(luò)的平均距離為1.8.

同時(shí),可以計(jì)算該網(wǎng)絡(luò)的聚集系數(shù)是0.4.

然后,設(shè)定互相連接的兩個(gè)路由器間的距離為1,每個(gè)路由器到網(wǎng)絡(luò)的距離如圖5所示.以路由器R1為例,根據(jù)距離向量算法,可以得出,穩(wěn)定后的路由表如表2所示.

表2 R1路由表

圖5 正則網(wǎng)絡(luò)模型

隨機(jī)替換其中的兩條連線,以構(gòu)成DSW網(wǎng)絡(luò),如圖6所示,計(jì)算DSW網(wǎng)絡(luò)的平均距離,如表3所示.

圖6 DSW網(wǎng)絡(luò)模型

表3 DSW網(wǎng)絡(luò)模型平均距離

這個(gè)網(wǎng)絡(luò)的聚集系數(shù)為0.4.

Steven Strogatz等人構(gòu)建的SW模型通過(guò)增加少量聚集系數(shù)的代價(jià),大幅降低平均距離.而該文的DSW模型則聚集系數(shù)和平均距離都與原網(wǎng)絡(luò)相同.

計(jì)算穩(wěn)定后的新網(wǎng)絡(luò)中路由器R1的路由表,如表4所列.

與原網(wǎng)絡(luò)相比,該模型降低了路由器R1到Net4和Net5的距離.

該文DSW模型,在當(dāng)今云計(jì)算的背景下,有以下兩個(gè)優(yōu)點(diǎn):

1) 原網(wǎng)絡(luò)中,由于每個(gè)路由器到其他路由器的平均距離都為1.8,因此每個(gè)路由器處于同等重要的地位.而新的DSW網(wǎng)絡(luò)模型,降低了路由器R1,R2以及R6到其他路由器的平均距離,因此在實(shí)際應(yīng)用中,路由器R1,R2以及R6可以作為網(wǎng)絡(luò)中的核心路由器.

表4 更新后的R1路由表

2) 新的DSW網(wǎng)絡(luò)模型中,在沒有改變路由器R1到其他網(wǎng)絡(luò)距離的前提下,縮短了路由器R1到Net4和Net5的距離.在實(shí)際中,也有應(yīng)用價(jià)值.

3 實(shí) 驗(yàn)

本實(shí)驗(yàn)對(duì)DSW進(jìn)行仿真分析.

本實(shí)驗(yàn)重點(diǎn)關(guān)注以下兩個(gè)問(wèn)題:

1) DSW節(jié)點(diǎn)的平均度數(shù)是否低于隨機(jī)網(wǎng)絡(luò)和Steven Strogatz SW網(wǎng)絡(luò)？

2) DSW節(jié)點(diǎn)中心性是否高于隨機(jī)網(wǎng)絡(luò)和Steven Strogatz SW網(wǎng)絡(luò)？

3.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)環(huán)境如下:10臺(tái)服務(wù)器,每臺(tái)配置均為WindowsServer 2012 64 bit,處理器為Intel Xeon 3.10 GHz,內(nèi)存為8GB.仿真工具為Wireshark 1.12.5.數(shù)據(jù)集使用Twitter data數(shù)據(jù)集,同時(shí),本實(shí)驗(yàn)?zāi)M生成1×104個(gè)用戶節(jié)點(diǎn).

3.2 結(jié)果與分析

使用節(jié)點(diǎn)的平均度數(shù)和節(jié)點(diǎn)中心性來(lái)衡量實(shí)驗(yàn)結(jié)果,其中節(jié)點(diǎn)中心性由平均度中心性、平均最近距離中心性和平均介數(shù)3個(gè)子指標(biāo)組成.

節(jié)點(diǎn)的度數(shù)表示SW網(wǎng)絡(luò)中個(gè)體的交際能力,定義為:

(1)

式中di為節(jié)點(diǎn)的度數(shù),n為節(jié)點(diǎn)的數(shù)量,i和j表示節(jié)點(diǎn),若i≠j,則aij=1,否則,aij=0.

節(jié)點(diǎn)的平均度數(shù)是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均值:

(2)

度中心性是對(duì)度數(shù)歸一化為:

(3)

式中n為節(jié)點(diǎn)數(shù),ki表示第i個(gè)節(jié)點(diǎn)的度數(shù).

平均度中心性是所有節(jié)點(diǎn)度中心性的平均值

(4)

最近距離中心性表示2個(gè)節(jié)點(diǎn)的遠(yuǎn)近,定義為:

(5)

其值越大,表示2節(jié)點(diǎn)越緊密.平均最近距離中心性是最近距離中心性的均值

(6)

介數(shù)表示通過(guò)節(jié)點(diǎn)的最短路徑的數(shù)目

(7)

式中σst表示s到t的最短路徑數(shù)量,σst(i)表示其中通過(guò)i節(jié)點(diǎn)的數(shù)量.

平均介數(shù)是對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的介數(shù)求平均值

(8)

實(shí)驗(yàn)結(jié)果如表5所列.

表5 實(shí)驗(yàn)結(jié)果

可以得出以下結(jié)論:

1) SW網(wǎng)絡(luò)的度數(shù)比隨機(jī)網(wǎng)絡(luò)低,而且DSW網(wǎng)絡(luò)的度數(shù)低于Steven Strogatz SW.

2) 隨機(jī)網(wǎng)絡(luò)平均度中心性高于SW網(wǎng)絡(luò),而且DSW網(wǎng)絡(luò)的平均度中心性低于Steven Strogatz SW.

3) DSW兩節(jié)點(diǎn)的緊密程度高于Steven Strogatz SW網(wǎng)絡(luò).

4) SW網(wǎng)絡(luò)中,部分節(jié)點(diǎn)為核心節(jié)點(diǎn).

4 結(jié)語(yǔ)與展望

本文作者構(gòu)造了一種直聯(lián)小世界模型,在該模型下,平均距離和聚集系數(shù)與原網(wǎng)絡(luò)相同,但是網(wǎng)絡(luò)的跳數(shù)等性能有所改變.

SW不僅在計(jì)算機(jī)網(wǎng)絡(luò)中應(yīng)用廣泛,而且廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的其他方面,比如,可以更深入地研究DSW與計(jì)算機(jī)圖形學(xué)一個(gè)分支:分形的聯(lián)系,因?yàn)榉中卧谒械拇笮〕叨认露硷@得相似,與DSW具有很多類似的性質(zhì).可以探討DSW的分?jǐn)?shù)維,從而研究如何簡(jiǎn)化計(jì)算機(jī)網(wǎng)絡(luò).

從更長(zhǎng)遠(yuǎn)看,由于前人對(duì)SW在工商管理的組織行為學(xué)方面已有深入研究,將計(jì)算機(jī)科學(xué)和工商管理科學(xué)中對(duì)SW的研究做一對(duì)比分析,可能得出新的理論.

[1] Tonneau A,Mitton N,Vandaele J.How to choose an experimentation platform for wireless sensor networks? A survey on static and mobile wireless sensor network experimentation facilities [J].Ad Hoc Networks,2015,30:115-127.

[2] Kim Y,Kim J,Yook S.Information transfer network of global market indices [J].Physica A:Statistical Mechanics and its Applications,2015,430:39-45.

[3] Abraham I,Bartal Y,Neiman O.Local embeddings of metric spaces [J].Algorithmica,2015,72(2):539-606.

[4] Bellasi D E,Rovatti R,Benini L,et al.A low-power architecture for punctured compressed sensing and estimation in wireless sensor-nodes [J].IEEE Transactions on Circuits and Systems I:Regular Papers,2015,62(5):1296-1305.

[5] Shen H,Park J H,Wu Z,et al.Finite-time H-infinity synchronization for complex networks with semi-Markov jump topology [J].Communications in Nonlinear Science and Numerical Simulation,2015,24(1-3):40-51.

[6] Fraschini M,Hillebrand A,Demuru M,et al.An EEG-based bometric system using eigenvector centrality in resting state brain networks [J].IEEE Signal Processing Letters,2015,22(6):666-670.

[7] Isele T,Hartung B,Hoevel P,et al.Excitation waves on a minimal small-world model [J].European Physical Journal B,2015,88(4):104.

[8] Zuev K M,Wu S,Beck J L.General network reliability problem and its efficient solution by Subset Simulation [J].Probabilistic Engineering Mechanics,2015,40:25-35.

[9] Kokubo S,Wang Z,Tanimoto J.Spatial reciprocity for discrete,continuous and mixed strategy setups [J].Applied Mathematics and Computation,2015,259:552-568.

[10] Wichmann B.Agents of change and the approximation of network outcomes:a simulation study [J].Networks and Spatial Economics,2015,15(1):17-41.

(責(zé)任編輯：包震宇,郁 慧)

A novel Direct Small World network model

LIN Tao1,3, GAO Jianhua1, FU Xue1, MA Yan1, LIN Yan2

(1.College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China; 2.Department of Information System and Operations Management,The University of Auckland,Auckland 92019,New Zealand; 3.College of Information Sciences and Technology,Pennsyivania State University,Pennsyivania 16802,USA)

There is a certain degree of redundancy and low efficiency of existing computer networks.This paper presents a novel Direct Small World network model in order to optimize networks.In this model,several nodes construct a regular network.Then,randomly choose and replot some nodes to generate Direct Small World network iteratively.There is no change in average distance and clustering coefficient.However,the network performance,such as hops,is improved.The experiments prove that compared to traditional small world network,the degree,average of degree centrality and average of closeness centrality are lower in Direct Small World network.This illustrates that the nodes in Direct Small World networks are closer than Watts-Strogatz small world network model.The Direct Small World can be used not only in the communication of the community information,but also in the research of epidemics.

Small World network; complex networks; node centrality; network reliability; network optimization

2015-06-07

國(guó)家自然科學(xué)基金(61073163,61373004);上海市企業(yè)自主創(chuàng)新專項(xiàng)資金項(xiàng)目(滬CXY-2013-88)

高建華,中國(guó)上海市徐匯區(qū)桂林路100號(hào),上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:jhgao@shnu.edu.cn

TP 393

A

1000-5137(2016)05-0566-07

10.3969/J.ISSN.1000-5137.2016.05.009