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

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

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

0 引 言

隨著計算機(jī)網(wǎng)絡(luò)的發(fā)明與大規(guī)模應(yīng)用,人們之間的距離越來越近.同時,另一方面,現(xiàn)有的計算機(jī)網(wǎng)絡(luò)存在一定程度冗余和效率低等問題.因此,引入小世界(SW)網(wǎng)絡(luò)為模型,以嘗試優(yōu)化現(xiàn)有的計算機(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é)點并不互相連接,但絕大部分節(jié)點經(jīng)過少數(shù)幾步就可到達(dá)[2].

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

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

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

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

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

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

計算機(jī)網(wǎng)絡(luò)是利用通信設(shè)備和線路將地理位置不同的、功能獨立的多個計算機(jī)系統(tǒng)連接起來,以功能完善的網(wǎng)絡(luò)軟件實現(xiàn)網(wǎng)絡(luò)的硬件、軟件及資源共享和信息傳遞的系統(tǒng).隨著計算機(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òu)成的圖,其中任意兩點之間的平均路徑長度比頂點數(shù)量小得多.最早起源于人文科學(xué),20世紀(jì)60年代,美國哈佛大學(xué)社會心理學(xué)家斯坦利·米爾格倫實驗發(fā)現(xiàn)世界上任意兩個人都可以經(jīng)過最多5個人而聯(lián)系,即所謂的“六度分割理論”.除了社會人際網(wǎng)絡(luò)以外,SW的例子在生物學(xué)、物理學(xué)、計算機(jī)科學(xué)等領(lǐng)域均有出現(xiàn)[7].許多圖可以用SW作為模型[8].萬維網(wǎng)、公路交通網(wǎng)、腦神經(jīng)網(wǎng)絡(luò)和基因網(wǎng)絡(luò)都呈現(xiàn)SW的特征[9].

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

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

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

2.1 算 法

DSW算法如圖1所示.

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

2.2 DSW實例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 疾病傳播的DSW

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

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

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

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

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

首先,可以計算網(wǎng)絡(luò)的平均距離,因為任何一個路由器到其他路由器的平均距離為1.8.根據(jù)對稱原理,整個網(wǎng)絡(luò)的平均距離為1.8.

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

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

表2 R1路由表

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

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

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

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

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

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

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

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

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

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

表4 更新后的R1路由表

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

3 實 驗

本實驗對DSW進(jìn)行仿真分析.

本實驗重點關(guān)注以下兩個問題:

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

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

3.1 實驗設(shè)計

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

3.2 結(jié)果與分析

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

(7)

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

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

(8)

實驗結(jié)果如表5所列.

表5 實驗結(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é)點的緊密程度高于Steven Strogatz SW網(wǎng)絡(luò).

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

4 結(jié)語與展望

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

SW不僅在計算機(jī)網(wǎng)絡(luò)中應(yīng)用廣泛,而且廣泛應(yīng)用于計算機(jī)科學(xué)的其他方面,比如,可以更深入地研究DSW與計算機(jī)圖形學(xué)一個分支:分形的聯(lián)系,因為分形在所有的大小尺度下都顯得相似,與DSW具有很多類似的性質(zhì).可以探討DSW的分?jǐn)?shù)維,從而研究如何簡化計算機(jī)網(wǎng)絡(luò).

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

[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

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

高建華,中國上海市徐匯區(qū)桂林路100號,上海師范大學(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