复杂网络的基础知识

1、第二章复杂网络的基础知识1 第二章复杂网络的基础知识2.1 网络的概念所谓“网络” （networks） ，实际上就是节点（ node）和连边（ edge）的集合。如果节点对（i，j）与 （j，i）对应为同一条边， 那么该网络为无向网络 （undirected networks） ，否则为有向网络（ directed networks） 。如果给每条边都赋予相应的权值，那么该网络就为加权网络 （weighted networks ） ， 否则为无权网络 （unweighted networks） ，如图 2-1 所示。图 2-1 网络类型示例(a) 无权无向网络(b) 加权网络(c) 无权有向

2、网络如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks） ，如图 2-2 所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks ） 。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks） 。图 2-2 规则网络示例(a) 一维有限规则网络(b) 二维无限规则网络第二章复杂网络的基础知识2 2.2 复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度（average path length） 、簇系数（ clustering ef

3、ficient） 、度分布（ degree distribution） 、介数（ betweenness ）等，下面介绍它们的定义。2.2.1 平均路径长度 （average path length ）定义网络中任何两个节点i 和 j 之间的距离 lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter）为网络中任意两个节点之间距离的最大值。即max,ijjild（2-1）定义网络的平均路径长度l 为网络中所有节点对之间距离的平均值。即111)1(2ninijijlnnl（2-2）其中 n 为网络节点数，不考虑节点自身的距离。网络的平均路径长度l又称为

4、特征路径长度（ characteristic path length ） 。网络的平均路径长度l 和直径 d 主要用来衡量网络的传输效率。2.2.2 簇系数 （clustering efficient）假设网络中的一个节点i 有 ki条边将它与其它节点相连， 这 ki个节点称为节点 i 的邻居节点，在这ki个邻居节点之间最多可能有ki(ki1)/ 2 条边。节点 i的 ki个邻居节点之间实际存在的边数ni和最多可能有的边数 ki(ki1)/ 2 之比就定义为节点 i 的簇系数，记为 ci。即)1(2iiiikknc(2-3) 整个网络的聚类系数定义为网络中所有节点i 的聚类系数 ci的平均值，

5、记第二章复杂网络的基础知识3 为 c。即niicnc11（2-4）显然， 0 c 1 之间。当 c=0 时，说明网络中所有节点均为孤立节点，即没有任何连边。当c=1 时，说明网络中任意两个节点都直接相连，即网络是全局耦合网络。2.2.3 度分布 （degree distribution）网络中某个节点 i 的度 ki定义为与该节点相连接的其它节点的数目，也就是该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点i 的度ki的的平均值称为网络的（节点）平均度，记为。即niiknk11（2-5）网络中节点的分布情况一般用度分布函数p(k)来描述。度分布函数 p(k)表示在网络中任意选取

6、一节点，该节点的度恰好为k 的概率。即niikknkp1)(1)(（2-6）通常，一个节点的度越大， 意味着这个节点属于网络中的关键节点，在某种意义上也越“重要”。2.2.4 介数（betweenness ）节点 i 的介数定义为网络中所有的最短路径中，经过节点i 的数量。用 bi表示。即nmin m,ggbnmnmnimi,（2-7）式中 gmn为节点 m 与节点 n 之间的最短路径数， gmin为节点 m 与节点 n 之第二章复杂网络的基础知识4 间经过节点 i 的最短路径数。节点的介数反映了该节点在网络中的影响力。描述网络结构的特征量还有很多，这里就不一一介绍， 在使用到它们的地方再给出

7、详细的说明。2.3 复杂网络的基本模型人们在对不同领域内的大量实际网络进行广泛的实证研究后发现：真实网络系统往往表现出小世界特性、 无标度特性和高聚集特性。 为了解释这些现象，人们构造了各种各样的网络模型，以便从理论上揭示网络行为与网络结构之间的关系，进而考虑改善网络的行为。下面介绍几类基本的网络模型。2.3.1 规则网络 （regular network ）常见的规则网络有三种：全局耦合网络（globally coupled network） 、最近邻耦合网络（ nearest-neighbor coupled network）和星型网络模型（ star coupled network） ，

8、如图 2-3 所示。图 2-3 三种典型的规则网络(a) 全局耦合网络(b) 最近邻耦合网络(c) 星型网络图 2-3 （a） 所示为一个含有 n 个节点的全局耦合网络。 网络中共有 n(n 1)/ 2条边，其平均路径长度l=1（最小） ，簇系数 c=1 （最大） 。度分布 p(k)为以 n 1为中心的 函数。模型的优点：能反映实际网络的小世界特性和大聚类特性。模型的缺点： 不能反映实际网络的稀疏特性。因为一个具有 n 个节点的全第二章复杂网络的基础知识5 局耦合网络的边的数目为o(n2)，而实际网络的边的数目一般是o(n)。图 2-3（b）所示为一个含有n 个节点的最近邻耦合网络。 网络中的

9、每个节点只和它周围的邻居节点相连，其中每个节点都与它左右各k2 个邻居节点相连（ k 为偶数） 。对于固定的 k 值，网络的平均路径长度为：)(2nknl（2-8）对于较大的 k 值，最近邻耦合网络的簇系数为：43)1(4)2(3kkc（2-9）度分布 p(k)为以 k 为中心的 函数。模型的优点：能反映实际网络的大聚类特性和稀疏特性。模型的缺点：不能反映实际网络的小世界特性。图 2-3（c）所示为一个具有n 个节点的星型网络。网络有一个中心节点，其余 n 1 个节点都只与这个中心节点相连，且它们彼此之间不连接。网络的平均路径长度：)(2)1()1(22nnnnl(2-10) 网络的簇系数为：

10、)(11nnnc(2-11) 网络的度分布为：第二章复杂网络的基础知识6 其它0)1()1(1)(11nkkkpnn(2-12) 规定：如果一个节点只有一个邻居，那么该节点的簇系数为1。也有些文献规定只有一个邻居的节点的簇系数为0，若依此定义，则星型网络的簇系数为 0。模型的优点：能反映实际网络的小世界特性和稀疏特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.2 er 随机网络 （random network ）该模型由匈牙利数学家ed?s和 r nyi 在上世纪 50 年代最先提出， 所以被人们称为 er随机网络模型。 er 随机网络的构造有两种方法。第一种方法：定义有标记的n 个节

11、（网络中的节点总数） ，并且给出整个网络的边数 n， 这些边的选取采用从所有可能的n(n 1)2 种情况中随机选取。第二种方法： 给定有标记的 n 个节点，以一定的随机概率p 连接所有可能出现的 n(n 1)2 种连接，假设最初有 n 个孤立的节点， 每对节点以随机概率p 进行连接。如图2-4 所示。图 2-4 er 随机网络的演化示意图（a）p=0 时，给定 10 个孤立节点；（b）（ c）p=0.1，0.15 时，生成的随机图er随机网络模型具有如下基本特性：（1）涌现或相变第二章复杂网络的基础知识7 如果当 n 时产生一个具有性质q 的 er 随机图的概率为1，那么几乎每一个 er随机图

12、都具有性质q。以连通性为例，若当连接概率p 达到某个临界值 pc (lnn)n 时，整个网络连通起来，那么以概率p 生成的每一个网络几乎都是连通的，否则，当p 小于该临界值时，几乎每一个网络都是非连通的。（2）度分布对于一个给定连接概率为p 的随机网络， 若网络的节点数 n 充分大，则网络的度分布接近泊松（ poission）分布，如图 2-5 所示。kkknkknekkppckp!)1()(11（2-13）式中=p(n 1) pn 表示 er随机网络的平均度。图 2-5 er 随机网络的度分布（取自文献 ）（3）平均路径长度假定网络的平均路径长度为l，从网络的一端走到网络的另一端，总步数大概

13、为 l。由于 er随机网络的平均度为 k，对于任意一个节点，其一阶邻居的数目为 k，二阶邻居的数目为 k2，以此类推，当经过l 步后遍历了网络的所有节点， 因此对于规模为 n 的随机网络， 有kl=n。由此可以得到网络的平均路径长度为：knpnnllnln)ln(ln（2-14）第二章复杂网络的基础知识8 由于 lnn 的值随 n 增长较慢， 所以规模很大的 er 随机网络具有很小的平均路径长度，如图2-6 所示。图 2-6 er 随机网络的平均路径长度与网络规模的关系（取自文献 ）（4）簇系数在 er随机网络中， 由于任何两个节点之间的连接概率p 都相等，所以 er随机网络的聚类系数为：nk

14、pc（2-15）可见，当网络规模n 固定时，簇系数随着网络节点平均度的增加而增加，如图 2-7 所示。当网络节点平均度固定时，簇系数随着网络规模n 的增加而下降，如图2-8 和所示。显然，当n 较大时， er 随机网络的簇系数很小。第二章复杂网络的基础知识9 图 2-7 （n=104）er 随机网络的簇系数与连接概率的关系（取自文献 ）图 2-8 （p=0.0015）er 随机网络的簇系数与网络规模的关系（取自文献 ）模型的优点：能反映实际网络的小世界特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.3 小世界网络 （small-world network）作为从完全规则网络向完全随机网

15、络的过渡，美国学者watts 和 strogatz第二章复杂网络的基础知识10 于 1998 年设计了一个具有小的平均路径长度和大的聚类系数的小世界网络模型（small-world network） ，简称 ws 小世界网络模型。ws 小世界网络模型的构造算法：（1）从规则网络开始：考虑一个含有n 个节点的最近邻耦合网络，它们围成一个环，其中每一个节点都与它左右相邻的各k/ 2 个节点相连，k 是偶数。（2）随机化重连：以概率p 随机地重新连接网络中的每一条边，即将连边的一个端点保持不变， 而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每个节点

16、不能有边与自身相连。为了保证网络具有稀疏性，要求nk，这样构造出来的网络模型具有较高聚类系数。 而随机化重连过程大大减小了网络的平均路径长度，使网络模型具有小世界特性。当p 取值较小时，重连过程对网络的聚类系数影响不大。当p时，模型退化为规则网络，当p时，模型退化为随机网络。通过调节p的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图2-9 所示. 图 2-9 ws 小世界网络模型（取自文献 ）ws 小世界网络模型的其聚类系数和平均路径长度可以看作是重连概率p的函数，分别记为c(p)和 l(p)，它们的变化规律如图2-10 所示。在某个 p 值范围内，ws 网络模型可以得到既有较短的平

17、均路径长度（小世界特性），又有较高聚类系数（高聚集特性） 。图 2-10 中 p 值在 0.0l 附近的网络即兼具这两方一面的特征。第二章复杂网络的基础知识11 图 2-10 ws 小世界网络模型的簇系数和平均路径长度随p 的变化关系（取自文献 ）由于在 ws 小世界网络模型的随机化重连过程中有可能破坏网络的连通性。为了避免出现因重连而造成的孤立子网，美国学者newman与 watts合作于 1999 年提出了用“随机化加边”取代“随机化重连”的小世界网络模型，称“nw 小世界模型”。nw 小世界网络模型的构造算法：（1）从规则网络开始：考虑一个含有n 个节点的最近邻耦合网络，它们围成一个环，

18、其中每一个节点都与它左右相邻的各k/2 个节点相连，k 是偶数。（2）随机化加边：以概率p 在随机选取的一对节点之间加上一条边。其中规定，任意两个不同的节点之间至多只能加一条边，并且每个节点不能有边与自身相连。当 p=0 时，模型退化为规则网络， 当 p=1 时，模型退化为随机网络。 通过调节 p 的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图 2-11所示。在 p 较小时， nw 模型具有与 ws 模型类似的特性。第二章复杂网络的基础知识12 图 2-11 nw 小世界网络模型（取自文献 ）小世界网络模型具有如下基本特性：（1）簇系数ws 小世界网络的聚类系数为：3)1()1(4

19、)2(3)(pkkpc(2-16) nw 小世界网络的聚类系数为：)2(4)1(4)2(3)(pkpkkpc(2-17) （2）平均路径长度至今为止，还没有人得到关于ws 小世界网络模型的平均路径长度的精确解析表达式， newman，moore 和 watts 分别用重整化群和序列展开方法得到如下近似公式：)2/(2)(nkpfknpl(2-18) 式中 f(u)为一普适标度函数，且满足：1/)(ln1)(uuuuconstuf(2-19) 目前为止，还没有f(u)的精确表达式， newman 等人基于平均场方法给出了如下的近似表达式：第二章复杂网络的基础知识13 2221)(2xxarcta

20、nhxxxf(2-20) （3）度分布对于 ws 小世界网络，当 kk/2 时有：22222)!2/()2/()1()(2/),min(0pkkkkkenkkpkppckpnknnknkn(2-21) 当 kk/ 2 时，p(k)=0。对于 nw 小世界网络，每个节点的度至少为k，因此当 kk 时，一个随机选取的节点的度为k 的概率为：kknkknkknkpnkpckp1)(2-22) 当 kk 时，p(k)=0。类似 er 随机网络模型， ws 小世界网络模型也是所有节点的度都近似相等的均匀网络。综上所述， er 随机网络、 ws 小世界网络和nw 小世界网络的度分布可近似用 poisson

21、分布来表示， 该分布在度的平均值 k处有一峰值， 然后按指数快速衰减。这类网络被称为均匀网络（homogeneous network）或指数网络（exponential network ） 。2.3.4 无标度网络 （scale-free network ）近年来，大量的实证研究表明，许多大规模真实网络（如www、internet以及新陈代谢网络等）的度分布函数都是呈幂律分布的形式：p(k) k。在这样的网络中， 大部分节点的度都很小， 但也有一小部分节点具有很大的度，没有一个特征标度。由于这类网络的节点的连接度并没有明显的特征标度，故称为 “无标度网络”。 为了解释实际网络中幂律分布产生的机

22、理，barab si 和 albert 在 1999第二章复杂网络的基础知识14 年提出了一个无标度网络模型，称为 ba 无标度模型。 该模型的构造主要基于现实网络的两个内在机制： 增长机制： 大多数真实网络是一个开放系统，随着时间的推移， 网络规模将不断增大， 即网络中的节点数和连边数是不断增加的。择优连接：新增加的节更倾向于与那些具有较高连接度的节点相连。也就是富人更富的观点（ rich get richer） 。ba 无标度网络模型的构造算法：（1）增长：在初始时刻，假定网络中己有m0个节点，在以后的每一个时间步长中，增加一个连接度为m 的节点（ mm0） ，新增节点与网络中已经存在的 m 个不同的节点相连，且不存在重复连接。（2）优先连接：在选择新节点的连接点时，一个新节点与一个已经存在的节点 i 相连的概率 i与节点 i 的度 ki成正比：jjiikk（2-23）经过 t 步后，这种算法能够产生一个含有n=t+m0个节点、mt 条边的网络。如图 2-12 所示的是 m=m0=2 时，ba 网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已经存在的两个节点相连。图 2-12 ba 无标度网络的演化过