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 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比较大时，其集聚系数为： ()()()()1323 2214K K C i K K --=≈- 虽然能保持高集聚系数，但平均路径长度为： ()4N l O N 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 % 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 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 小结 在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部分的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象（也称为小世界现象）的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以由小世界网络来作为模型。万维网、公路交通网、脑神经网络和基因网络都呈现小世界网络的特征。 小世界网络模型反映了朋友关系网络的一种特性，即大部分的人的朋友都是和他们住在同一条街上的邻居或在同一单位工作的同事。另一方面，也有些人是住得较远的，甚至是远在异国他乡的朋友，这种情形对应于小世界模型中通过重新连线产生的远程连接。 （注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注） 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 程序仿真实例 例一、请输入最近邻耦合网络中节点的总数N:30 请输入最近邻耦合网络中每个节点的邻居数K:4 请输入随机化重连的概率p:0.9 例二、请输入最近邻耦合网络中节点的总数N:40 请输入最近邻耦合网络中每个节点的邻居数K:2 请输入随机化重连的概率p:0.7 Matlab的m文件代码如下： N=input('请输入最近邻耦合网络中节点的总数N:'); K=input('请输入最近邻耦合网络中每个节点的邻居数K:'); if K>floor(N-1)|mod(K,2)~=0; disp('参数输入错误：K值必须是小于网络节点总数且为偶数的整数'); return ; end angle=0:2*pi./N:2*pi-2*pi/N; angle=0:2*pi/N:2*pi-2*pi/N; x=100*sin(angle); y=100*cos(angle); plot(x,y,'ro','MarkerEdgeColor','g','MarkerFaceColor','r','MarkerSize',8); hold on; A=zeros(N); for i=1:N for j=i+1:i+K/2 jj=j; if j>N jj=mod(j,N); end A(i,jj)=1; A(jj,i)=1; end end %WS小世界网络的代码 p=input('请输入随机化重连的概率p:'); for i=1:N for j=i+1:i+K/2 jj=j; if j>N jj=mod(j,N); end p1=rand(1,1); if p1 第二章复杂网络的基础知识 2.1 网络的概念 所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。 图2-1 网络类型示例 (a) 无权无向网络(b) 加权网络(c) 无权有向网络 如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。 图2-2 规则网络示例 (a) 一维有限规则网络(b) 二维无限规则网络 2.2 复杂网络的基本特征量 描述复杂网络的基本特征量主要有：平均路径长度（average path length ）、簇系数（clustering efficient ）、度分布（degree distribution ）、介数（betweenness ）等，下面介绍它们的定义。 2.2.1 平均路径长度（average path length ） 定义网络中任何两个节点i 和j 之间的距离l ij 为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter ）为网络中任意两个节点之间距离的最大值。即 }{max ,ij j i l D = （2-1） 定义网络的平均路径长度L 为网络中所有节点对之间距离的平均值。即 ∑∑-=+=-=111)1(2N i N i j ij l N N L （2-2） 其中N 为网络节点数，不考虑节点自身的距离。网络的平均路径长度L 又称为特征路径长度（characteristic path length ）。 网络的平均路径长度L 和直径D 主要用来衡量网络的传输效率。 2.2.2 簇系数（clustering efficient ） 假设网络中的一个节点i 有k i 条边将它与其它节点相连，这k i 个节点称为节点i 的邻居节点，在这k i 个邻居节点之间最多可能有k i (k i -1)/2条边。节点i 的k i 个邻居节点之间实际存在的边数N i 和最多可能有的边数k i (k i -1)/2之比就定义为节点i 的簇系数，记为C i 。即 ) 1(2-=i i i i k k N C (2-3) 整个网络的聚类系数定义为网络中所有节点i 的聚类系数C i 的平均值，记 复杂网络基础理论 第二章网络拓扑结构与静态特征 第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2 2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3 2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录 2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5 2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6 课题：WS小世界网络模型构造 姓名赵训 学号 2 班级计算机实验班 一、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); 小世界网络的研究现状与展望 !"#$%#&#’()#&#*%+",-(.*(-/’*’01/%#+*&(/2("#,3*445/%406#(7/%8 黄萍张许杰刘刚 （华东理工大学商学院管理科学与工程系上海%$$$&’） 摘要近年来，真实网络中小世界效应和无标度特性的发现激起了学术界对复杂网络的研究热潮，基于小世界网络的知识管理研究也得到了一定发展。在对小世界网络的研究背景、基础概念以及各个领域的研究进行简单综述的基础上，提出了其今后可能的发展趋势。 关键词复杂网络小世界网络流言传播无标度网络 现实世界中许许多多的复杂网络都是具有小世界或无尺度特征的复杂网络：从生物体中的大脑结构到各种新陈代谢网络，从()*+,)+*到---，从大型电力网络到全球交通网络，从科研合作网络到各种政治、经济、社会关系网络等等，数不胜数。各种网络的研究目前在世界上受到了高度的重视，形成了日益高涨的热潮，已成为一个极其重要而且富有挑战性的前沿科研方向。 !小世界网络研究背景及其基本概念 !.!复杂网络拓扑结构人们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构［%］。网络拓扑结构经过以下&个发展阶段：在最初的!$$多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示。到了!"世纪/$年代末，数学家们想出了一种新的构造网络的方法，即两个节点之间连边与否不再是根据一个概率决定的［!］，这样生成的网络叫做随机网络（01)234），在接下来的5$年里它一直被认为是描述真实系统最好的网络。直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络，对于复杂网络的研究标志着第三阶段的到来［5%］。 复杂网络拓扑结构的不确定性是复杂网络研究的基本问题。%$世纪中叶，6,237和0+)89突破传统图论，用随机图描绘了复杂网络拓扑。近年来研究发现，很多实际的复杂网络既不完全规则也不完全随机，而是介于完全规则和完全随机这两个极端之间，既具有类似规则网络的较大集聚系数，又具有类似于随机网络的较小平均路径长度，这就是小世界网络。人际关系网络中的“六度分离”就是小世界网络的经典例子。 大多数早期文献中都有关于六度分离的描述，!":’年，哈佛大学社会心理学家斯坦利?米尔格拉姆（;*1)<+8=9<> ?,14）作了这样的一个实验，他要求&$$多人发信把他的一封信寄到某市一个“目标”人。于是形成了发信人的链条，链上 的每个成员都力图把这封信寄给他们的朋友、家庭成员、商业同事或偶然认识的人，以便尽快到达目标人。实验结果是，一共:$个链条最终到达目标人，链条中平均步骤大约为:。人们把这个结果说成“六度分离”并广为传播［&!!!］。 应该注意到三种概念在当代对复杂网络的思考中占有重要地位。1.小世界的概念。它以简单的措辞描述了大多数网络尽管规模很大但是任意两个节点间却有一条相当短的路径的事实。@.集群即集聚度（A 关于小世界网络的文献综述 一、小世界网络概念方面的研究 Watts和Strogatz开创性的提出了小世界网络并给出了WS小世界网络模型。小世界网络的主要特征就是具有比较小的平均路径长度和比较大的聚类系数。所谓网络的平均路径长度，是指网络中两个节点之间最短路径的平均值。聚类系数被用来描述网络的局部特征，它表示网络中两个节点通过各自相邻节点连接在一起的可能性，以及衡量网络中是否存在相对稳定的子系统。规则网络具有大的特征路径长度和高聚类系数，随机网络则有短的特征路径长度和比较小的聚类系数[1]。 Guare于1967年在《今日心理学》杂志上提出了“六度分离”(Six Degrees of Separation) 理论，即“小世界现象”。该理论认为，在社交网络中存在短路径，即人们只要知道自己认识的人，就能很快地把信息传递到任何远方目标[2]。 .Stanleymilgram的邮件试验，后来的“培根试验”，以及1998年《纽约时代周刊》的关于莱温斯基的讽刺性游戏，都表现出：似乎在庞大的网络中各要素之间的间隔实际很“近”，科学家们把这种现象称为小世界效应[3]。研究发现，世界上任意两个人可以平均通过6个人联系在一起，人们称此现象为“六度分离” [2]。 二、小世界网络模型方面的研究 W-S模型定义了两个特征值：a.特征路径的平均长度L。它是指能使网络中各个结点相连的最少边长度的平均数，也就是上面说的小世界网络平均距离。b.集团化系数C。网络结点倾向于结成各种小的集团,它描述网络局部聚类特征。 稍后，Newman和WattS对上述的WS模型作了少许改动，提出了另一个相近但较好的(NW)小世界网络模型[5]，其做法是不去断开原来环形初始网络的任何一条边、而只是在随机选取的节点对之间增加一条边(这时，新连接的边很可能是长程边)。这一模烈比WS模型容易分析，因为它在形成过程中不会出现孤立的竹点簇。 其次，还有Monasson小世界网络模型[6]以及一些其它的变形模型包括BW 小世界网络模型等等[7]。 三、小世界网络应用方面的研究 ①、在生物学领域的应用 Wdt怡和StrogatZ证明疾病全球传播所需的时间和特征路径长度非常相似，只要在传播网络中加人一些捷径就可以使传播速度明显加快。运用病毒在小世界网络中的传播性质可推出信息在一个平均分离度为6的网络中传播要比在平均分离度为一百或一百万的网络中快得多[8]。 许多知名的生物网络表现出了小世界网络节点间的关连性。一般的小世界网络模型,也利用了网络的无向和无标度特性来展示网络中各节点之间的联系。这种网络模型能模拟一些神经网络的重要性质，例如，染色体结合的方向和标度。 [9][10]。 有学者研究了基于神经网络的有小世界结构的联想记忆模型。这一网络检索某一存储的模型的有效性展示了混乱的有限价值的阶段转换。更加常规化的网络很难恢复这个模型，而对混合的不对称的状态更有效。[11]。 ②、在博弈论方面的应用 function [DeD,aver_DeD]=Degree_Distribution(A) %% 求网络图中各节点的度及度的分布曲线 %% 求解算法：求解每个节点的度，再按发生频率即为概率，求P(k) %A————————网络图的邻接矩阵 %DeD————————网络图各节点的度分布 %aver_DeD———————网络图的平均度 N=size(A,2); DeD=zeros(1,N); for i=1:N % DeD(i)=length(find((A(i,:)==1))); DeD(i)=sum(A(i,:)); end aver_DeD=mean(DeD); if sum(DeD)==0 disp('该网络图只是由一些孤立点组成'); return; else figure; bar([1:N],DeD); xlabel('节点编号n'); ylabel('各节点的度数K'); title('网络图中各节点的度的大小分布图'); end figure; M=max(DeD); for i=1:M+1; %网络图中节点的度数最大为M,但要同时考虑到度为0的节点的存在性 N_DeD(i)=length(find(DeD==i-1)); % DeD=[2 2 2 2 2 2] end P_DeD=zeros(1,M+1); P_DeD(:)=N_DeD(:)./sum(N_DeD); bar([0:M],P_DeD,'r'); xlabel('节点的度 K'); ylabel('节点度为K的概率 P(K)'); title('网络图中节点度的概率分布图'); 平均路径长度 function [D,aver_D]=Aver_Path_Length(A) %% 求复杂网络中两节点的距离以及平均路径长度 %% 求解算法：首先利用Floyd算法求解出任意两节点的距离，再求距离的平均值得平均路 小世界网络及其性质 复杂网络是多主体系统的一个子集，对它的研究是计算经济学的一个重要研究领域。而贸易网络又是复杂网络在社会科学领域的一个子集，因此要讨论贸易网络，首先要关注关于复杂网络的一般性研究。在本章中，我们先介绍复杂网络研究的一个重要成果，即小世界模型，这为后面讨论贸易网络做准备。因为小世界模型只是一个纯粹的数学问题，并不包含某一学科的特殊含义，因此要首先讨论贸易网络的经济学意义，这是从一个简单的分工协调问题开始的。之后，我们进一步的追问，贸易网络是否也具有小世界这样一个普遍存在的性质。 1、多主体系统中的复杂网络 我们生活在各种各样的网络之中。在与同学、朋友、老师交往的时候，我们处于一个人际关系网络中；在我们使用各种电器的时候，我们处于一个电力网络中，很多发电厂、变电所、输电线构成了这个网络；我们去银行取钱的时候，便处于一个银行网络之中，而银行又可以与各种投资者，贷款人联系，这又是一个更大的网络。复杂网络是最近几年新兴起来的一个研究方向，如图 3.1 所示，复杂网络是多主体系统的一个子集，它里面还包括了社会关系网络（社会学）、神经网络（生物学）、计算机网络（计算机科学）、贸易网络（经济学）等等诸多的网络类别。复杂网络是多主体系统研究的一个重要分支，对社会网络、贸易网络的分析是计算经济学（ACE）的一个主要领域。 ACE 在社会科学角度对复杂网络的研究主要关注以下几个方面：（1）市场或 人际关系网络的拓扑结构究竟是什么样的。（2）这些网络结构的微观基础是什么，即如何从个体的行为出发，通过自下而上的建模涌现出这样的网络。（3）社会科学领域的网络与其它领域的网络能否找到一致的共性特征。社会科学可 小世界网络简介及MATLAB建模 1.简介 小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以用小世界网络来作为模型。因特网、公路交通网、神经网络都呈现小世界网络的特征。 小世界网络最早是由邓肯·瓦茨（Duncan Watts）和斯蒂文·斯特罗加茨（Steven Strogatz）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS模型），这也是最典型的小世界网络的模型。 由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW小世界网络模型，该模型是通过用“随机化加边”模式来取代WS小世界网络模型构造中的“随机化重连”。 在考虑网络特征的时候，使用两个特征来衡量网络：特征路径长度和聚合系数。 特征路径长度（characteristic path length）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。 聚合系数(clustering coefficient)：假设某个节点有k个边，则这k条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。 我们可以发现规则网络具有很高的聚合系数，大世界（large world，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（small world，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征路径长度很小。试验表明，少量的short cut的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个short cut的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的short cut的建立就能使整个网络不知不觉地变成小世界网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整， 复杂网络理论及其研究现状 复杂网络理论及其研究现状 【摘要】简单介绍了蓬勃发展的复杂网络研究新领域，特别是其中最具代表性的是随机网络、小世界网络和无尺度网络模型；从复杂网络的统计特性、复杂网络的演化模型及复杂网络在社会关系研究中的应用三个方面对其研究现状进行了阐述。 【关键词】复杂网络无标度小世界统计特性演化模型 一、引言 20世纪末，以互联网为代表的信息技术的迅速发展使人类社会步入了网络时代。从大型的电力网络到全球交通网络，从Internet 到WWW，从人类大脑神经到各种新陈代谢网络，从科研合作网络到国际贸易网络等，可以说，人类生活在一个充满着各种各样的复杂网络世界中。 在现实社会中，许多真实的系统都可以用网络的来表示。如万维网（WWW网路）可以看作是网页之间通过超级链接构成的网络；网络可以看成由不同的PC通过光缆或双绞线连接构成的网络；基因调控网络可以看作是不同的基因通过调控与被调控关系构成的网络；科学家合作网络可以看成是由不同科学家的合作关系构成的网络。复杂网络研究正渗透到数理科学、生物科学和工程科学等不同的领域，对复杂网络的定性与定量特征的科学理解，已成为网络时代研究中一个极其重要的挑战性课题，甚至被称为“网络的新科学”。 二、复杂网络的研究现状 复杂网络是近年来国内外学者研究的一个热点问题。传统的对网络的研究最早可以追溯到18世纪伟大数学家欧拉提出的著名的“Konigsberg七桥问题”。随后两百多年中，各国的数学家们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。规则网络过于理想化而无法表示现实中网络的复杂性，在20世纪60年代由Erdos和Renyi（1960）提出了随机网络。进入20世纪90年代，人们发现现实世界中绝大多数的网络既不是完全规则，也不是完全随机 小世界复杂网络模型研究 摘要：复杂网络在工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。通过高级计算机网络课程学习，本文介绍了复杂网络研究历史应用，理论描述方法及阐述对几种网络模型的理解。 1复杂网络的发展及研究意义 1.1复杂网络的发展历程 现实世界中的许多系统都可以用复杂网络来描述，如社会网络中的科研合作网、信息网络中的万维网、电力网、航空网，生物网络中的代谢网与蛋白质网络。 由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网；从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久；直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。 2复杂网络的基本概念 2.1网络的定义 自随机图理论提出至今，在复杂网络领域提出了许多概念和术语。网络（Network）在数学上以图（Graph）来表示，图的研究最早起源于18世纪瑞士著名数学家Euler的哥尼斯堡七桥问题。复杂网络可以用图论的语言和符号精确简洁地加以描述。图论不仅为数学家和物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。 网络的节点和边组成的集合。节点为系统元素，边为元素间的互相作用（关系）。若用图的方式表示网络，则可以将一个具体网络可抽象为一个由点集V和 小世界网络小世界网络简介及简介及MATLAB 建模 1.简介 小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以用小世界网络来作为模型。因特网、公路交通网、神经网络都呈现小世界网络的特征。 小世界网络最早是由邓肯·瓦茨（Duncan Watts ）和斯蒂文·斯特罗加茨（Steven Strogatz ）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS 模型），这也是最典型的小世界网络的模型。 由于WS 小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW 小世界网络模型，该模型是通过用“随机化加边”模式来取代WS 小世界网络模型构造中的“随机化重连”。 在考虑网络特征的时候，使用两个特征来衡量网络： 特征路径长度和聚合系数。 特征路径长度（characteristic path length ）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。 聚合系数(clustering coefficient)：假设某个节点有k 个边，则这k 条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。 我们可以发现规则网络具有很高的聚合系数，大世界（large world ，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（small world ，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征路径长度很小。试验表明，少量的short cut 的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个short cut 的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的short cut 的建立就能使整个网络不知不觉地变成小世界网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整， 第4卷第3期 复杂系统与复杂性科学 Vol.4No.3 2007年9月 C OMP LEX SYSTE M S AND COM P LEX I TY SC I E NCE Sep.2007 文章编号:1672-3813(2007)03-0001-09 开源软件的复杂网络分析及建模 郑晓龙,曾大军,李慧倩,毛文吉,王飞跃,戴汝为 (中国科学院自动化研究所复杂系统与智能科学重点实验室,北京100080) 摘要:开源软件现在变得越来越复杂。把开源软件看作复杂网络并进行研究,有助 于更好地理解软件系统。同时,开源软件是一种较为复杂的人工系统,通过对它们 的研究也可以推动复杂网络理论的应用。以一种基于源代码包的L inux操作系 统———Gent oo L inux操作系统为研究对象,我们把该系统中的软件包抽象成节点, 软件包之间的依赖关系抽象成边,以此建立复杂网络,并对其进行了分析。发现已 有模型不能很好地描述与预测Gent oo网的演化过程,因此,提出了一种新的演化模型。在该模型中,网络现有节点连接新节点的概率不但与现有节点的度有关系,而且也受到现有节点“年龄”的影响。还通过计算机仿真实验把仿真数据与Gent oo真实数据进行了比较,结果显示,新模型更为适合Gent oo网。 关键词:复杂网络;Gent oo;聚集系数;度分布;模型 中图分类号:N94;TP393;TP31文献标识码:A Ana lyz i n g and M odeli n g O pen Source Software a s Co m plex Networks ZHENG Xiao2l ong,ZENG Da2jun,L I Hui2qian,MAO W en2ji,WANG Fei2yue,DA I Ru2wei (The Key Laborat ory of Comp lex Syste m s and I ntelligence Science,I nstitute of Aut omati on, Chinese Academy of Sciences,Beijing100080,China) Abstract:Soft w are syste m s including those based on open2s ource code are becom ing increasingly com2 p lex.Studying the m as comp lex net w orks can p r ovide quantifiable measures and useful insights fr om the point of vie w of s oft w are engineering.I n the mean while,as one of the most comp lex man2made artifacts, they p r ovide a fruitful app licati on domain of comp lex syste m s theory.I n this paper,we analyze one of the most popular L inux meta packages/distributi ons called the Gent oo syste m.I n our analysis,we model s oft2 ware packages as nodes and dependencies a mong the m as arcs.Our e mp irical study shows that the resul2 ting Gent oo net w ork can not be exp lained by existing random graph models.This motivates our work in devel op ing a ne w model in which ne w nodes are connected t o old nodes with p r obabilities that depend not only on the degrees of the old nodes but als o the“ages”of these nodes.Thr ough si m ulati on,we de mon2 strate that our model has better exp lanat ory power than the existing models. Key words:comp lex net w orks;Gent oo;cluster coefficient;degree distributi on;model 收稿日期:2007-08-23 基金项目:国家自然科学基金委基金(60621001,60573078);科技部973项目(2006CB705500,2004CB318103);中国科学院、国家外国专家局,创新团队国际合作伙伴计划(2F05N01) 作者简介:郑晓龙(1982-),男,安徽人,博士研究生,研究方向为复杂网络与数据挖掘。 复杂网络度分布的研究 (1) 1. 复杂网络的研究对象........................................................................................ 1 2. 复杂网络的研究内容........................................................................................ 1 3. 复杂网络中的三个概念.................................................................................... 1 4. 复杂网络的几何量............................................................................................ 1 5. 社会网络与其它网络的判别指标.................................................................... 2 6. 随机网络－ER 模型 ......................................................................................... 2 7. 随机网络的研究宗旨........................................................................................ 2 8. 子图出现的临界概率........................................................................................ 3 9. 子图临界概率存在的证明................................................................................ 3 10. BA 模型与度的幂指分布 ................................................................................ 4 11. BA 模型构造的网络度符合幂指形式的证明 (4) 复杂网络度分布的研究 － 复杂网络度分布的研究 河北工大硕士论文 陈德伟 指导教师：何文辰 1. 复杂网络的研究对象 用来描述真实网络统计特征的物理量主要有度分布、平均路径长度、聚集系数、相关系数等，都是力求更加详细、精确的描述复杂的真实网络。寻找网络各种宏观统计性质的微观生成机制一直都是网络研究中一项极具意义而且也是极具挑战性的工作。现在人们已经对复杂网络的小世界性质和无标度特征的微观生成机制有了一定的认识，但是度的相关性、团体性质、分层结构等更为复杂的宏观统计性质的微观生成机制的探索还处于起步阶段。对不同结构复杂网络的鲁棒性和脆弱性(vulnerability)的研究也是一个具有广泛应用价值的课题。 2. 复杂网络的研究内容 目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。 3. 复杂网络中的三个概念 三种概念在当代对复杂网络的思考中占有重要地位。第一，小世界概念；第二，集群即集聚系数的概念；第三，幂律的度分布概念。 4. 复杂网络的几何量 直径：网络的直径是指任意两个顶点之间最短路径的最长长度(包含的边数)。 集聚系数：对于网络中的任意一个节点i 来说，其集聚系数i C 表示与i 相连的节点中任意两点之间相互连接的概率。它可定义如下：如果与节点i 相连的点的数目为i k ，则在这i k 个节点之间最多存在2/)1(-k k 条边，而实际存在的可能只有i E 条边，则得到i 的集聚系数i C 为 ) 1(2-= i i i i k k E C . 复杂网络的某些性质研究及其应用 自从Watts,Strogatz 1998年发现真实网络的小世界特性以来,复杂网络融合了图论、工程数学、计算机理论、社会科学等学科的有关理论与成果,已成为了一门单独的学科。经过十多年的研究,科学家们已经发现了一些典型复杂网络模型如小世界网络模型、无标度网络模型、确定性小世界网络模型等,同时也发现了这些典型网络模型的一些主要特性。 本文围绕复杂网络的小世界现象,针对典型复杂网络模型重点研究了网络节点度序列长度特性、电阻距离特性及其应用;基于代数图论中的凯莱图（Cayley）模型在随机化加边后也同样具有复杂网络的小世界特性,论文结合无线传感器网络和数据中心网络的应用需求,同时研究了基于代数图论的具有小世界特性的复杂网络模型及应用。论文主要成果如下:（1）在肖文俊等人提出复杂网络度序列长度新特性的基础上,论文从理论上证明了具有扩展幂律分布、泊松分布、指数分布的复杂网络模型的度序列长度的新特性:即度序列长度l与 log2N是同级别的结论,进一步完善了肖文俊等人的结论。 实验仿真结果及现实网络的数据验证了该结论的有效性。该结论从理论上解释了为什么现实世界的网络直径不大的问题,可以作为复杂网络的基本特性之一,同时论文提出了基于复杂网络的度序列长度的复杂网络模型。 针对复杂网络的搜索问题,论文完成了最短路径算法和最大度算法的仿真实验,结果表明在复杂网络中基于最大度的搜索算法相比基于最短路径的搜索算法更有效。（2）论文研究了复杂网络中的电阻距离特性及其在社团划分中应用的需求,提出了结合节点中心性指标与电阻距离的社团划分算法。 论文选择了节点度中心性、接近度指标、特征向量、聚类系数及最短路径等小世界网络
WS小世界网络模型的程序代码(matlab)
复杂网络的基础知识
复杂网络基础2(M.Chang)
课题：WS小世界网络模型构造
小世界网络的研究现状与展望
小世界网络综述
复杂网络模型的matlab实现
小世界网络及其性质
小世界网络简介及MATLAB建模
复杂网络理论及其研究现状
小世界复杂网络模型研究
看看挺有用的(小世界网络简介及MATLAB建模)
开源软件的复杂网络分析及建模
复杂网络度分布的研究
复杂网络的某些性质研究及其应用
相关主题
文本预览