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