复杂网络几种模型的比较与分析.pdf

科技信息博士专家论坛
·2006年第3期
复杂网络几种模型的比较与分析

兰州交通大学信息与电气工程学院邬开俊郑丽英王铁君

[摘要]近年来,真实网络中小世界效应和自由标度特性的发现激起了科学界对复杂网络的研究热潮,本文我们从度
分布、平均路径长度、聚集系数、小世界效应对随机网络、小世界网络和自由标度网络几种网络模型进行了比较和分
析。
[关键词]复杂网络随机网络小世界网络自由标度网络

引言式中是节点的度也就是说节点有个最近邻
1kii,iki;E(i)
自从年和提出小世界网络模型以为这个最近邻节点中实际存在的连结数目为这
1998WattsStrogatzki;ki(ki-1)/2
来[1]复杂网络的研究在过去几年得到了迅速的发展它已遍及个最近邻节点中所有可能的连结数目不难看出是一个
,,ki。C(i)
各个学科领域,从生物学到物理学,甚至到社会科学。它之所以局域几何量,它只描述节点i附近的集群系数。而对于整个网络
能够取得迅猛发展,可以把它归结为以下几条原因:(1)伴随着的集群系数就是所有节点的集群系数的平均值
在各个领域中数据获取的计算机化,出现了各种关于现实复杂N
1
网络拓扑性的大型数据库计算能力的不断提高使人们能C=ΣC(i)(4)
;(2),Ni=1
够对包含以数百万计节点的网络进行研究这在以前是无法实
,3复杂网络模型
现的实证分析表明从万维网到新陈代谢网许多领域的各
;(3),,3.1随机网络
种复杂网络展现了某些共同的统计性质如幂律度分布表明其
,,Erodos和Renyi于1959年构建了ER模型,也就是随机网
中存在一些普适性的概念和规律研究理论也有了突破
;(4),络。ER网络中定义了由n条边连接的N个节点的随机网络,这
和提出小世界网络的构造方式和
WattsStrogatz,Barabasin条边是从N(N-1)/2条可能的边中任意选取的。共有N个
则指出增长和偏好连接是形成无标度网络的根本原节点和条边的n个网络这些网络就形成了一个概率
Albert,nCN(N-1)/2,
因[2]统计物理学的研究方法在复杂网络研究中得到广泛应用
,。空间。在这个空间中,每一步的实现都具有相等的或然率。
本文简述了复杂网络的基本概念及网络参数,对几种网络(1)平均路径长度
模型的网络特征及性质的比较和分析对揭示复杂网络的性质随机网络的平均度令
,<k>=2n/N=p(N-1)≈pN。Lrand
具有十分重要的意义为一个随机网络的平均路径长度随机网络的L个节点
。,<K>rand
网络参数的距离为或者是接近于因此L即
2LrandLrand,N～<K>rand,:
幂律的度分布[3][3]
2.1Lrand～ln(N)/ln(<k>)
幂律的度分布是描述节点特征最简单的也是研究最多的概平均路径长度随网络大小变化呈对数增长的趋势具有典型
念节点的度是它的所有连结数目所有节点的度的平均的小世界效应由于随的增长比较缓慢因此即使它在
。iKi。。logNN,
就称为网络的平均度用来表示在节点的度中的扩散用
,<k>,较大的系统中,平均路径长度还是很小。
分布函数来表示给出了一个随机选取的节点有确切
p(k)。p(k)(2)集群系数
的条连结的概率度分布函数反映了函数系统的统计特征理
k。。复杂网络具有很大的集群系数,随机网络中的一个节点和
论上利用度分布可以计算出其他表征全局特性参数的量化数
它的最近邻节点连结概率等于任意选取两个节点的连结概率,
值因此随机网络的集群系数[3]这也就
。Crand=P=<k>/N<<1,
平均路径长度
2.2意味着一个大标度的随机网络不具备簇效应。由上式,对于不同
在由个节点组成的网络中第个节点到第个节点的大小的随机网络如果我们把作为的函数在对
N,ij,Crand/<k>N。
距离定义为从节点最少经过多少次连接到节点这个距离
ij,数平面内,它们的斜率仍然为-1,斜率表明现实网络是不服从
叫做最短路径定义式
l(i,j),随机网络预测的。C/<k>不随1/N的减少而减少,而与N无
N关这一特征在规则的格子上得到了充分的体现规则格子的集
1。。
lmin(i)=Σl(i,j)(1)群系数取决于所取格子的数目而不取决于规则格子的大小
Ni=1,。
小世界网络
对于无向图l(i,j)=l(j,i),平均最短路径就定义为3.2
N实证结果表面,大多数的真实网络具有小世界性(较小的最
1
短路径和聚集性相对较大的聚集系数[3]见表所示然而
l=Σlmin(i)(2))(),1。,
Ni=1
虽然规则耦合网络是成簇的但不具有小世界效应而随机网络
当网络有向时l(i,j)≠l(j,i),平均路径只能用公式4计算。,。
则表现出小世界效应却不具有簇效应这就说明规则复合网络
平均最短路径描述了节点对间的