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

图论与网络优化课程设计

四种基本网络（NCN、ER、WS、BA）

的构造及其性质比较

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

关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。

1

四种基本网络（NCN、ER、WS、BA）

的构造及其性质比较

1. 概述

1. 网络科学的概述

网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2. 最近邻耦合网络的概述

如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。

常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每个节点都与它左右各K/2个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。

NCN的Matlab实现：

%function b = ncn(N,K)

%此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵

function b = ncn(N,K) b=zeros(N); for i = 1:N

for j = (i+1):(i+K/2) if j<=N

b(i,j)=1; b(j,i)=1; else

b(i,j-N)=1;

2

b(j-N,i)=1; end end end end

图-1即为N?20，K?6时的最近邻耦合网络的节点图。

图- 1：最近邻耦合网络

3. ER随机网络的概述

与完全规则网络相对应的是完全随机网络，最为经典的模型是Erdos和Renyi于20世纪50年代末开始研究的现在称为ER随机图的模型。该模型既易于描述又可通过解析方法研究。在20世纪的后40年中，ER随机图理论一直是研究复杂网络拓扑的基本理论。关于随机图的理论较为全面的数学论述可参考Bollobas的著作[1]。

ER随机图G(N,p)的构造算法：

（1）. 初始化：给定N个节点以及连边概率p?[0,1]。 （2）. 随机连边：

a) 选择一对没有边相连的不同节点。

b) 生成一个随机数r?(0,1)。

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);

3

for i = 1:N-1

for j = (i+1):N r=rand; if r

b(i,j)=1; b(j,i)=1; end end end end

图-2即为N?20，p?0.3158时的完全随机网络的节点图。

图- 2：完全随机网络

4. WS小世界网络的概述

顾名思义，小世界网络具有明显聚类和小世界特征。从直观上看，毕竟大部分实际网络既不是完全规则也不是完全随机的：在现实生活中，人们通常认识他们的邻居和同事，但也可能有一些朋友远在异国他乡。

WS小世界网络的工作1998年6月在《Nature》[2]上发表，作者是美国Cornell大学的博士生Watts及其导师、非线性动力学专家Strogatz教授。Watts和Strogatz发现：作为从完全规则网络向完全随机网络的过渡，只要在规则网络中引入少许的随机性就可以产生具有小世界特征的网络模型，现在称为WS小世界网络模型。

WS小世界模型构造算法： （1）. 从规则网络开始：给定一个含有N个节点的环状最近邻耦合网络，其中每个节

点都与它左右相邻的K/2个节点相连，K是偶数。

（2）. 随机化重连：以概率p随机地重新连接网络中原有的每条边，即把每条边的

一个端点保持不变，另一个端点改取为网络中随机选择的一个节点。其中规定不得有重边和自环。

WS算法的Matlab实现代码： %function b = ws(N,K,p)

%此函数生成一个具有N个节点的WS小世界网络。

4