1第二章复杂网络的基础知识2.1网络的概念所谓“网络"(networks),实际上就是节点(node)和连边(edge)的集合。如果节点对(i,j)与(j,i)对应为同一条边，那么该网络为无向网络(undirectednetworks),否则为有向网络(directednetworks)。如果给每条边都赋予相应的权值，那么该网络就为加权网络(weightednetworks)，否则为无权网络(unweightednetworks)，如图2-1所示。(a)无权无向网络(b)加权网络(c)无权有向网络如果节点按照确定的规则连边，所得到的网络就称为“规则网络”(regularnetworks),如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”(randomnetworks)o如果节点按照某种(自)组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”(complexnetworks)。(a)(b)图2-2规则网络示例(a)一维有限规则网络(b)二维无限规则网络图2-1网络类型示例二二22-2N(N-1)艺迓l2-(2-2.2复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度(averagepathlength)、簇系数(clusteringefficient))度分布(degreedistribution)、介数(betweenness)等，下面介绍它们的定义。2・2・1平均路径长度(averagepathlength)定义网络中任何两个节点i和j之间的距离-•为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径(diameter)为网络中任意两个节点之间距离的最大值。即D=max{/}iji,j定义网络的平均路径长度L为网络中所有节点对之间距离的平均值。即其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度(characteristicpathlength)。网络的平均路径长度L和直径D主要用来衡量网络的传输效率。2・2・2簇系数(clusteringefficient)假设网络中的一个节点i有k.条边将它与其它节点相连，这k.个节点称为ii节点i的邻居节点，在这k.个邻居节点之间最多可能有k.(k.-1)2条边。节点i的k个邻居节点之间实际存在的边数N.和最多可能有的边数k.(k-1)2之比就iiii定义为节点i的簇系数，记为C.。即i2NIk(k-1)ii3整个网络的聚类系数定义为网络中所有节点i的聚类系数C.的平均值，记i4为C。2-4)2-7)C=丄为CN1=1显然，0
