图论与网络优化课程设计四种基本网络（NCN、ER、WS、BA）的构造及其性质比较摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。
本文着重研究这几种网络的构造算法程序。
通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。
关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。
四种基本网络（NCN、ER、WS、BA）的构造及其性质比较1.概述1.网络科学的概述网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。
网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。
本文着重研究这几种网络的构造算法程序。
计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。
2.最近邻耦合网络的概述如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。
这是一个得到大量研究的稀疏的规则网络模型。
常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。
这类网络的一个重要特征个节点都与它左右各/2就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。
NCN的Matlab实现：%function b = ncn(N,K)%此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络%返回结果b为该最近邻耦合网络对应的邻接矩阵function b = ncn(N,K)b=zeros(N);for i = 1:Nfor j = (i+1):(i+K/2)if j<=Nb(i,j)=1;b(j,i)=1;elseb(i,j-N)=1;b(j-N,i)=1; end end end end图-1即为20N =，6K =时的最近邻耦合网络的节点图。
图- 1：最近邻耦合网络3. ER 随机网络的概述与完全规则网络相对应的是完全随机网络，最为经典的模型是Erdos 和Reny i 于20世纪50年代末开始研究的现在称为ER 随机图的模型。
该模型既易于描述又可通过解析方法研究。
在20世纪的后40年中，ER 随机图理论一直是研究复杂网络拓扑的基本理论。
关于随机图的理论较为全面的数学论述可参考Bollobas 的著作[1]。
ER 随机图(,)G N p 的构造算法：（1）. 初始化：给定N 个节点以及连边概率[0,1]p ∈。
（2）. 随机连边：a) 选择一对没有边相连的不同节点。
b) 生成一个随机数(0,1)r ∈。
c) 如果r p <，那么在这对节点之间添加一条边；否则就不添加边。
d) 重复步骤a) ~c)，直到所有的节点对都被选择过一次。
ER 算法的Matlab 实现： %function b = er(N,p)%此函数生成一个有N 个节点，节点连边概率p ∈[0,1]的ER 随机图 %返回结果b 为该ER 随机图对应的邻接矩阵function b = er(N,p) b = zeros(N);for i = 1:N-1for j = (i+1):N r=rand; if r<pb(i,j)=1; b(j,i)=1; end end end end图-2即为20N =，0.3158p =时的完全随机网络的节点图。
图- 2：完全随机网络4. WS 小世界网络的概述顾名思义，小世界网络具有明显聚类和小世界特征。
从直观上看，毕竟大部分实际网络既不是完全规则也不是完全随机的：在现实生活中，人们通常认识他们的邻居和同事，但也可能有一些朋友远在异国他乡。
WS 小世界网络的工作1998年6月在《Nature 》[2]上发表，作者是美国Cornell 大学的博士生Watts 及其导师、非线性动力学专家Strogatz 教授。
Watts 和Strogatz 发现：作为从完全规则网络向完全随机网络的过渡，只要在规则网络中引入少许的随机性就可以产生具有小世界特征的网络模型，现在称为WS 小世界网络模型。
WS 小世界模型构造算法： （1）. 从规则网络开始：给定一个含有N 个节点的环状最近邻耦合网络，其中每个节点都与它左右相邻的/2K 个节点相连，K 是偶数。
（2）. 随机化重连：以概率p 随机地重新连接网络中原有的每条边，即把每条边的一个端点保持不变，另一个端点改取为网络中随机选择的一个节点。
其中规定不得有重边和自环。
WS 算法的Matlab 实现代码： %function b = ws(N,K,p)%此函数生成一个具有N 个节点的WS 小世界网络。
%返回结果b 为该小世界网络对应的邻接矩阵。
%由于WS 小世界网络都是首先由规则的最近邻耦合网络生成的，故需要先调用ncn.mfunction b = ws(N,K,p) b = ncn(N,K); for i = 1:N-1 for j = i+1:N if b(i,j)~=0 if rand<pb(i,j) = 0;b(j,i) = 0; %随机重连，遍历原规则网络中的每一条边 c = 1:N-1;c = c'; %保持其一端的节点不变，产生一个随机数 for h = N-1:(-1):i %若该随机数小于p ，则随机选取除该端点 c(h,1) = h+1; %之外的另一个节点作为另一端的节点。
endd = ceil((N-1)*rand); s = c(d,1); b(i,s) = 1; b(s,i) = 1; end end end end end图-3即为20,6N K ==，0.5p =时的WS 小世界网络的节点图。
图- 3：WS 小世界网络5. BA 无标度网络的概述20世纪末网络科学研究上有两个重要发现，一个是上面提到的W S 小世界网络，另一个就是BA 无标度网络。
这类网络的节点的度没有明显的特征长度，其度分布都可以用适当的幂律形式来较好地描述。
现实生活中的Internet 、WWW 、科研合作网络以及蛋白质交互网络等众多不同领域的网络都是是某种形式上的BA 无标度网络。
BA 无标度网络的工作于1999年10月发表在《Science 》上[3]，由美国Notre Dam e 大学物理系的Barabas i 教授及其博士生Albert 合作完成。
BA 无标度网络模型构造算法： （1）. 增长：从一个具有M 个节点的连通网络开始，每次引入一个新的节点并且连接到m 个已经存在的节点上，这里m ≤M 。
（2）. 优先连接：一个新节点与一个已经存在的节点i 连接的概率i ∏与节点i 的度ik 之间满足如下关系ii jjk k ∏=∑。
BA 算法的Matlab 实现代码： %function b = ba(M,m,N)%此函数生成一个具有N 个节点的BA 无标度网络%M 为初始代连通网络的节点数、m 为每次引入的新节点连接到已存在的节点的个数 %其中m ≤M%返回结果b 为所求BA 无标度网络对应的邻接矩阵function b = ba(M,m,N) b = zeros(N);if M==1 M=2; endfor i = 1:M-1 %这里为简便起见，假使初始网络为完全连通网络 for j = (i+1):M b(i,j) = 1; b(j,i) = 1; end endd = zeros(N,1); %建立一个存储每个节点度值的矩阵 for i = 1:Md(i,1) = M-1; endfor i = M+1:Nmm = 0; %mm 为当前步已经和新节点连接的旧节点个数 dd = d(1:i-1,1); %dd 为d 的副本 while mm<m mm = mm+1;dn = 0; %dn 为节点度之和 for j = 1:i-1dn = dn+dd(j,1); endp = zeros(i-1,1); %p 为节点累积度值占总度值百分比的矩阵 p(1,1) = dd(1,1)/dn; for j = 2:i-1p(j,1) = p(j-1,1)+dd(j,1)/dn; endr = rand;for j = 1:i-1 %进行m 次轮盘赌方法选择与新节点相连的节点 if r<p(j,1) b(i,j)=1; b(j,i)=1;d(i,1)=d(i,1)+1; d(j,1)=d(j,1)+1; dd(j,1) = 0; break; end end end end示例：图-4即为3,2,20M m N ===时的BA 无标度网络的节点图图- 4：BA 无标度网络从以上四种网络的构造算法出发，很容易得出其边数、度分布、平均路径长度、聚类系数的理论值，如下表：表- 1ln ln ln NN2(ln )N N通过拓扑性质的表达式得出有意义的结论。
例如：小世界网络的平均路径长度（记比同等规模的随机网运用以上四个算法的Matlab代码生成规模为1000的4种网络模型，再用NodeXL分析其拓扑性质，通过比较得出结论。
表- 2NCN（1000,6）ER（1000，0.006）WS（1000,6,0.5）BA(3,3,1000)图像边数3000 3015 2992 2994度分布平均度6 6.030 5.984 5.998平均路径长度83.667 4.029739 4.280806 3.451422聚类系数0.6 0.006 0.089 0.04比较和分析(1)、在同等网络规模下，小世界网络的平均路径长度介于规则网络与随机网络之间，这也是小世界网络所以为“小世界”最为显著的特征；(2)、由表中度分布图可以看出：规则网络有规则的度分布、无标度网络明显倾向于幂律分布，即网络中绝大多数节点的度集中于某一值，但始终有少数节点的度在较远的其他值，这有点类似于现实生活中的“二八法则”、而随机网络和小世界网络的度分布都倾向于二项分布、正态分布或者泊松分布；(3)、从四个网络的聚类系数可以看出，规则网络、小世界网络和无标度具有相对较大的聚类系数。