一种新型直联小世界网络模型

林 涛, 高建华, 伏 雪, 马 燕, 林 艳

(1.上海师范大学 信息与机电工程学院,上海 200234; 2.奥克兰大学 信息系统系,奥克兰 92019; 3.宾夕法尼亚州立大学 信息科学与技术学院,宾夕法尼亚州 16802)



一种新型直联小世界网络模型

林 涛1,3, 高建华1, 伏 雪1, 马 燕1, 林 艳2

(1.上海师范大学 信息与机电工程学院,上海 200234; 2.奥克兰大学 信息系统系,奥克兰 92019; 3.宾夕法尼亚州立大学 信息科学与技术学院,宾夕法尼亚州 16802)

现有计算机网络存在一定程度冗余和效率低等问题,提出一种新的直联小世界(DSW)网络模型以优化网络.首先将节点构成正则网络,然后取任意节点重画,通过迭代生成DSW网络.在该模型下,平均距离和聚集系数与原网络相同,但是网络的跳数等性能有所改变.实验证明,DSW网络的度数、平均度中心性以及平均最近距离中心性均低于原有小世界(SW)网络.表明DSW网络两节点的紧密程度高于SW网络.该模型不仅可以有效应用于社区信息的传播,还可以用于流行病传播的研究.

小世界网络; 复杂网络; 节点中心性; 网络可靠性; 网络优化

0 引 言

随着计算机网络的发明与大规模应用,人们之间的距离越来越近.同时,另一方面,现有的计算机网络存在一定程度冗余和效率低等问题.因此,引入小世界(SW)网络为模型,以尝试优化现有的计算机网络,在网络信息传递方面尤其重要[1].

在网络理论中,SW网络是一类特殊的复杂网络结构,在这种网络中大部分的节点并不互相连接,但绝大部分节点经过少数几步就可到达[2].

本文作者构造一种新型SW模型:直联小世界网络(DSW).在该模型下,平均距离和聚集系数与原网络相同,但是网络的跳数等性能有所改变.

本文以实例说明DSW网络在现实生活中有广泛应用.不仅可以有效应用于社区信息的传播,而且可以用于流行病传播的研究.一方面,可以通过人为构建DSW网络,在不显著增加成本的前提下,快速传播社区信息.另一方面,可以通过人为破坏DSW网络迅速降低流行病的传播.

章节安排如下:第1部分介绍SW网络的基本概念.第2部分,论述DSW网络的算法和实例.第3部分,实验以及结果分析.最后是结语与展望.

1 SW网络介绍

这个世界能有多小？数千年前的哲学家就在思考这个问题.20世纪末,随着计算机网络的发明与大规模应用,全球信息传播方式发生翻天覆地变化.同时,由于计算机网络的冗余以及效率低(比如:使用大部分的即时聊天软件时,即使两个人在同一幢大楼,聊天信息一般也需要经过ISP服务器),因而需要优化网络[3].

优化网络的一个思路是减少路由次数.路由(routing)就是通过互联网把信息从源地址传输到目的地址[4].路由发生在OSI网络参考模型中的第三层即网络层,已经成为互联网上寻找路径的最主要方法[5].

计算机网络是利用通信设备和线路将地理位置不同的、功能独立的多个计算机系统连接起来,以功能完善的网络软件实现网络的硬件、软件及资源共享和信息传递的系统.随着计算机网络的发展,出现了很多网络模型,用于解决网络中存在的效率与资源的关系,SW网络就是一种最新出现的重要网络模型[6].

SW是一个由大量顶点构成的图,其中任意两点之间的平均路径长度比顶点数量小得多.最早起源于人文科学,20世纪60年代,美国哈佛大学社会心理学家斯坦利·米尔格伦实验发现世界上任意两个人都可以经过最多5个人而联系,即所谓的“六度分割理论”.除了社会人际网络以外,SW的例子在生物学、物理学、计算机科学等领域均有出现[7].许多图可以用SW作为模型[8].万维网、公路交通网、脑神经网络和基因网络都呈现SW的特征[9].

在计算机科学中,SW最早是由邓肯·瓦茨(Duncan Watts)和斯蒂文·斯特罗加茨(Steven Strogatz)在1998年引进的.将高聚集系数和低平均路径长度作为特征,一般就称作瓦兹-史楚盖兹模型(WS模型)[10],这也是最典型的SW的模型.

2 DSW网络

本节提出DSW网络的算法和实例.

2.1 算 法

DSW算法如图1所示.

该算法的核心是首先将节点构成正则网络(第1行),然后取任意节点重画(第2、3行),最后迭代k次(第4行).

2.2 DSW实例

本小节分别在社区网络和疾病传播方面给出DSW的两个实例.

2.2.1 社区网络分析

平均距离也称为特征路径长度或平均最短路径长度,指的是一个网络中两点之间最短路径长度(或称距离)的平均值.从一个节点Si出发,经过与它相连的节点,逐步“走”到另一个节点Sj所经过的路途,称为两点间的路径.其中最短的路径也称为两点间的距离,记作dist(i,j)为:

DSW网络可以有效地应用于社区信息的扩散.对于最简单的社区,每个社区由一个顶点表示,共有4个顶点.首先,社区通过如下方式连接,构成正则图,如图2所示.

可以求得,其平均距离为1.5,聚集系数为0.66.

若随机将处于对角线上的两个社区相连,如图3所示.

则重画后的社区的平均距离为1,聚集系数为0.83.

事实上,现实社会中的随机网络,如图4所示.

图2 正则社区网络

图3 随机的社区网络

图4 现实社区网络

其平均距离为1,聚集系数为1.

分析相关数据,如表1所列.

表1 各种社区网络参数比较

由此例可知,对于一个存在几个社区的网络,通过DSW网络可以在不显著增大聚集系数的前提下,明显的降低社区间信息传递的平均距离.

2.2.2 疾病传播的DSW

以上社区网络实例虽然简单,但是在现实生活中有其实际应用,不仅可以应用于计算机网络,也可以应用于流行病的传播.比如某年在中国出现的H7N9流感.

若以一个省市代表一个节点,则其分布正如上例的分析.世卫组织强调H7N9没有人与人传播的证据,就是在力图传递这个信息:此病毒没有形成DSW网络.因为在DSW网络中,病毒可以迅速传播.

2.3 DSW动态路由分析

DSW在计算机网络中有重要应用,尤其可以应用于动态路由中.本小节在平均距离和聚集系数都不变的前提下,分析DSW模型.

根据2.1节算法,使用距离向量算法计算一个正则网络模型的路由表,如图5所示.

首先,可以计算网络的平均距离,因为任何一个路由器到其他路由器的平均距离为1.8.根据对称原理,整个网络的平均距离为1.8.

同时,可以计算该网络的聚集系数是0.4.

然后,设定互相连接的两个路由器间的距离为1,每个路由器到网络的距离如图5所示.以路由器R1为例,根据距离向量算法,可以得出,稳定后的路由表如表2所示.

表2 R1路由表

图5 正则网络模型

随机替换其中的两条连线,以构成DSW网络,如图6所示,计算DSW网络的平均距离,如表3所示.

图6 DSW网络模型

表3 DSW网络模型平均距离

这个网络的聚集系数为0.4.

Steven Strogatz等人构建的SW模型通过增加少量聚集系数的代价,大幅降低平均距离.而该文的DSW模型则聚集系数和平均距离都与原网络相同.

计算稳定后的新网络中路由器R1的路由表,如表4所列.

与原网络相比,该模型降低了路由器R1到Net4和Net5的距离.

该文DSW模型,在当今云计算的背景下,有以下两个优点:

1) 原网络中,由于每个路由器到其他路由器的平均距离都为1.8,因此每个路由器处于同等重要的地位.而新的DSW网络模型,降低了路由器R1,R2以及R6到其他路由器的平均距离,因此在实际应用中,路由器R1,R2以及R6可以作为网络中的核心路由器.

表4 更新后的R1路由表

2) 新的DSW网络模型中,在没有改变路由器R1到其他网络距离的前提下,缩短了路由器R1到Net4和Net5的距离.在实际中,也有应用价值.

3 实 验

本实验对DSW进行仿真分析.

本实验重点关注以下两个问题:

1) DSW节点的平均度数是否低于随机网络和Steven Strogatz SW网络？

2) DSW节点中心性是否高于随机网络和Steven Strogatz SW网络？

3.1 实验设计

实验环境如下:10台服务器,每台配置均为WindowsServer 2012 64 bit,处理器为Intel Xeon 3.10 GHz,内存为8GB.仿真工具为Wireshark 1.12.5.数据集使用Twitter data数据集,同时,本实验模拟生成1×104个用户节点.

3.2 结果与分析

使用节点的平均度数和节点中心性来衡量实验结果,其中节点中心性由平均度中心性、平均最近距离中心性和平均介数3个子指标组成.

节点的度数表示SW网络中个体的交际能力,定义为:

(1)

式中di为节点的度数,n为节点的数量,i和j表示节点,若i≠j,则aij=1,否则,aij=0.

节点的平均度数是网络中所有节点的平均值:

(2)

度中心性是对度数归一化为:

(3)

式中n为节点数,ki表示第i个节点的度数.

平均度中心性是所有节点度中心性的平均值

(4)

最近距离中心性表示2个节点的远近,定义为:

(5)

其值越大,表示2节点越紧密.平均最近距离中心性是最近距离中心性的均值

(6)

介数表示通过节点的最短路径的数目

(7)

式中σst表示s到t的最短路径数量,σst(i)表示其中通过i节点的数量.

平均介数是对网络中所有节点的介数求平均值

(8)

实验结果如表5所列.

表5 实验结果

可以得出以下结论:

1) SW网络的度数比随机网络低,而且DSW网络的度数低于Steven Strogatz SW.

2) 随机网络平均度中心性高于SW网络,而且DSW网络的平均度中心性低于Steven Strogatz SW.

3) DSW两节点的紧密程度高于Steven Strogatz SW网络.

4) SW网络中,部分节点为核心节点.

4 结语与展望

本文作者构造了一种直联小世界模型,在该模型下,平均距离和聚集系数与原网络相同,但是网络的跳数等性能有所改变.

SW不仅在计算机网络中应用广泛,而且广泛应用于计算机科学的其他方面,比如,可以更深入地研究DSW与计算机图形学一个分支:分形的联系,因为分形在所有的大小尺度下都显得相似,与DSW具有很多类似的性质.可以探讨DSW的分数维,从而研究如何简化计算机网络.

从更长远看,由于前人对SW在工商管理的组织行为学方面已有深入研究,将计算机科学和工商管理科学中对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.

(责任编辑：包震宇,郁 慧)

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

国家自然科学基金(61073163,61373004);上海市企业自主创新专项资金项目(沪CXY-2013-88)

高建华,中国上海市徐汇区桂林路100号,上海师范大学信息与机电工程学院,邮编: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