图论与网络优化课程设计-Matlab实现

1图论与网络优化课程设计四种基本网络（NCN、ER、WS、BA）的构造及其性质比较摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighborcouplednetwork）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。2四种基本网络（NCN、ER、WS、BA）的构造及其性质比较1.概述1.网络科学的概述网络科学（NetworkScience）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighborcouplednetwork）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。2.最近邻耦合网络的概述如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每个节点都与它左右各/2K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。NCN的Matlab实现：%functionb=ncn(N,K)%此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络%返回结果b为该最近邻耦合网络对应的邻接矩阵functionb=ncn(N,K)b=zeros(N);fori=1:Nforj=(i+1):(i+K/2)ifj=Nb(i,j)=1;b(j,i)=1;elseb(i,j-N)=1;3b(j-N,i)=1;endendendend图-1即为20N，6K时的最近邻耦合网络的节点图。图-1：最近邻耦合网络3.ER随机网络的概述与完全规则网络相对应的是完全随机网络，最为经典的模型是Erdos和Renyi于20世纪50年代末开始研究的现在称为ER随机图的模型。该模型既易于描述又可通过解析方法研究。在20世纪的后40年中，ER随机图理论一直是研究复杂网络拓扑的基本理论。关于随机图的理论较为全面的数学论述可参考Bollobas的著作[1]。ER随机图(,)GNp的构造算法：（1）.初始化：给定N个节点以及连边概率[0,1]p。（2）.随机连边：a)选择一对没有边相连的不同节点。b)生成一个随机数(0,1)r。c)如果rp，那么在这对节点之间添加一条边；否则就不添加边。d)重复步骤a)~c)，直到所有的节点对都被选择过一次。ER算法的Matlab实现：%functionb=er(N,p)%此函数生成一个有N个节点，节点连边概率p∈[0,1]的ER随机图%返回结果b为该ER随机图对应的邻接矩阵functionb=er(N,p)b=zeros(N);4fori=1:N-1forj=(i+1):Nr=rand;ifrpb(i,j)=1;b(j,i)=1;endendendend图-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实现代码：%functionb=ws(N,K,p)%此函数生成一个具有N个节点的WS小世界网络。5%返回结果b为该小世界网络对应的邻接矩阵。%由于WS小世界网络都是首先由规则的最近邻耦合网络生成的，故需要先调用ncn.mfunctionb=ws(N,K,p)b=ncn(N,K);fori=1:N-1forj=i+1:Nifb(i,j)~=0ifrandpb(i,j)=0;b(j,i)=0;%随机重连，遍历原规则网络中的每一条边c=1:N-1;c=c';%保持其一端的节点不变，产生一个随机数forh=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;endendendendend图-3即为20,6NK，0.5p时的WS小世界网络的节点图。图-3：WS小世界网络5.BA无标度网络的概述20世纪末网络科学研究上有两个重要发现，一个是上面提到的WS小世界网络，另一个就是BA无标度网络。这类网络的节点的度没有明显的特征长度，其度分布都可以用适当的6幂律形式来较好地描述。现实生活中的Internet、、科研合作网络以及蛋白质交互网络等众多不同领域的网络都是是某种形式上的BA无标度网络。BA无标度网络的工作于1999年10月发表在《Science》上[3]，由美国NotreDame大学物理系的Barabasi教授及其博士生Albert合作完成。BA无标度网络模型构造算法：（1）.增长：从一个具有M个节点的连通网络开始，每次引入一个新的节点并且连接到m个已经存在的节点上，这里m≤M。（2）.优先连接：一个新节点与一个已经存在的节点i连接的概率i与节点i的度ik之间满足如下关系iijjkk。BA算法的Matlab实现代码：%functionb=ba(M,m,N)%此函数生成一个具有N个节点的BA无标度网络%M为初始代连通网络的节点数、m为每次引入的新节点连接到已存在的节点的个数%其中m≤M%返回结果b为所求BA无标度网络对应的邻接矩阵functionb=ba(M,m,N)b=zeros(N);ifM==1M=2;endfori=1:M-1%这里为简便起见，假使初始网络为完全连通网络forj=(i+1):Mb(i,j)=1;b(j,i)=1;endendd=zeros(N,1);%建立一个存储每个节点度值的矩阵fori=1:Md(i,1)=M-1;endfori=M+1:Nmm=0;%mm为当前步已经和新节点连接的旧节点个数dd=d(1:i-1,1);%dd为d的副本whilemmmmm=mm+1;7dn=0;%dn为节点度之和forj=1:i-1dn=dn+dd(j,1);endp=zeros(i-1,1);%p为节点累积度值占总度值百分比的矩阵p(1,1)=dd(1,1)/dn;forj=2:i-1p(j,1)=p(j-1,1)+dd(j,1)/dn;endr=rand;forj=1:i-1%进行m次轮盘赌方法选择与新节点相连的节点ifrp(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;endendendend示例：图-4即为3,2,20MmN时的BA无标度网络的节点图图-4：BA无标度网络82.理论分析从以上四种网络的构造算法出发，很容易得出其边数、度分布、平均路径长度、聚类系数的理论值，如下表：表-1NCN最近邻耦合网络ER随机网络WS小世界网络BA无标度网络边数/2NK(1)/2MpNN/2NK()(1)/2NMmMM度分布1,0,kKkK二项分布（N很大p很小时近似泊松分布）11(1)kkNkNCpp介于规则网络与随机网络之间，近似泊松分布幂律分布：232mk平均度K(1)kpN平均路径长度/211[2/](2)2NmmKNNK~/ERERLDInNInk2();ln(),1NfNKpKNKpNKpKplnlnlnNLN聚类系数2/2233(2)4(1)KKCCKK1kCpN33(2)(1)(1/)4(1)KpONK2(ln)NCN比较和分析通过拓扑性质的表达式得出有意义的结论。例如：小世界网络的平均路径长度（记为L）绝不会小于同等规模的随机网络的L；无标度网络的L比同等规模的随机网络的L小得多。93.仿真分析运用以上四个算法的Matlab代码生成规模为1000的4种网络模型，再用NodeXL分析其拓扑性质，通过比较得出结论。表-2NCN（1000,6）ER（1000，0.006）WS（1000,6,0.5）BA(3,3,1000)图像边数3000301529922994度分布平均度66.0305.9845.998平均路径长度83.6674.0297394.2808063.451422聚类系数0.60.0060.0890.04比较和分析(1)、在同等网络规模下，小世界网络的平均路径长度介于规则网络与随机网络之间，这也是小世界网络所以为“小世界”最为显著的特征；(2)、由表中度分布图可以看出：规则网络有规则的度分布、无标度网络明显倾向于幂律分布，即网络中绝大多数节点的度集中于某一值，但始终有少数节点的度在较远的其他值，这有点类似于现实生活中的“二八法则”、而随机网络和小世界网络的度分布都倾向于二项分布、正态分布或者泊松分布；(3)、从四个网络的聚类系数可以看出，规则网络、小世界网络和无标度具有相对较大的聚类系数。从我们的直观经验出发，现实生活中的网络往往都具有较大的聚类系数，这说明规则网络、小世界网络和无标度网络更接近于我们的现实生活。而随机网络聚类系数相对较小，可以猜想其具有较强的鲁棒性。10现在我们再看看改变网络规模N和参数m对BA无标度网络度分布的影响。表-3NM=m1000150020001357结论见后。4.结论本文所列举的四种基本网络模型，各有其特点和研究价值。通过以上网络模型的构造算法、Matlab实现、理论分析和仿真分析，可以得出以下基本结论：（1）.最近邻耦合网络具有规则的结构，是最容易被分析和理解的网络模型。它的许多性质易于用纯数学上的解析方法来研究。现实网络的许多性质，都是介于完全规则网络与完全随机网络之间的，因此最近邻耦合网络看似简单，实则蕴含着无穷的奥妙。（2）.ER随机网络是典型的完全随机网络。当网络规模一定时，它的各种拓扑性质就完全由随机连边概率p决定了。当网络规模足够大时，即使p非常小（如表-2中的ER随机图模型，0.002p），整个网络却表现出较短的平均路径长度（4.03），即“小世界