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

ws小世界网络模型构造课题：ws小世界网络模型构造姓名 赵训 学号 201026811130 班级 计算机实验班 一、ws 小世界网络简介1998年, watts和strogatz 提出了小世界网络这一概念,并建立了ws模型。 实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较大的聚类系数) 。 传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而er 随机网络具有小世界特性但却没有高聚类特性。 因此这两种传统的网络模型都不能很好的来表示实际的真实网络。 watts和strogatz建立的ws小世界网络模型就介于这两种网络之间,同时具有小世界特性和聚类特性,可以很好的来表示真实网络。二、ws小世界模型构造算法1、从规则图开始：考虑一个含有n个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各k/2节点相连，k是偶数。2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如图a所示。图a相应程序代码（使用matlab实现）ws_net.m （位于“代码”文件夹内）function ws_net()disp(ws小世界网络模型)n=input(请输入网络节点数);k=input(请输入与节点左右相邻的k/2的节点数);p=input(请输入随机重连的概率);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:n if i+k=n for j=i+1:i+k a(i,j)=1; end else for j=i+1:n a(i,j)=1; end for j=1:(i+k)-n) a(i,j)=1; end end if ki for j=i-k:i-1 a(i,j)=1; end else for j=1:i-1 a(i,j)=1; end for j=n-k+i:n a(i,j)=1; end endenddisp(a);%随机化重连for i=1:n for j=i+1:n if a(i,j)=1 pp=unifrnd(0,1); if ppn jj=mod(j,n); end a(i,jj)=1; a(jj,i)=1; endend%计算平均路径长度l(0)d1=a;d1(find(d1=0)=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为inf，自身到自身的距离为0.for i=1:n d1(i,i)=0;endm=1;while md1(i,m)+d1(m,j) d1(i,j)=d1(i,m)+d1(m,j); end end end m=m+1;endl0=sum(sum(d1)/(n*(n-1); %平均路径长度%计算聚类系数c(0)ci0=zeros(n,1);for i=1:n aa1=find(d1(i,:)=1); %寻找子图的邻居节点 if isempty(aa1) ci0(i)=0; else m1=length(aa1); if m1=1 ci0(i)=0; else b1=d1(aa1,aa1); % 抽取子图的邻接矩阵 ci0(i)=length(find(b1=1)/(m1*(m1-1); end endendc0=mean(ci0);for z=1:14 % p(z)=1/2(z-1); for g=1:20 %生成最近邻耦合网络 b=zeros(n); for i=1:n for j=i+1:i+k jj=j; if jn jj=mod(j,n); end b(i,jj)=1; b(jj,i)=1; end end %随机化重连 % for i=1:n% p_rand=rand(1,1);% b=find(b(i,:)=1);% for j=1:length(b)% j1=b(j);% if p_randp(z,1) % 生成的随机数小于p，则边进行随机化重连,否则，边不进行重连% b(i,j1)=0;b(j1,i)=0;% bb=randint(1,1,1,n);% if b(i,bb)=0&b(bb,i)=0&bb=i %重连条件% b(i,bb)=1;b(bb,i)=1;% end% end% end% end for i=1:n for j=1:k p_rand=rand(1,1); if p_randn j2=mod(j2,n); end b(i,j2)=0; b(j2,i)=0; b(i,bb)=1; b(bb,i)=1; end end end end %计算平均路径长度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 m2d(i,m2)+d(m2,j) d(i,j)=d(i,m2)+d(m2,j); end end end 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);%求出平均路径% else l(z,g)=sum(sum(d)/(n*(n-1);%求出平均路径% end %计算聚类系数aver_c ci=zeros(n,1); for i=1:n aa=find(d(i,:)=1); %寻找子图的邻居节点 if isempty(aa) ci(i)=0; else m3=length(aa); if m3=1 ci(i)=0; else bb=d(aa,aa); % 抽取子图的邻接矩阵 ci(i)=length(find(bb=1)/(m3*(m3-1); end end end c(z,g)=mean(ci); endendfigurelws=mean(l,2);cws=mean(c,2);semilogx(p,lws/l0,ro);hold on;semilogx(p,cws/c0,b*);对应输出(ws.fig的截图)与图b（图b位于第7页）吻合四、结论在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达（本文只讨论ws小世界模型）。在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象（也称为小世界现象）的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以由小世界网络来作为模型。万维网、公路交通网、脑神经网络和基因网络都呈现小世界网络的特征。小世界网络模型反映了朋友关系网络的一种特性，即大部分的人的朋友都是和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是住得较远的，甚至是远在异国他乡的朋友，这种情形对应于ws小世界模型中通过重新连线产生的远程连接。五、参考来源1.ws与nw两种小世界网络模型的建模及仿真研究王波,王万良,杨旭华 浙江工业大学学报 第37 卷第2 期 2009 年4 月2.“小世界”网络的集体动力学 duncan j. watts ， steven h. strogatz （nature | vol 393 |