图论与网络优化课程设计_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

%返回结果b为该小世界网络对应的邻接矩阵。

%由于WS小世界网络都是首先由规则的最近邻耦合网络生成的，故需要先调用ncn.m

function 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

b(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; %之外的另一个节点作为另一端的节点。 end

d = ceil((N-1)*rand); s = c(d,1); b(i,s) = 1; b(s,i) = 1; end end end end end

图-3即为N?20,K?6，p?0.5时的WS小世界网络的节点图。

图- 3：WS小世界网络

5. BA无标度网络的概述

20世纪末网络科学研究上有两个重要发现，一个是上面提到的WS小世界网络，另一个就是BA无标度网络。这类网络的节点的度没有明显的特征长度，其度分布都可以用适当的

5

幂律形式来较好地描述。现实生活中的Internet、WWW、科研合作网络以及蛋白质交互网络等众多不同领域的网络都是是某种形式上的BA无标度网络。

BA无标度网络的工作于1999年10月发表在《Science》上[3]，由美国Notre Dame大学物理系的Barabasi教授及其博士生Albert合作完成。

BA无标度网络模型构造算法： （1）. 增长：从一个具有M个节点的连通网络开始，每次引入一个新的节点并且连接

到m个已经存在的节点上，这里m≤M。

（2）. 优先连接：一个新节点与一个已经存在的节点i连接的概率?i与节点i的度ki之间满足如下关系

?ki??i。

jkjBA算法的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; end

for i = 1:M-1 %这里为简便起见，假使初始网络为完全连通网络 for j = (i+1):M b(i,j) = 1; b(j,i) = 1; end end

d = zeros(N,1); %建立一个存储每个节点度值的矩阵 for i = 1:M

d(i,1) = M-1; end

for i = M+1:N

mm = 0; %mm为当前步已经和新节点连接的旧节点个数 dd = d(1:i-1,1); Y为d的副本 while mm

6

dn = 0; %dn为节点度之和 for j = 1:i-1

dn = dn+dd(j,1); end

p = zeros(i-1,1); %p为节点累积度值占总度值百分比的矩阵 p(1,1) = dd(1,1)/dn; for j = 2:i-1

p(j,1) = p(j-1,1)+dd(j,1)/dn; end

r = rand;

for j = 1:i-1 %进行m次轮盘赌方法选择与新节点相连的节点 if r

d(i,1)=d(i,1)+1; d(j,1)=d(j,1)+1; dd(j,1) = 0; break; end end end end

示例：图-4即为M?3,m?2,N?20时的BA无标度网络的节点图

图- 4：BA无标度网络

7

2. 理论分析

从以上四种网络的构造算法出发，很容易得出其边数、度分布、平均路径长度、聚类系数的理论值，如下表：

表- 1

边数 度分布 平均度 NCN最近邻耦合网络 ER随机网络 ?M??pN(N?1)/2 WS小世界网络 BA无标度网络 (N?M)m?M(M?1)/2 NK/2 NK/2 介于规则网络与随机网络之间，近似泊松分布 Nf(NKp);K ln(NKp),NKp??1K2p?1,k?K ??0,k?KK 二项分布（N很大p很小时近似泊松分布）kkN?1?k CN?1p(1?p)幂律分布：2mk 2?3?k??p(N?1) 1N/2?[2m/K]平均(N?2)m?1路径N?长度 2K 23?CK/22CKLER?DER~InN/In?k? LlnN lnlnN聚类系数 3(K?2)?4(K?1) ?k?C?p? N?1 3(K?2)(1?p)3?O(1/N)4(K?1)C(lnN)2 N比较通过拓扑性质的表达式得出有意义的结论。例如：小世界网络的平均路径长度（记和分为L）绝不会小于同等规模的随机网络的L；无标度网络的L比同等规模的随机网析 络的L小得多。

8

3. 仿真分析

运用以上四个算法的Matlab代码生成规模为1000的4种网络模型，再用NodeXL分析其拓扑性质，通过比较得出结论。

表- 2

NCN（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)、从四个网络的聚类系数可以看出，规则网络、小世界网络和无标度具有相对较大的聚类系数。从我们的直观经验出发，现实生活中的网络往往都具有较大的聚类系数，这说明规则网络、小世界网络和无标度网络更接近于我们的现实生活。而随机网络聚类系数相对较小，可以猜想其具有较强的鲁棒性。

9

现在我们再看看改变网络规模N和参数m对BA无标度网络度分布的影响。

表- 3

N M=m 1 1000 1500 2000 3 5 7 结论见后。

4. 结论

本文所列举的四种基本网络模型，各有其特点和研究价值。通过以上网络模型的构造算法、Matlab实现、理论分析和仿真分析，可以得出以下基本结论：

（1）. 最近邻耦合网络具有规则的结构，是最容易被分析和理解的网络模型。它的许

多性质易于用纯数学上的解析方法来研究。现实网络的许多性质，都是介于完全规则网络与完全随机网络之间的，因此最近邻耦合网络看似简单，实则蕴含着无穷的奥妙。

（2）. ER随机网络是典型的完全随机网络。当网络规模一定时，它的各种拓扑性质

就完全由随机连边概率p决定了。当网络规模足够大时，即使p非常小（如表-2

中的ER随机图模型，p?0.002），整个网络却表现出较短的平均路径长度（4.03），即“小世界”特性；整个网络的度分布也倾向于二项分布。这些都说明随机中往往蕴含着规律性的东西，自然（或曰科学）给人的惊喜（惊奇）是无穷的。

（3）. WS小世界网络是由规则的最近邻耦合网络引入随机性得来的，所以它的许多

10

性质都介于完全规则网络与完全随机网络之间。然而它最为突出的“小世界”特性，最贴近于我们的现实生活，对它在各种形式下的拓扑性质的研究，具有极大的实用价值。

（4）. BA无标度网络引入了WS小世界网络所忽略的实际网络的另外两个重要特性，

即增长（Growth）特性和优先连接（Preferential attachment）特性。这使得BA无标度网络表现出幂律性的度分布，且该幂律性与网络规模N和参数m均无关的更为复杂的拓扑性质。对这些特性的研究，有利于人们理解并控制实际网络的演变与发展。受BA无标度网络的鲁棒性与脆弱性的启发，直接改善了人们对传染病的预防与控制机制。

5. 参考文献

[1] BOLLOBáS B. Random Graphs [M]. New York: Academic Press, 2nd ed.,2001.

[2] WATTS D J,STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature,

1998,393(6684):440-442.

[3] BARABáSI A-L,ALBERT R. Emergence of scaling in random networks [J]. Science,

1999,286(5439):509-512.

11

性质都介于完全规则网络与完全随机网络之间。然而它最为突出的“小世界”特性，最贴近于我们的现实生活，对它在各种形式下的拓扑性质的研究，具有极大的实用价值。

（4）. BA无标度网络引入了WS小世界网络所忽略的实际网络的另外两个重要特性，

即增长（Growth）特性和优先连接（Preferential attachment）特性。这使得BA无标度网络表现出幂律性的度分布，且该幂律性与网络规模N和参数m均无关的更为复杂的拓扑性质。对这些特性的研究，有利于人们理解并控制实际网络的演变与发展。受BA无标度网络的鲁棒性与脆弱性的启发，直接改善了人们对传染病的预防与控制机制。

5. 参考文献

[1] BOLLOBáS B. Random Graphs [M]. New York: Academic Press, 2nd ed.,2001.

[2] WATTS D J,STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature,

1998,393(6684):440-442.

[3] BARABáSI A-L,ALBERT R. Emergence of scaling in random networks [J]. Science,

1999,286(5439):509-512.

11

本文来源：https://www.bwwdw.com/article/wg53.html