复杂网络的基础知识

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

2、络”(regularnetworks)，如图 2-2 所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络” (random network。如果节点按照某种(自)组织原则的方式 连边，将演化成各种不同的网络，称为“复杂网络”(complex networks)0(a)(b)图 2-2 规则网络示例(b)二二(a) 一维有限规则网络(b)二维无限规则网络2.2 复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度(average path len gth)、簇系数(clustering efficient)度分布(degree distribution)介数(betw

3、eennesS等，下面介绍它们的定义2.2.1 平均路径长度 (average path len gth定义网络中任何两个节点 i 和 j 之间的距离 lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径(diameter)为网络中任意两个节点之间距离的最大值。即D = max lji, j定义网络的平均路径长度 L 为网络中所有节点对之间距离的平均值。即(2-2)其中 N 为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度(characteristic path length)网络的平均路径长度 L 和直径 D 主要用来衡量网络的传输效率。

4、2.2.2 簇系数(clustering efficient)假设网络中的一个节点 i 有 ki条边将它与其它节点相连，这 ki个节点称为 节点 i的邻居节点，在这 ki个邻居节点之间最多可能有 ki(ki-1)/2 条边。节点 i 的 ki个邻居节点之间实际存在的边数 Ni和最多可能有的边数 ki(ki-1)/2 之比就 定义为节点 i 的簇系数，记为 Ci。即(2-1)2NiCiki(ki-1)(2-3)整个网络的聚类系数定义为网络中所有节点i 的聚类系数 Ci的平均值，记为 C。即C=NCi(2-4)i =1显然，0 C 1 之间。当 C=0 时，说明网络中所有节点均为孤立节点，即 没有

5、任何连边。当 C=1 时，说明网络中任意两个节点都直接相连，即网络是全 局耦合网络。2.2.3 度分布(degree distributen)网络中某个节点 i 的度 ki定义为与该节点相连接的其它节点的数目，也就是 该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点 i 的度 ki的的平均值称为网络的(节点)平均度，记为 。即1Nk kjNi=i在网络中任意选取一节点，该节点的度恰好为k 的概率。即1NP(k)(k_kj)Ny通常，一个节点的度越大，意味着这个节点属于网络中的关键节点， 在某种 意义上也越“重要”。2.2.4 介数(betweennesS节点 i 的介数定义为网

6、络中所有的最短路径中，经过节点表示。即式中 gmn为节点 m 与节点 n 之间的最短路径数，gmin为节点 m 与节点 n 之(2-5)网络中节点的分布情况一般用度分布函数P(k)来描述。度分布函数 P(k)表示(2-6)i 的数量。用 BiBigmi nm,ngmn(2-7)间经过节点 i 的最短路径数节点的介数反映了该节点在网络中的影响力。描述网络结构的特征量还有很多， 这里就不一一介绍，在使用到它们的地 方再给出详细的说明。2.3 复杂网络的基本模型人们在对不同领域内的大量实际网络进行广泛的实证研究后发现：真实网络系统往往表现出小世界特性、无标度特性和高聚集特性。为了解释这些现象， 人们

7、构造了各种各样的网络模型， 以便从理论上揭示网络行为与网络结构之间 的关系，进而考虑改善网络的行为。下面介绍几类基本的网络模型。2.3.1 规则网络(regular network)常见的规则网络有三种：全局耦合网络(globally coupled network)、最近 邻耦合网络(nearest-neighbor coupled network 和星型网络模型(star coupled network)，如图 2-3 所示。(a)(b)图 2-3三种典型的规则网络(a)全局耦合网络(b)最近邻耦合网络图2-3(a)所示为一个含有N个节点的全局耦合网络。 网络中共有N(N-1)/2 条边，

8、其平均路径长度 L=1 (最小)，簇系数 C=1 (最大)。度分布 P(k)为以 N-1 为中心的 S函数。模型的优点：能反映实际网络的小世界特性和大聚类特性。模型的缺点：不能反映实际网络的稀疏特性。因为一个具有 N 个节点的全(c)星型网络局耦合网络的边的数目为 0(N2)，而实际网络的边的数目一般是 0(N)图 2-3 (b)所示为一个含有 N 个节点的最近邻耦合网络。网络中的每个节 点只和它周围的邻居节点相连，其中每个节点都与它左右各 K/2 个邻居节点 相连(K 为偶数)。对于固定的 K 值，网络的平均路径长度为:NL(Nr)2K(2-8)对于较大的 K 值，最近邻耦合网络的簇系数为:

9、C 3(K -2)3C 二-4(K -1)4(2-9)度分布 P(k)为以 K 为中心的 S函数。模型的优点：能反映实际网络的大聚类特性和稀疏特性。模型的缺点：不能反映实际网络的小世界特性。图 2-3 (c)所示为一个具有 N 个节点的星型网络。网络有一个中心节点, 其余 N-1 个节点都只与这个中心节点相连，且它们彼此之间不连接。网络的平均路径长度：2(N 1)L =22 (N )N(N -1)网络的簇系数为：(2-10)(N：)(2-11)网络的度分布为:1-善(K=1)P(K) = (K = N1)(2-12)o其它规定: 如果一个节点只有一个邻居，那么该节点的簇系数为1。也有些文献规定

10、只有一个邻居的节点的簇系数为 0,若依此定义，则星型网络的簇系数 为 0。模型的优点：能反映实际网络的小世界特性和稀疏特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.2 ER 随机网络(random network)该模型由匈牙利数学家 Ed?s 和 Renyi 在上世纪 50 年代最先提出，所以被 人们称为 ER 随机网络模型。ER 随机网络的构造有两种方法。第一种方法：定义有标记的 N 个节(网络中的节点总数)，并且给出整个 网络的边数 n,这些边的选取采用从所有可能的 N(N-1)/2 种情况中随机选取。第二种方法：给定有标记的 N 个节点，以一定的随机概率 p 连接所有可能 出

11、现的 N(N-1)/2 种连接，假设最初有 N 个孤立的节点，每对节点以随机概率 p 进行连接。如图 2-4 所示。图 2-4 ER 随机网络的演化示意图(a) p=0 时，给定 10 个孤立节点；(b)(c) p=0.1，0.15 时，生成的随机图ER 随机网络模型具有如下基本特性：(1)涌现或相变(c)如果当 N-x时产生一个具有性质 Q 的 ER 随机图的概率为 1,那么几乎 每一个ER 随机图都具有性质 Q。以连通性为例，若当连接概率 p 达到某个临 界值 Pc*(InN)/N 时，整个网络连通起来，那么以概率 p 生成的每一个网络几乎都是连通的，否则，当 p 小于该临界值时，几乎每一

12、个网络都是非连通的。(2)度分布对于一个给定连接概率为 p 的随机网络，若网络的节点数 N 充分大，则网络的度分布接近泊松(Poission)分布，如图 2-5 所示。P(k) = cN_ipk(1 - p)N(2-13) k!式中=p(N -1)呼 N 表示 ER 随机网络的平均度。(3)平均路径长度假定网络的平均路径长度为 L,从网络的一端走到网络的另一端，总步数 大概为 L。由于 ER 随机网络的平均度为,对于任意一个节点，其一阶邻 居的数目为,二阶邻居的数目为2，以此类推，当经过 L 步后遍历 了网络的所有节点，因此对于规模为 N 的随机网络，有L=N。由此可以得 到网络的平均路径长度

13、为：In N = In Nln(pN) In k(2-14)图 2-5 ER 随机网络的度分布(取自文献 )由于 lnN 的值随 N 增长较慢，所以规模很大的 ER 随机网络具有很小的平 均路径长度，如图 2-6 所示。图 2-6 ER 随机网络的平均路径长度与网络规模的关系(取自文献 )(4)簇系数在 ER 随机网络中，由于任何两个节点之间的连接概率 p 都相等，所以 ER 随机网络的聚类系数为：(2-15)可见，当网络规模 N 固定时，簇系数随着网络节点平均度 k的增加而增加，如图 2-7 所示。当网络节点平均度k固定时，簇系数随着网络规模 N 的 增加而下降，如图 2-8 和所示。显然，

14、当 N 较大时，ER 随机网络的簇系数很 小。图 2-7( N=104) ER 随机网络的簇系数与连接概率的关系(取自文献random networlt1M1000SIZE OF THE NETWORKS(N)图 2-8( p=0.0015)ER 随机网络的簇系数与网络规模的关系(取自文献模型的优点：能反映实际网络的小世界特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.3 小世界网络(small-world network)作为从完全规则网络向完全随机网络的过渡，美国学者Watts 和 Strogatz.0.6.6场..0.random network1NUJQ1NUJ

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

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

17、网络模型可以得到既有较短的平均路径长度（小世界特性），又有较高聚类系数（高聚集特性）。图 2-10 中 p 值在 0.01 附近的网络即兼具这两方 一面的特征。随机化重连规则网络P=O小世界网络随机网络 厂口占二.口ft JfiCp)/C0)L（pHL-0,4r*0.2 p 0.0.ti.i. , ,. 1 . i. J住*1E-30,010.11P图 2-10 WS 小世界网络模型的簇系数和平均路径长度随p 的变化关系（取自文献）由于在 WS 小世界网络模型的随机化重连过程中有可能破坏网络的连通 性。为了避免出现因重连而造成的孤立子网，美国学者Newman 与 Watts 合作于 1999

18、年提出了用“随机化加边”取代“随机化重连”的小世界网络模型， 称“ NW 小世界模型”。NW 小世界网络模型的构造算法：（1） 从规则网络开始：考虑一个含有 N 个节点的最近邻耦合网络，它们 围成一个环，其中每一个节点都与它左右相邻的各 K/2 个节点相连，K 是偶数。（2） 随机化加边：以概率 p 在随机选取的一对节点之间加上一条边。其中规定，任意两个不同的节点之间至多只能加一条边，并且每个节点不能有边与自身相连。当 p=0 时，模型退化为规则网络，当 p=1 时，模型退化为随机网络。通过 调节 p 的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图 2-11所示。在 p 较小时，N

19、W 模型具有与 WS 模型类似的特性。规则网络小世界网络随机网络图 2-11 NW 小世界网络模型(取自文献 )小世界网络模型具有如下基本特性:(1)簇系数WS 小世界网络的聚类系数为：NW 小世界网络的聚类系数为:(2)平均路径长度至今为止，还没有人得到关于 WS 小世界网络模型的平均路径长度的精确 解析表达式，Newman，Moore 和 Watts 分别用重整化群和序列展开方法得到 如下近似公式：式中 f(u)为一普适标度函数，且满足:const u 1f(U)Jl nu )/u u1目前为止，还没有 f(u)的精确表达式，Newman 等人基于平均场方法给出 了如下5叭巡一2)4(K

20、I)(2-16)3(K -2)C(P)一4(K -1) 4Kp(p 2)(2-17)L(P)二2NKf (NKp /2)(2-18)(2-19)卫=0 - p -1随机化加边的近似表达式：(3)度分布对于 WS 小世界网络，当 k K/2 时有:min(k-2,t2)kK-n2cK/2“、n 4-n(pK/2)2送CK/2(1 p)np2-e心(k-K/2 - n)!当 kv K/2 时，P(k)=0。对于 NW 小世界网络，每个节点的度至少为 K，因此当 k K 时，一个随机选取的节点的度为 k 的概率为：当 kv K 时，P(k)=0。类似 ER 随机网络模型，WS 小世界网络模型也是所有

21、节点的度都近似相 等的均匀网络。综上所述，ER 随机网络、WS 小世界网络和 NW 小世界网络的度分布可 近似用Poisson 分布来表示，该分布在度的平均值 v k处有一峰值，然后按指 数快速衰减。这类网络被称为均匀网络(homoge neous network)或指数网络(exponential network)。(2-20)P(k) =(2-21)(2-22)2.3.4 无标度网络 (scale-free network)近年来，大量的实证研究表明，许多大规模真实网络(如 WWW、In ternet 以及新陈代谢网络等)的度分布函数都是呈幕律分布的形式：P(k) * k 。在这样的网络中

22、，大部分节点的度都很小，但也有一小部分节点具有很大的度， 没有 一个特征标度。由于这类网络的节点的连接度并没有明显的特征标度， 故称为“无 标度网络”。为了解释实际网络中幕律分布产生的机理，Barabsi 和 Albert 在 1999年提出了一个无标度网络模型，称为 BA 无标度模型。该模型的构造主要基于现 实网络的两个内在机制：增长机制：大多数真实网络是一个开放系统， 随着时 间的推移，网络规模将不断增大，即网络中的节点数和连边数是不断增加的。择优连接：新增加的节更倾向于与那些具有较高连接度的节点相连。也就是富人 更富的观点（rich get richer）。BA 无标度网络模型的构造算法：（1） 增长：在初始时刻，假定网络中己有 mo个节点，在以后的每一个时 间步长中，增加一个连接度为 m 的节点（mW mo），新增节点与网络中已经存 在的 m个不同的节点相连，且不存在重复连接。（2） 优先连接：在选择新节点的连接点时，一个新节点与一个已经存在 的节点 i 相连的概率 n 与节点 i 的度 ki成正比：k“ i亡（2-23）j经过 t 步后，这种算法能够产生一个含有 N=t+mo个节点、mt 条边的网络。如图 2-12 所示的是 m=mo=2 时，BA 网络的演化过程。初始网络有两个节点，每次新增