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

课题：WS小世界网络模型构造姓名 赵训************班级计算机实验班一、 WS小世界网络简介1998年，Watts和Strogatz提出了小世界网络这一概念，并建立了WS模型实证结果表明，大多 数的真实网络都具有小世界特性（较小的最短路径）和聚类特性（较大的聚类系数）传统的规 则最近邻耦合网络具有高聚类的特性，但并不具有小世界特性;而ER随机网络具有小世界特性但 却没有高聚类特性因此这两种传统的网络模型都不能很好的来表示实际的真实网络Watts 和Strogatz建立的WS小世界网络模型就介于这两种网络之间，同时具有小世界特性和聚类特性， 可以很好的来表示真实网络二、 WS小世界模型构造算法1、 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与 它左右相邻的各K/2节点相连，K是偶数2、 随机化重连：以概率）随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一 个端点取为网络中随机选择的一个节点其中规定，任意两个不同的节点之间至多只能有一条边， 并且每一个节点都不能有边与自身相连在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就 可以控制从完全规则网络到完全随机网络的过渡，如图a所示。

规则网络 WS小世界网络 随机捌络p = 0 0 1 p -1图a相应程序代码（使用Matlab实现）ws_ne t.m (位于“代码”文件夹内)func tion ws_ne t() disp('WS小世界网络模型') N=inpu t('请输入网络节点数')；K=input ('请输入与节点左右相邻的K/2的节点数'); p=inpu t('请输入随机重连的概率')； angle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(angle); y=100*sin(angle);plot( x,y,'r.','Markersize',30);hold on;%生成最近邻耦合网络； 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

p=0 (ws_n=16_k=2_p=0.fig 的截图)p=1 （ws_n=16_k=2_p=1.fig 的截图）输出结果与图a（图a位于第2页）吻合三、WS小世界网络模型平均路径长度L（p）与聚类系数C（p）归一化图平均路径长度平均路径长度也称为特征路径长度或平均最短路径长度，指的是一个网络中两点之间最 短路径长度（或称距离）的平均值从一个节点s出发，经过与它相连的节点，逐步“走” i到另一个节点s所经过的路途，称为两点间的路径其中最短的路径也称为两点间的距 j离，记作山叩！；.」：而平均路径长度定义为：这其中N是节点数目，并定义节点到自身的最短路径长度为0如果不计算到自身的距 离，那么平均路径长度的定义就变成：集聚系数集聚系数（也称群聚系数、集群系数）是用来描述图或网络中的顶点（节点）之间结集 成团的程度的系数具体来说，是一个点的邻接点之间相互连接的程度例如在社交网 络中，你的朋友之间相互认识的程度一个节点s的集聚系数C（i）等于所有与它相i连的顶点相互之间所连的边的数量，除以这些顶点之间可以连出的最大边数显然C（i） 是一个介于0与1之间的数°C（i）越接近1,表示这个节点附近的点越有“抱团”的趋 势。

介于随机与规则之间对于纯粹的规则网络，当其中连接数量接近饱和时，集聚系数很高，平均路径长度也十 分短例如完全耦合网络，每两个节点之间都相连，所以集聚系数是1，平均路径长度 是1然而，现实中的复杂网络是稀疏的，连接的个数只是节点数的若干倍 （心）， 远远不到饱和如果考虑将节点排列成正多边形，每各节点都只与距离它最近的2K个 节点相连，那么在K比较大时，其集聚系数为：虽然能保持高集聚系数，但平均路径长度为:G严黑PN）平均路径长度与节点数成正比纯粹的随机网络（如ER随机网络模型）有着很小的平均路径长度，但同时集聚系数也 很小可是现实中的不少网络虽然有很小的平均路径长度，但却也有着比随机网络高出 相当多的集聚系数因此瓦茨和斯特罗加茨认为，现实中的复杂网络是一种介于规则网 络和随机网络之间的网络他们把这种特性称为现实网络的小世界特性，就是：1.有很小的平均路径长度：在节点数N很大时，平均路径长度近似于dist-c k>g（N）2.有很高的集聚系数：集聚系数大约和规则网络在同一数量级，远大于随机网络 的集聚系数WS模型的集聚系数C （红色）与平均路径长度L（蓝色）随P变化的图像相应程序代码(使用Matlab实现)ws.m (位于“代码”文件夹内)clc;clear all;format long;n=1000;k=5;L=zeros(14,20);C=zeros(14,20);for i=1:14p(15-i,1)=1/2"i-1);end% p=zeros(1,14);% p1=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>n jj=mod(j,n);endA(i,jj)=1; A(jj,i)=1;endend %%计算平均路径长度 L(0)D1=A;D1(find(D1==0))=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为inf,自身到自身的距离为 0.for i=1:nD1(i,i)=0;endm=1;while m<=n %Floyd 算法求解任意两点的最短距离for i=1:nfor 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(Dl))/(n*(n-l))% 平均路径长度%%计算聚类系数C(0)Ci0=zeros(n,1);for i=1:naal=find(Dl(i,:)==l%寻找子图的邻居节点if isempty(aal)Ci0(i)=0;else ml=length(aal);辻 m1==1Ci0(i)=0;elseBl=Dl(aal,aal); % 抽取子图的邻接矩阵Ci0(i)=length(find(Bl==l))/(ml*(ml-l));endendendC0=mean(Ci0);for z=l:l4% p(z)二/T(z-1);for g=l:20%%生成最近邻耦合网络B=zeros(n);for i=l:n for j=i+l:i+kjj=j;if j>n jj=mod(j,n);endB(i,jj)=l; B(jj,i)=l;endend%随机化重连for i=1:n% p_rand=rand(1,1);% b=find(B(i,:)==1);% for j=1:length(b)% j1=b(j);% if p_randnj2=mod(j2,n);endB(i,j2)=0;B(j2,i)=0;B(i,bb)=1;B(bb,i)=1;endendendend%%计算平均路径长度 aver_L% n1=size(A,2);D=B;D(find(D==0))=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为 inf自身到自身的距离为 0.for i=1:n D(i,i)=0;end m2=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);endendend m2=m2+1;end% if length(infline)>0% D(infline,:)=[];% D(:,infline)=[];% 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:n aa=find(D(i,:)==1); %寻找子图的邻居节点 if isempty(aa)Ci(i)=0;elsem3=length(aa);if m3==1 Ci(i)=0;else BB=D(aa,aa); % 抽取子图的邻接矩阵endCi(i)=length(find(BB==1))/(m3*(m3-1));endendC(z,g)=mean(Ci); endendfig。