小世界网络.doc

_4.2 小世界网络4.2.1 小世界网络简介1998年, Watts和Strogatz 提出了小世界网络这一概念，并建立了WS模型。实证结果表明，大多数的真实网络都具有小世界特性（较小的最短路径）和聚类特性（较大的聚类系数）。传统的规则最近邻耦合网络具有高聚类的特性，但并不具有小世界特性；而随机网络具有小世界特性但却没有高聚类特性。因此这两种传统的网络模型都不能很好的来表示实际的真实网络。Watts和Strogatz建立的小世界网络模型就介于这两种网络之间，同时具有小世界特性和聚类特性，可以很好的来表示真实网络。4.2.2 小世界模型构造算法1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡。相应程序代码（使用Matlab实现）ws_net.m （位于“代码”文件夹内）function ws_net()disp(小世界网络模型)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: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 Kifor j=i-K:i-1 A(i,j)=1;endelsefor j=1:i-1A(i,j)=1; endfor j=N-K+i:N A(i,j)=1; endendenddisp(A);%随机化重连for i=1:Nfor j=i+1:Nif A(i,j)=1pp=unifrnd(0,1); if ppnjj=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 mD1(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)Ci0=zeros(n,1);for i=1:naa1=find(D1(i,:)=1); %寻找子图的邻居节点if isempty(aa1)Ci0(i)=0;elsem1=length(aa1);if m1=1Ci0(i)=0;elseB1=D1(aa1,aa1); % 抽取子图的邻接矩阵Ci0(i)=length(find(B1=1)/(m1*(m1-1);endendendC0=mean(Ci0);for z=1:14% p(z)=1/2(z-1);for g=1:20%生成最近邻耦合网络B=zeros(n);for i=1:nfor j=i+1:i+kjj=j;if jnjj=mod(j,n);endB(i,jj)=1; B(jj,i)=1;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_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% endfor i=1:nfor j=1:kp_rand=rand(1,1);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:nD(i,i)=0;endm2=1;while m2D(i,m2)+D(m2,j)D(i,j)=D(i,m2)+D(m2,j);endendendm2=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:naa=find(D(i,:)=1); %寻找子图的邻居节点if isempty(aa)Ci(i)=0;elsem3=length(aa);if m3=1Ci(i)=0;elseBB=D(aa,aa); % 抽取子图的邻接矩阵Ci(i)=length(find(BB=1)/(m3*(m3-1);endendendC(z,g)=mean(Ci);endendfigureLWS=mean(L,2);CWS=mean(C,2);semilogx(p,LWS/L0,ro);hold on;semilogx(p,CWS/C0,b*);4.2.4 小结在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部分的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达。在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象（也称为小世界现象）的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以由小世界网络来作为模型。万维网、公路交通网、脑神经网络和基因网络都呈现小世界网络的特征。