复杂网络的基础知识.pdfVIP

第二章复杂网络的基础知识

2.1网络的概念

所谓“网络”(networks),实际上就是节点(node)和连边(edge)的集合。

如果节点(3J)与/)应为同一条边，那么该网络为无向网络(undirected

networks),否则为有向网络(directednetworks)。如果给每条边都赋予相应的权

值，那么该网络就为加权网络(weightednelworks),否则为无权网络(unweighted

networks),如图2-1所示。

图2-1网络类型示例

(a)无权无向网络(b)加权网络(c)无权有向网络

如果节点按照确定的规贝J连边，所得到的网络就称为“规则网络(regular

networks),如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就

称为“随机网络(randomneiworks)。如果节点按照某种(自)组织原则的方式

连边，将演化成各种不同的网络，称为“复杂网络(complexneiworks)。

图2-2规则网络示例

(a)一维有限规则网络(b)二维无限规则网络

2.2复杂网络的基本特征量

描述复杂网络的基本特征量主要有：平均路径长度(averagepathlength)

簇系数(clusteringefficient)度分布(degreedistribution)介数(betweenness)

等，下面介绍它们的定义。

221平均路径长度(averagepathlength)

定义网络中任何两个节点i和j之间的距离片为从其中一个节点出发到达

另一个节点所要经过的连边的最少数目。定义网络的直径(diameter)为网络

中任意两个节点之间距离的最大值。即

D=max｛。｝(2-1)

Lj

定义网络的平均路径长度L为网络中所有节点之间距离的平均值。即

2N-lN

L=N(N—1)EE%(2々)

v)i=lj=i+\

其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L

又称为特征路径长度(characieristicpathlength)o

网络的平均路径长度L和直径D主要用来衡量网络的传输效率。

222簇系数(clusteringefficient)

假设网络中的一个节点，有k•条边将它与其它节点相连，这k个节点称为

节点i的邻居节点，在这k•个邻居节点之间最多可能有奴kT)/2条边。节点i

的k个邻居节点之间实际存在的边数M和最多可能有的边数1)/2之比就

定义为节点i的簇系数，记为即

2华

(2-3)

帚化一1)

整个网络的聚类系数定义为网络中所有节点i的聚类系数C•的平均值，记

为C。即

[N

。=万26