复杂网络的基础知识

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

2、"(regularnetworks),如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”(randomnetworks)°如果节点按照某种(自)组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络"(complexnetworks)0(a)(b)图2-2规则网络示例(a)一维有限规则网络(b)二维无限规则网络第二章复杂网络的基础知识2.2复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度(averagepathlength)、簇系数(clusteringefficient)>度分布(degreedistribu

3、tion)、介数(betweenness等，下面介绍它们的定义。2.2.1 平均路径长度(averagepathlength定义网络中任何两个节点i和j之间的距离lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径(diameter)为网络中任意两个节点之间距离的最大值。即D=maxlj(2-1)i,j定义网络的平均路径长度L为网络中所有节点对之间距离的平均值。即L=N(N-1)NN(2-2)-liji1jT1其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度(characteristicpathlength)。网络的平均路径长度L和直

4、径D主要用来衡量网络的传输效率。2.2.2 簇系数(clusteringefficient)假设网络中白一个节点i有k条边将它与其它节点相连，这ki个节点称为节点i的邻居节点，在这ki个邻居节点之间最多可能有ki(ki-1)/2条边。节点i的ki个邻居节点之间实际存在的边数Ni和最多可能有的边数ki(ki-1)/2之比就定义为节点i的簇系数，记为Ci。即(2-3)G=4ki(ki-1)整个网络的聚类系数定义为网络中所有节点i的聚类系数Ci的平均值，记为Co即第二章复杂网络的基础知识N(2-4)1CkgNi1显然，0<C&1之间。当C=0时，说明网络中所有节点均为孤立节点，即没有任

5、何连边。当C=1时，说明网络中任意两个节点都直接相连，即网络是全局耦合网络。2.2.3 度分布(degreedistribution)网络中某个节点i的度ki定义为与该节点相连接的其它节点的数目，也就是该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点i的度ki的的平均值称为网络的(节点)平均度，记为<k>。即,1VN.'k)=T乙ki(2-5)Ni=1网络中节点的分布情况一般用度分布函数P(k)来描述。度分布函数P(k)表示在网络中任意选取一节点，该节点的度恰好为k的概率。即1NP(k)=(k-ki)(2-6)NiT通常，一个节点的度越大，意味着这个节点属于

6、网络中的关键节点，在某种意义上也越“重要”。2.2.4介数(betweenness节点i的介数定义为网络中所有的最短路径中，经过节点i的数量。用Bi表示。即Bi=£-gminm,nri,m#n(2-7)m,ngmn式中gmn为节点m与节点n之间的最短路径数，gmin为节点m与节点n之第二章复杂网络的基础知识问经过节点i的最短路径数。节点的介数反映了该节点在网络中的影响力。描述网络结构的特征量还有很多，这里就不一一介绍，在使用到它们的地方再给出详细的说明。2.3复杂网络的基本模型人们在对不同领域内的大量实际网络进行广泛的实证研究后发现：真实网络系统往往表现出小世界特性、无标度特性和高聚

7、集特性。为了解释这些现象，人们构造了各种各样的网络模型，以便从理论上揭示网络行为与网络结构之间的关系，进而考虑改善网络的行为。下面介绍几类基本的网络模型。2.3.1规则网络(regularnetwork)常见的规则网络有三种：全局耦合网络(globallycouplednetwork)最近邻耦合网络(nearest-neighborcouplednetwork和星型网络模型(starcouplednetwork),如图2-3所示。(b)图2-3三种典型的规则网络(a)全局耦合网络(b)最近邻耦合网络(c)星型网络网络中共有N(N-1)/2图2-3(a)所示为一个含有N个节点的全局耦合网络。条边

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

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

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

11、4所示。图2-4ER随机网络的演化示意图(a)p=0时，给定10个孤立节点；(b)(c)p=0.1,0.15时，生成的随机图ER随机网络模型具有如下基本特性：(1)涌现或相变第二章复杂网络的基础知识如果当N一刈寸产生一个具有性质Q的ER随机图的概率为1,那么几乎每一个ER随机图都具有性质Qo以连通性为例，若当连接概率p达到某个临界值Pc8(lnN)/N时，整个网络连通起来，那么以概率p生成的每一个网络几乎都是连通的，否则，当p小于该临界值时，几乎每一个网络都是非连通的。(2)度分布对于一个给定连接概率为p的随机网络，若网络的节点数N充分大，则网络的度分布接近泊松(Poission)分布，如图2

12、-5所示。kkN-1kk!(2-13)P(k)=Cnp(1-p)式中<k>=p(N-1)即N表示ER随机网络的平均度图2-5ER随机网络的度分布(取自文献)(3)平均路径长度假定网络的平土§路径长度为L,从网络的一端走到网络的另一端，总步数大概为L。由于ER随机网络的平均度为<k>,对于任意一个节点，其一阶邻居的数目为<k>,二阶邻居的数目为<k>2,以此类推，当经过L步后遍历了网络的所有节点，因此对于规模为N的随机网络，有<k>L=N。由此可以得到网络的平均路径长度为：_lnN_lnNLln(pN)ln<k>(

13、2-14)第二章复杂网络的基础知识由于lnN的值随N增长较慢，所以规模很大的ER随机网络具有很小的平均路径长度，如图2-6所示图2-6ER随机网络的平均路径长度与网络规模的关系(取自文献)(4)簇系数在ER随机网络中，由于任何两个节点之间的连接概率p都相等，所以ER随机网络的聚类系数为：(2-15)可见，当网络规模N固定时，簇系数随着网络节点平均度k的增加而增加，如图2-7所示。当网络节点平均度4固定时，簇系数随着网络规模N的增加而下降，如图2-8和所示。显然，当N较大时，ER随机网络的簇系数很小。第二章复杂网络的基础知识口.口r1r一,fIa.Q0.20同O,e0.8toconnectedp

14、robability图2-7(N=104)ER随机网络的簇系数与连接概率的关系(取自文献)图2-8(p=0.0015)ER随机网络的簇系数与网络规模的关系(取自文献)1NUJ一口LLL山。ooN_o£lxjlg30模型的优点：能反映实际网络的小世界特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.3 小世界网络(small-worldnetwork)作为从完全规则网络向完全随机网络的过渡，美国学者Watts和Strogatz第二章复杂网络的基础知识于1998年设计了一个具有小的平均路径长度和大的聚类系数的小世界网络模型(small-worldnetwork),简称WS小世界网络

15、模型。WS小世界网络模型的构造算法：(1)从规则网络开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每一个节点都与它左右相邻的各K/2个节点相连，K是偶数。(2)随机化重连：以概率p随机地重新连接网络中的每一条边，即将连边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每个节点不能有边与自身相连。为了保证网络具有稀疏性，要求N>>K,这样构造出来的网络模型具有较高聚类系数。而随机化重连过程大大减小了网络的平均路径长度，使网络模型具有小世界特性。当p取值较小时，重连过程对网络的聚类系数影响不大。当p=

16、0时，模型退化为规则网络，当p=l时，模型退化为随机网络。通过调节p的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图2-9所示.小世界网络随机网络子*=1随机优重连图2-9WS小世界网络模型(取自文献)WS小世界网络模型的具聚类系数和平均路径长度可以看作是重连概率p的函数，分别记为C(p)和L(p),它们的变化规律如图2-10所示。在某个p值范围内，WS网络模型可以得到既有较短的平均路径长度(小世界特性)，又有较高聚类系数(高聚集特性)。图2-10中p值在0.0l附近的网络即兼具这两方一面的特征。101.00月0,60,40.20.0第二章复杂网络的基础知识卜'口'口

17、口g白二”口口口C(P)/C(O)口PL(p)/L口图2-10WS小世界网络模型的簇系数和平均路径长度随p的变化关系(取自文献)由于在WS小世界网络模型的随机化重连过程中有可能破坏网络的连通性。为了避免出现因重连而造成的孤立子网，美国学者Newman与Watts合作于1999年提出了用“随机化加边”取代“随机化重连”的小世界网络模型，称“NW小世界模型”。NW小世界网络模型的构造算法：(1)从规则网络开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每一个节点都与它左右相邻的各K/2个节点相连，K是偶数。(2)随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中规定，任意

18、两个不同的节点之间至多只能加一条边，并且每个节点不能有边与自身相连。当p=0时，模型退化为规则网络，当p=1时，模型退化为随机网络。通过调节p的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图2-11所示。在p较小时，NW模型具有与WS模型类似的特性。11第二章复杂网络的基础知识规则网络小世界网络随机网络P-0d>p-1髓机化加边图2-11NW小世界网络模型(取自文献)小世界网络模型具有如下基本特性:(1)簇系数WS小世界网络的聚类系数为:C(p)=3(K-2)4(K-1)p)3(2-16)NW小世界网络的聚类系数为:C(P)=3(K-2)4(K-1)4Kp(p2)(2-17)(

19、2)平均路径长度至今为止，还没有人得到关于WS小世界网络模型的平均路径长度的精确解析表达式，Newman,Moore和Watts分别用重整化群和序列展开方法得到如下近似公式：2N,L(p)f(NKp/2)K(2-18)式中f(u)为一普适标度函数，且满足:f(u)=<constu«1Jlnu)/uu»1(2-19)目前为止，还没有f(u)的精确表达式，Newman等人基于平均场方法给出了如下的近似表达式:12(2-20)(2-21)(2-22)第二章复杂网络的基础知识f(x)&,1arctanhJ2、x22xx2(3)度分布对于WS小世界网络，当k>K/

20、2时有:min(k-K-,K-)kK-nc/i、vcK/2、n4-n(pK/2)一2_与P(k)=cCK/2(1-p)np二e丁n力n(k-K/2-n)!当k<K/2时，P(k)=0o对于NW小世界网络，每个节点的度至少为K,因此当k>K时，一个随机选取的节点的度为k的概率为：当k<K时，P(k)=0o类似ER随机网络模型，WS小世界网络模型也是所有节点的度都近似相等的均匀网络。综上所述，ER随机网络、WS小世界网络和NW小世界网络的度分布可近似用Poisson分布来表示，该分布在度的平均值<k>处有一峰值，然后按指数快速衰减。这类网络被称为均匀网络(homoge

21、neousnetwork)或指数网络(exponentialnetwork)。2.3.4无标度网络(scale-freenetwork)近年来，大量的实证研究表明，许多大规模真实网络(如WWW>Internet以及新陈代谢网络等)的度分布函数都是呈幕律分布的形式：P(k)8k二。在这样的网络中，大部分节点的度都很小，但也有一小部分节点具有很大的度，没有一个特征标度。由于这类网络的节点的连接度并没有明显的特征标度，故称为“无标度网络”。为了解释实际网络中幕律分布产生的机理，Barabsi和Albert在199913第二章复杂网络的基础知识年提出了一个无标度网络模型，称为BA无标度模型。该模

22、型的构造主要基于现实网络的两个内在机制：增长机制：大多数真实网络是一个开放系统，随着时间的推移，网络规模将不断增大，即网络中的节点数和连边数是不断增加的。择优连接：新增加的节更倾向于与那些具有较高连接度的节点相连。也就是富人更富的观点(richgetricher)。BA无标度网络模型的构造算法：(1)增长：在初始时刻，假定网络中己有m0个节点，在以后的每一个时间步长中，增加一个连接度为m的节点(m&mo),新增节点与网络中已经存在的m个不同的节点相连，且不存在重复连接。(2)优先连接：在选择新节点的连接点时，一个新节点与一个已经存在的节点i相连的概率H与节点i的度ki成正比：k；口i二仁(2-23)ikj经过t步后，这种算法能够产生一个含有N=t+mo个节点、mt条边的网络。如图2-12所示白是m=mo=2时，BA网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已经存在的两个节点相连。=>«=>,=t>.