复杂网络的基础知识

第二章复杂网络的基础知识2.1网络的概念所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirectednetworks），否则为有向网络（directednetworks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weightednetworks），否则为无权网络（unweightednetworks），如图2-1所示。图2-1网络类型示例(a)无权无向网络(b)加权网络(c)无权有向网络如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regularnetworks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（randomnetworks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complexnetworks）。图2-2规则网络示例(a)一维有限规则网络(b)二维无限规则网络2.2复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度（averagepathlength）、簇系数（clusteringefficient）、度分布（degreedistribution）、介数（betweenness）等，下面介绍它们的定义。2.2.1平均路径长度（averagepathlength）定义网络中任何两个节点i和j之间的距离lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter）为网络中任意两个节点之间距离的最大值。即}{max,ijjilD（2-1）定义网络的平均路径长度L为网络中所有节点对之间距离的平均值。即111)1(2NiNijijlNNL（2-2）其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度（characteristicpathlength）。网络的平均路径长度L和直径D主要用来衡量网络的传输效率。2.2.2簇系数（clusteringefficient）假设网络中的一个节点i有ki条边将它与其它节点相连，这ki个节点称为节点i的邻居节点，在这ki个邻居节点之间最多可能有ki(ki1)/2条边。节点i的ki个邻居节点之间实际存在的边数Ni和最多可能有的边数ki(ki1)/2之比就定义为节点i的簇系数，记为Ci。即)1(2iiiikkNC(2-3)整个网络的聚类系数定义为网络中所有节点i的聚类系数Ci的平均值，记为C。即NiiCNC11（2-4）显然，0≤C≤1之间。当C=0时，说明网络中所有节点均为孤立节点，即没有任何连边。当C=1时，说明网络中任意两个节点都直接相连，即网络是全局耦合网络。2.2.3度分布（degreedistribution）网络中某个节点i的度ki定义为与该节点相连接的其它节点的数目，也就是该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点i的度ki的的平均值称为网络的（节点）平均度，记为k。即NiikNk11（2-5）网络中节点的分布情况一般用度分布函数P(k)来描述。度分布函数P(k)表示在网络中任意选取一节点，该节点的度恰好为k的概率。即NiikkNkP1)(1)(（2-6）通常，一个节点的度越大，意味着这个节点属于网络中的关键节点，在某种意义上也越“重要”。2.2.4介数（betweenness）节点i的介数定义为网络中所有的最短路径中，经过节点i的数量。用Bi表示。即nminm,ggBnmnmnimi,,（2-7）式中gmn为节点m与节点n之间的最短路径数，gmin为节点m与节点n之间经过节点i的最短路径数。节点的介数反映了该节点在网络中的影响力。描述网络结构的特征量还有很多，这里就不一一介绍，在使用到它们的地方再给出详细的说明。2.3复杂网络的基本模型人们在对不同领域内的大量实际网络进行广泛的实证研究后发现：真实网络系统往往表现出小世界特性、无标度特性和高聚集特性。为了解释这些现象，人们构造了各种各样的网络模型，以便从理论上揭示网络行为与网络结构之间的关系，进而考虑改善网络的行为。下面介绍几类基本的网络模型。2.3.1规则网络（regularnetwork）常见的规则网络有三种：全局耦合网络（globallycouplednetwork）、最近邻耦合网络（nearest-neighborcouplednetwork）和星型网络模型（starcouplednetwork），如图2-3所示。图2-3三种典型的规则网络(a)全局耦合网络(b)最近邻耦合网络(c)星型网络图2-3（a）所示为一个含有N个节点的全局耦合网络。网络中共有N(N1)/2条边，其平均路径长度L=1（最小），簇系数C=1（最大）。度分布P(k)为以N1为中心的δ函数。模型的优点：能反映实际网络的小世界特性和大聚类特性。模型的缺点：不能反映实际网络的稀疏特性。因为一个具有N个节点的全局耦合网络的边的数目为O(N2)，而实际网络的边的数目一般是O(N)。图2-3（b）所示为一个含有N个节点的最近邻耦合网络。网络中的每个节点只和它周围的邻居节点相连，其中每个节点都与它左右各K／2个邻居节点相连（K为偶数）。对于固定的K值，网络的平均路径长度为：)(2NKNL（2-8）对于较大的K值，最近邻耦合网络的簇系数为：43)1(4)2(3KKC（2-9）度分布P(k)为以K为中心的δ函数。模型的优点：能反映实际网络的大聚类特性和稀疏特性。模型的缺点：不能反映实际网络的小世界特性。图2-3（c）所示为一个具有N个节点的星型网络。网络有一个中心节点，其余N1个节点都只与这个中心节点相连，且它们彼此之间不连接。网络的平均路径长度：)(2)1()1(22NNNNL(2-10)网络的簇系数为：)(11NNNC(2-11)网络的度分布为：其它0)1()1(1)(11NKKKPNN(2-12)规定：如果一个节点只有一个邻居，那么该节点的簇系数为1。也有些文献规定只有一个邻居的节点的簇系数为0，若依此定义，则星型网络的簇系数为0。模型的优点：能反映实际网络的小世界特性和稀疏特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.2ER随机网络（randomnetwork）该模型由匈牙利数学家Edös和Rényi在上世纪50年代最先提出，所以被人们称为ER随机网络模型。ER随机网络的构造有两种方法。第一种方法：定义有标记的N个节（网络中的节点总数），并且给出整个网络的边数n，这些边的选取采用从所有可能的N(N1)／2种情况中随机选取。第二种方法：给定有标记的N个节点，以一定的随机概率p连接所有可能出现的N(N1)／2种连接，假设最初有N个孤立的节点，每对节点以随机概率p进行连接。如图2-4所示。图2-4ER随机网络的演化示意图（a）p=0时，给定10个孤立节点；（b）～（c）p=0.1，0.15时，生成的随机图ER随机网络模型具有如下基本特性：（1）涌现或相变如果当N→∞时产生一个具有性质Q的ER随机图的概率为1，那么几乎每一个ER随机图都具有性质Q。以连通性为例，若当连接概率p达到某个临界值pc∝(lnN)／N时，整个网络连通起来，那么以概率p生成的每一个网络几乎都是连通的，否则，当p小于该临界值时，几乎每一个网络都是非连通的。（2）度分布对于一个给定连接概率为p的随机网络，若网络的节点数N充分大，则网络的度分布接近泊松（Poission）分布，如图2-5所示。kkkNkkNekkppCkP!)1()(11（2-13）式中k=p(N1)≈PN表示ER随机网络的平均度。图2-5ER随机网络的度分布（取自文献[]）（3）平均路径长度假定网络的平均路径长度为L，从网络的一端走到网络的另一端，总步数大概为L。由于ER随机网络的平均度为﹤k﹥，对于任意一个节点，其一阶邻居的数目为﹤k﹥，二阶邻居的数目为﹤k﹥2，以此类推，当经过L步后遍历了网络的所有节点，因此对于规模为N的随机网络，有﹤k﹥L=N。由此可以得到网络的平均路径长度为：kNpNNLlnln)ln(ln（2-14）由于lnN的值随N增长较慢，所以规模很大的ER随机网络具有很小的平均路径长度，如图2-6所示。图2-6ER随机网络的平均路径长度与网络规模的关系（取自文献[]）（4）簇系数在ER随机网络中，由于任何两个节点之间的连接概率p都相等，所以ER随机网络的聚类系数为：NkpC（2-15）可见，当网络规模N固定时，簇系数随着网络节点平均度k的增加而增加，如图2-7所示。当网络节点平均度k固定时，簇系数随着网络规模N的增加而下降，如图2-8和所示。显然，当N较大时，ER随机网络的簇系数很小。图2-7（N=104）ER随机网络的簇系数与连接概率的关系（取自文献[]）图2-8（p=0.0015）ER随机网络的簇系数与网络规模的关系（取自文献[]）模型的优点：能反映实际网络的小世界特性。模型的缺点：不能反映实际网络的大聚类特性。2.3.3小世界网络（small-worldnetwork）作为从完全规则网络向完全随机网络的过渡，美国学者Watts和Strogatz于1998年设计了一个具有小的平均路径长度和大的聚类系数的小世界网络模型（small-worldnetwork），简称WS小世界网络模型。WS小世界网络模型的构造算法：（1）从规则网络开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每一个节点都与它左右相邻的各K/2个节点相连，K是偶数。（2）随机化重连：以概率p随机地重新连接网络中的每一条边，即将连边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每个节点不能有边与自身相连。为了保证网络具有稀疏性，要求NK，这样构造出来的网络模型具有较高聚类系数。而随机化重连过程大大减小了网络的平均路径长度，使网络模型具有小世界特性。当p取值较小时，重连过程对网络的聚类系数影响不大。当p时，模型退化为规则网络，当p时，模型退化为随机网络。通过调节p的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图2-9所示.图2-9WS小世界网络模型（取自文献[]）WS小世界网络模型的其聚类系数和平均路径长度可以看作是重连概率p的函数，分别记为C(p)和L(p)，它们的变化规律如图2-10所示。在某个p值范围内，WS网络模型可以得到既有较短的平均路径长度（小世界特性），又有较高聚类系数（高聚集特性）。图2-10中p值在0.0l附近的网络即兼具这两方一面的特征。图2-10WS小世界网络模型的簇系数和平均路径长度随p的变化关系（取自文献[]）由于在WS小世界网络模型的随机化重连过程中有可能破坏网络的连通性。为了避免出现因重连而造成的孤立子网，美国学者Newman与Watts合作于1999年提出了用“随机化加边”取代“随机化重连”的小世界网络模型，称“NW小世界模型”。NW小世界网络模型的构造算法：（1）从规则网络开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每一个节点都与它左右相邻的各K/2个节点相连，K是偶数。（2）随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中规定，任意两个不同的节点之间至多只能加一条边，并且每个节点不能有边与自身相连。当p=0时，模型退化为规则网络，当p=1时，模型退化为随机网络。通过调节p的值就可以控制模型从完全规则网络到完全随机网络的过渡，如图2-11所示。在p较小时，NW模型具有与WS模型类似的特性。图2-11NW小世界网络模型（取自文献[]）小世界网络模型具有如下基本特性：（1）簇系数WS小世界网络的聚类系数为：3)1()1(4)2(3)(pKKpC