图论与网络优化课程设计_matlab实现.

《图论与网络优化课程设计_matlab实现.》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论与网络优化课程设计四种基本网络（NCN、ER、WS、BA）的构造及其性质比较摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighborcouplednetwork）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和

2、分析。关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。11四种基本网络（NCN、ER、WS、BA）的构造及其性质比较1.概述1.网络科学的概述网络科学（NetworkScience）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而

3、丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighborcouplednetwork）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。2.最近邻耦合网络的概述如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量

4、研究的稀疏的规则网络模型。常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的个节点，其中每个节点都与它左右各个邻居节点相连，这里是一个偶数。这类网络的一个重要特征就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。NCN的Matlab实现：%functionb=ncn(N,K)%此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络%返回结果b为该最近邻耦合网络对应的邻接矩阵functionb=ncn(N,K)b=zeros(N);fori=1:Nforj=

5、(i+1):(i+K/2)ifj<=Nb(i,j)=1;b(j,i)=1;elseb(i,j-N)=1;11b(j-N,i)=1;endendendend图-1即为，时的最近邻耦合网络的节点图。图-1：最近邻耦合网络1.ER随机网络的概述与完全规则网络相对应的是完全随机网络，最为经典的模型是Erdos和Renyi于20世纪50年代末开始研究的现在称为ER随机图的模型。该模型既易于描述又可通过解析方法研究。在20世纪的后40年中，ER随机图理论一直是研究复杂网络拓扑的基本理论。关于随机图的理论较为全面的数学论述可参考Bollobas

6、的著作[1]。ER随机图的构造算法：（1）.初始化：给定个节点以及连边概率。（2）.随机连边：a)选择一对没有边相连的不同节点。b)生成一个随机数。c)如果，那么在这对节点之间添加一条边；否则就不添加边。d)重复步骤a)~c)，直到所有的节点对都被选择过一次。ER算法的Matlab实现：%functionb=er(N,p)%此函数生成一个有N个节点，节点连边概率p∈[0,1]的ER随机图%返回结果b为该ER随机图对应的邻接矩阵functionb=er(N,p)11b=zeros(N);fori=1:N-1forj=(i+1):Nr

7、=rand;ifr

8、发现：作为从完全规则网络向完全随机网络的过渡，只要在规则网络中引入少许的随机性就可以产生具有小世界特征的网络模型，现在称为WS小世界网络模型。WS小世界模型构造算法：（1）.从规则网络开始：给定一个含有N个节点的环状最近邻耦合网络，其中每个节点都与