小世界网络.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: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 K<i
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
end
end
disp(A);
%随机化重连
for i=1:N
for j=i+1:N
if A(i,j)==1
pp=unifrnd(0,1); if pp<=p
A(i,j)=0; A(j,i)=0;
b=unidrnd(N); while i==b
b=unidrnd(N); end
A(i,b)=1; A(b,i)=1; end
end
end
end
%根据邻接矩阵连线
for i=1:N
for j=1:N
if A(i,j)==1
plot([x(i),x(j)],[y(i),y(j)],'linewidth',1); hold on;
end
end
end
hold off
aver_path=aver_pathlength(A);
disp(aver_path);
4.2.3小世界网络模型平均路径长度与聚类系数
对于纯粹的规则网络，当其中连接数量接近饱和时，集聚系数很高，平均路径长度也十分短。例如完全耦合网络，每两个节点之间都相连，所以集聚系数是1，平均路径长度是1。然而，现实中的复杂网络是稀疏的，连接的个数只是节点数的若干倍，远远不到饱和。如果考虑将节点排列成正多边形，每个节点都只与距离它最近的 2K 个节点相连，那么在K比较大时，其集聚系数为：

虽然能保持高集聚系数，但平均路径长度为：

平均路径长度与节点数成正比。纯粹的随机网络有着很小的平均路径长度，但同时集聚系数也很小。可是现实中的不少网络虽然有很小的平均路径长度，但却也有着比随机网络高出相当多的集聚系数。因此瓦茨和斯特罗加茨认为，现实中的复杂网络是一种介于规则网络和随机网络之间的网络。他们把这种特性称为现实网络的小世界特性，就是：
1. 有很小的平均路径长度：在节点数N很大时，平均路径长度近似于随机网络；
2. 有很高的集聚系数：集聚系数大约和规则网络在同一数量级，远大于随机网络的集聚系数。
相应程序代码（使用Matlab实现）
ws.m （位于“代码”文件夹内）
clc;
clear all;
format long;
n=1000;
k=5;
L=zeros(14,20);
C=zeros(14,20);
for i=1:14
p(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:n
for j=i+1:i+k
jj=j;
if j>n
jj=mod(j,n);
end
A(i,jj)=1; A(jj,i)=1;
end
end
%%计算平均路径长度L(0)
D1=A;
D1(find(D1==0))=inf; %将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为inf，自身到自身的距离为0.
for i=1:n
D1(i,i)=0;
end
m=1;
while m<=n %Floyd算法求解任意两点的最短距离
for i=1:n
for j=1:n
if D1(i,j)>D1(i,m)+D1(m,j)
D1(i,j)=D1(i,m)+D1(m,j);
end
end
end
m=m+1;
end
L0=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
end
end
C0=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 j>n
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_rand<p(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_rand<p(z,1)
bb=randint(1,1,[1,n]);
if B(i,bb)==0&&B(bb,i)==0&&bb~=i %重连条件
j2=j+i;
if j2>n
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 m2<=n %Floyd算法求解任意两点的最短距离
for i=1:n
for j=1:n
if D(i,j)>D(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);
end
end
figure
LWS=mean(L,2);
CWS=mean(C,2);
semilogx(p,LWS/L0,'ro');
hold on;
semilogx(p,CWS/C0,'b*');
4.2.4 小结
在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部分的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达。
在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象（也称为小世界现象）的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以由小世界网络来作为模型。万维网、公路交通网、脑神经网络和基因网络都呈现小世界网络的特征。
小世界网络模型反映了朋友关系网络的一种特性，即大部分的人的朋友都是和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是住得较远的，甚至是远在异国他乡的朋友，这种情形对应于小世界模型中通过重新连线产生的远程连接。