WS小世界网络模型构造实践报告

1、WS小世界网络模型构造课题：WS小世界网络模型构造姓名 赵训学号 201026811130班级计算机实验班一、WS小世界网络简介1998年,Watts和Strogatz提岀了小世界网络这一概念，并建立了 W濮型。实证结果表明，大多数的真实网络都具有小世界特性（较小的最短路径）和聚类特性（较大的聚类系数）。传统的规 则最近邻耦合网络具有高聚类的特性，但并不具有小世界特性；而ER随机网络具有小世界特性但却没有高聚类特性。因此这两种传统的网络模型都不能很好的来表示实际的真实网络。Watts和Strogatz建立的WS、世界网络模型就介于这两种网络之间，同时具有小世界特性和聚类特性，可以很好的来表示真

2、实网络。二、WSb世界模型构造算法它们围成一个环，其中每个节点都与即将边的一个端点保持不变，而另1、从规则图开始：考虑一个含有 r个点的最近邻耦合网络, 它左右相邻的各K/2节点相连，K是偶数。2、随机化重连：以概率p随机地从新连接网络中的每个边，个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边, 并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如图a所示。规则网络 WS小世界网络随机网络p = 00<p<Ip-I相应程序代码（使用

3、Matlab实现）ws_net.m （位于“代码”文件夹内）fun ctio n ws_n et()disp('WS小世界网络模型')N=i nput('请输入网络节点数)；K=input('请输入与节点左右相邻的K/2的节点数');p=i nput('请输入随机重连的概率');an gle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(a ngle);y=100*si n(an gle);plot(x,y,'r.','Markersize',30);hold on;%fc成最近邻耦合网络；

4、A=zeros(N);disp(A);for i=1:Nif i+K<=Nfor j=i+1:i+KA(i,j)=1;endelsefor j=i+1:NA(i,j)=1;endfor j=1:(i+K)-N)A(i,j)=1;endendif K<ifor j=i-K:i-1A(i,j)=1;end elsefor j=1:i-1A(i,j)=1;endfor j=N-K+i:NA(i,j)=1;endendenddisp(A);%随机化重连for i=1:Nfor j=i+1:N if A(i,j)=1 pp=unifrn d(0,1);if pp<=pA(i,j)=0;

5、A(j,i)=0; b=unidrn d(N); while i=b b=unidrn d(N);endA(i,b)=1;A(b,i)=1;endendendend% 艮据邻接矩阵连线for i=1:Nfor j=1:Nif A(i,j)=1plot(x(i),x(j),y(i),y(j),'li newidth',1); hold on;endendendhold offaver_path=aver_pathle ngth(A); disp(aver_path);对应输出（取网络节点数 N=16, K=2; p分别取0, 0.1 , 1）。p=0( ws_n=16_k=2_p

6、=0.fig 的截图)P=0.1 （ws_n=16_k=2_p=0.1.fig 的截图）-100-80-60-40-20020406080100p=1 （ws_n=16_k=2_p=1.fig 的截图）输出结果与图a（图a位于第2页）吻合。三、WS、世界网络模型平均路径长度 L（p）与聚类系数C（p）归一化图平均路径长度平均路径长度也称为特征路径长度或平均最短路径长度，指的是一个网络中两点之间最短路径长度（或称距离）的平均值。从一个节点Si出发，经过与它相连的节点，逐步“走” 到另一个节点s所经过的路途，称为两点间的路径。其中最短的路径也称为两点间的距离，记作而平均路径长度定义为:这其中N是节

7、点数目，并定义节点到自身的最短路径长度为0。如果不计算到自身的距离，那么平均路径长度的定义就变成：集聚系数集聚系数（也称群聚系数、 集群系数）是用来描述图或网络中的顶点（节点）之间结集 成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如在社交网 络中，你的朋友之间相互认识的程度。一个节点Si的集聚系数 Qi）等于所有与它相连的顶点相互之间所连的边的数量， 除以这些顶点之间可以连出的最大边数。显然Ci）是一个介于0与1之间的数。C（i）越接近1,表示这个节点附近的点越有 "抱团”的趋 势。介于随机与规则之间对于纯粹的规则网络， 当其中连接数量接近饱和时，集聚系数很高，

8、 分短。例如完全耦合网络，每两个节点之间都相连，所以集聚系数是平均路径长度也十1,平均路径长度是1。然而，现实中的复杂网络是稀疏的，连接的个数只是节点数的若干倍）,每各节点都只与距离它最近的 2K个远远不到饱和。如果考虑将节点排列成正多边形, 节点相连，那么在 K比较大时，其集聚系数为：(K t)(37J2)32K(2K - i) 4虽然能保持高集聚系数，但平均路径长度为:平均路径长度与节点数成正比。纯粹的随机网络（如 ER随机网络模型）有着很小的平均路径长度，但同时集聚系数也 很小。可是现实中的不少网络虽然有很小的平均路径长度，但却也有着比随机网络高出相当多的集聚系数。因此瓦茨和斯特罗加茨认

9、为，现实中的复杂网络是一种介于规则网 络和随机网络之间的网络。他们把这种特性称为现实网络的小世界特性，就是：1.有很小的平均路径长度：在节点数N很大时，平均路径长度近似于distc ex log(Al2.有很高的集聚系数：集聚系数大约和规则网络在同一数量级，远大于随机网络 的集聚系数。相应程序代码(使用Matlab实现)ws.m (位于“代码”文件夹内)clc;clear all;format lo ng;n=1000;k=5;L=zeros(14,20);C=zeros(14,20);for i=1:14p(15-i,1)=1/2A(i-1);end% p=zeros(1,14);% p1=

10、 zeros(14,20);% LWS=zeros(14,1);% CWS=zeros(14,1);%生成最近邻耦合网络A=zeros (n);for i=1: nfor j=i+1:i+kjj=j;if j>njj=mod(j, n);endA(i,jj)=1; A(jj,i)=1;endend%计算平均路径长度L(0)D1=A;inf,自身D1(fi nd(D1=0)=i nf;%将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为到自身的距离为 0.for i=1: nD1(i,i)=0;endm=1;while m<=n%Floyd算法求解任意两点的最短距离for i=1: n

11、for j=1: nif D1(i,j)>D1(i,m)+D1(m,j)D1(i,j)=D1(i,m)+D1(m,j);endendendm=m+1;endL0=sum(sum(D1)/( n*( n-1);% 平均路径长度%十算聚类系数C(0)CiO=zeros( n,1);for i=1: naa1=fi nd(D1(i,:)=1);%寻找子图的邻居节点if isempty(aal)Ci0(i)=0;elsem1=le ngth(aa1);if m1=1Ci0(i)=0;elseB仁D1(aa1,aa1);%抽取子图的邻接矩阵CiO(i)=le ngth(fi nd(B 1=1)/(

12、m1*(m1-1);endendendC0=mea n(CiO);for z=1:14%p(z)=1/2A(z-1);for g=1:20%生成最近邻耦合网络B=zeros (n);for i=1: nfor j=i+1:i+kjj=j；if j>njj=mod(j, n); endB(i,jj)=1; B(jj,i)=1; endend%随机化重连for i=1:n%p_ra nd=ra nd(1,1);%b=fi nd(B(i,:)=1);%for j=1:le ngth(b)%j仁 b(j);%if p_rand<p(z,1)%生成的随机数小于p,则边进行随机化重连，否则，边

13、不进行重连%件%endendendB(i,j1)=0;B(j1,i)=0;bb=ra ndin t(1,1,1, n);if B(i,bb)=0&&B(bb,i)=0&&bb=iB(i,bb)=1;B(bb,i)=1;end%重连条for i=1: nfor j=1:kp_ran d=ra nd(1,1);if p_ra nd<p(z,1)bb=ra ndin t(1,1,1, n);if B(i,bb)=0&&B(bb,i)=0&&bb=i j2=j+i;if j2>nj2=mod(j2, n);endB(i,j2)

14、=0;B(j2,i)=0;B(i,bb)=1;B(bb,i)=1;endendendend%计算平均路径长度aver_L%n仁 size(A,2);D=B;%重连条件两点无边相连时赋值为inf，D(fi nd(D=0)=i nf;%将邻接矩阵变为邻接距离矩阵,自身到自身的距离为 0.for i=1: nD(i,i)=0;endm2=1;while m2<=n%Floyd算法求解任意两点的最短距离for i=1: nfor j=1: nif D(i,j)>D(i,m2)+D(m2,j)D(i,j)=D(i,m2)+D(m2,j);endendendm2=m2+1;end%if len

15、 gth(i nflin e)>0%D(i nflin e,:)=;%D(:,i nflin e)=;%n2=size(D,2);%L(z,g)=sum(sum(D)/(n2*(n2-1);% 求出平均路径%elseL(z,g)=sum(sum(D)/(n*(n-1);% 求出平均路径%end%计算聚类系数aver_CCi=zeros( n,1);for i=1: naa=fi nd(D(i,:)=1);%寻找子图的邻居节点if isempty(aa)Ci(i)=0;elsem3=le ngth(aa);if m3=1Ci(i)=0;elseBB=D(aa,aa);%抽取子图的邻接矩阵C

16、i(i)=le ngth(fi nd(BB=1)/(m3*(m3-1);endendendC(z,g)=mea n( Ci);endendfigureLWS=mea n( L,2);CWS=mea n(C,2); semilogx(p, LWS/LO,'ro'); hold on; semilogx(p,CWS/CO,'b*');对应输出（ws.fig的截图） * 才* +'4- 1' 厂+*0704020.110O <>M I L卜10'与图b （图b位于第7页）吻合四、结论在网络理论中，小世界网络是一类特殊的复杂网络结构，

17、在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达（本文只讨论WS小世界模型）。在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”小世界网络就是对这种现象（也称为小世界现象）的数学描述。用数学中图论的语言来说， 小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外， 小世界网络的例子在生物学、 物理学、计算机科学等领域也 有出现。许多经验中的图可以由小世界网络来作为模型。万维网、公路交通网、 脑神经网络和基因网络都呈现小世界网络的特征。小世界网络模型反映了朋友关系网络的一种特性，即大部分的人的朋友都是和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是住得较远的，甚至是远在异国他乡的朋友，这种情形对应于WS、世界模型中通过重新连线产生的远程连接。五、参考来源1. W与NV两种小世界网络模型的建模及仿真研究王波,王万良，杨旭华 浙