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

1、科技信息廊士专家论坛2006年第3期复杂网络几种模型的比较与分析兰州交通大学信息与电气工程学院 绑开俊 郑丽英 王铁君摘 要近年來真实网络中小世界效应和自由标度特性的发现激起了科学界对复杂网络的研究热潮，本文我们从度 分布、平均路径氏度、聚集系数、小世界效Z对随机网络、小壯界M络和1'1由标度网络儿种网络模空进行了比较和分 析。关键词复朵网络随机网络小世界网络自由标度网络科技信息廊士专家论坛2006年第3期科技信息廊士专家论坛2006年第3期1引言自从1998年Watts和Strogatz提出小世界网络模型以 來复杂网络的研究在过去儿年得到了迅速的发展它已遍及 各个学科领域从生物学到物

2、理学農至到社会科学。它Z所以 能够取得迅猛发展可以把它归结为以下儿条原因：(1)伴随着 在各个领域屮数据获取的计算机化出现J'W种关于现实复杂 网络拓扑性的大型数搦库；(2计算能力的不断提高，使人们能 够对包含以数百万计节点的网络进行研究这在以前是无法实 现的：(3)实证分析农明从万维网到新陈代谢网，许多领域的各 种复杂网络展现了某些共同的统计性质如慕律度分布，表明其 中存在一些营适性的槪念和规律：(4)研究理论也有了突破 Watts和Strogatz提111小世界网络的构造方式.Barabasi和 Albert则指出增氏和偏好连接肚形成无标度网络的根本原 因，统计物理学的研究方法在复

3、杂网络研究中得到广泛应用。本文简述了复杂也络的基本概念及网络参数对儿种网络 模型的网络特征及性质的比较和分析对弼示父杂网络的性质 具有十分重要的总义。2网络参数2. 1幕律的度分布¥彳|!的度分布是描述卩点特征姒简单的也肚研究最参的概 念。节点i的度K,是它的所冇连结数He所冇节点的度的平均 就称为网络的平均度，用Vk>来表示，在节点的度中的扩散用 分布甬数p(k來表示。p(k)给出了 -个随机选取的节点冇确切 的k条连结的槪率。度分布曲数反映J'西数系统的统计特征c理 论上利用度分布可以计篦出比他表征全局特性参数的量化数 值。2.2平均路径K:度在由N个节点纽成的网络

4、中第i个节点到第j个节点的 距离泄义为从节点i最少经过多少次连接到节点j这个距离 l(ij)叫做最短路径定义式Nlmin(i)= - r-/l(i.j)( 1 )对于无向图平均最短路径就定义为当网络有向时l(i,j)Ml(ji)平均路径只能用公式4计算。 平均最短路径描述r节点对间的平均分离同时也反映了网络 的尺寸丙此常叫做网络直径。23集祥系数。成铁的固冇趋势可以用集祥系数來衷达这 个概念起源于社会科学。比如说在一个人的刖友圈中他的刖 友屮的两个很可能彼此也金刖友这种性质可以更容易理解集 祥系数的概念。更准确的说可以把集样系数C定义为一个节 点的相邻节点也可能是彼此的相邻节点。对于个节点i的

5、集 祥系数可以定义为下式，厂厂、2E(i)C(,) = kl(k.-D(3)弍中k,是节点i的度也就是说节点i冇个k.最近邻；E(i) 为这个k,最近邻点中实际存在的连结数U；k.(k.-l)/2为这 个k,屍近邻节点中所冇可能的连结数He不难看出CG)是个 局域几何量它只描述节点i附近的集群系数。而对于整个网络 的集祥系数就是所冇节点的集群系数的平均值NC =Yc(i)(4)3复杂网络模吃3.1随机网络Erodos和Renvi于1959年构建ER模取也就是随机网 络L ER网络中定义r由n条边连接的N个描点的M机网络.这 n条边是从N(N-1) /2条可能的边中任怠选取的。共冇N个 节点和n

6、条边的a(N_n.7个网络这些网络就形成一个概率 空间1在这个空间中每一步的实现都具冇相等的或然率。仃)平均路径长度随机网络的平均度Vk> = 2n/N = p (N-l)apN。令Iz 为一个随机网络的平均路從K度随机网络的<K>5e个节点 的HU离为或者是接近于1十卅因此NV K >' 即： I” 亠ln(N)/ln(<k>)l：3¥均路從长度随网络人小变化呈对数增氏的趨势具仃典型 的小世界效应。由于logN随N的增氏比较缓慢因此即使它在 较人的系统屮平均路径长度还是很小。(2) 集能系数复杂网络具有很人的集群系数随机网络屮的一个节点和

7、 它的破近邻"点连结概率等J：任愆选取两个节点的连结槪率. 因此随机网络的集群系数Cr.n- = P = <k>/N«l3.这也就 总味着个人标度的随机网络不M語簇效应"山上式.对于不同 人小的随机网络如果我们把C_,/<k>作为N的西数。乍对 数平面内，它们的斜率仍然为一1,斜率表明现实网络楚不服从 随机网络预测的。C/<k>不随1/N的减少而减少而与N无 关。这 特征在规则的格/上得到了充分的体现。规则格/的集 群系数取决于所取格了的数忖而不取决于规则格了的人小。3. 2小世界网络实证结果农而人多数的真实网络具有小世界性(较

8、小的最 短路径)和聚集性(相对较人的聚集系数).见农1所示。然而, 加然规则耦介网络是成簇的但不貝仃小世界效应。而随机网络 则表现出小世界效应却不具有簇效应。这就说明规则宣合网络 和ER随机网络不H仃现实网络(如人类友谊网络及World Wide Web)'l«的某兆朿要性质。因为许多现实网络既不是规则 的也不是完全随机的，因此为描述从-个规则的格f到 个 随机网络的过渡.Watts和Strogatz于1998年捉出了小世界网 络这-概念并建立f WS模型l°WS模型衣述如l、：WS模熨 始于一具有N个节点的维网络.网络的节点与其最近的邻揺 点和次邻接点相连接然后毎

9、条边以概率p車新连接约東条件 为廿点间无重边无门环。模型构造过程如图1所示。而规则网 络和随机网络则分别在p为0和1时的特例。当前研究的热点科技信息廊士专家论坛2006年第3期科技信息廊士专家论坛2006年第3期基金项目：甘肃省建设科技计划项目资助(JK2OO5-21)作者简介|那开俊：为1978年生山东莒南人助教，礦士研究生研究方向:复杂网洛科能信息处理.郑丽英：女.1957年岀生河南内乡人教授研究方向：数据结构与麺法数据挖拥分布式系统科技信息廊士专家论坛2006年第3期是p在01 Z间的WS网络的性质这些性质仃：()度分布当P = 0时对应的网络规则图。两个节点间的 平均距离V1 >

10、线性地随N增氏而增2集胖系数人度分布足 屮心点位于K = k的丙数.n当p=l时系统变为随机图随机网络是Poisson分布<1> 对数地随N增氏而增集祥系 数随N减少而减少。在p等于(01)区间任意值时模盘显示出 小世界特性<L>约等丁随机图的值网络具仃高度集能性.Networksize<k>1lfaadCCratxlWWW tsiie level undir15312735. 213. 13. 350. 10780. 00023Movie actors225226613. 652. 990. 790. 00027Math. Co authorship709

11、753.99.5& 20. 595.4X107E. coli subsirmi(? graph2827. 352.93. 040. 320.026Sil wood Park food web1541. 753. 403. 230. 150. 03Words synonyms2231113.484.53. 840. 70. 0006原来丁两数形式的度分布逐渐拓宽最终形成Poisson分布。 表1实际网络的small word现彖RoguiH/S4Tiaib«o«idRn 八 tfom O p 1Irvcreasing ra?xtomne!»图l小世界网络扌石

12、扑结构示意图$科技信息廊士专家论坛2006年第3期科技信息廊士专家论坛2006年第3期N.C.(C.-l)/2NetworkSize<k>routr.nLrallrand1 ”、WWW3257294.512. 452. 111.28. 324.77Internetrouter38882. 572. 482.4812. 15& 75& 67Movie actors2122502& 782.32.34. 543. 654.01Co authors math.70979.5& 26. 53Silwood park154I. 751. 1

13、31. 133.43. 232Metabolic *E. coli7787. 3. 322. 89表2实际网络的scale free现彖慕律分布相对于指数分布其图形没有峰值人多数节点仅 有少量连按，不存在随机网络中的特征标度于是Barabasi和 Albert称这种分布具有¥律特征的网络为自由标度网络(Scale -free网络)。为解释自由标度网络的形成机制 1999年Barabasi和Albert提出了著名的BA模型他们认为其它的网 络模型不能占股到现实网络的两个特征：(1)人多数现实网络都 具有开放性并且它们是由新节点的不断加入而形成。但是大多 数模型都足静

14、止的虽然连结可以加入或者圧(下转第3页)(2平均路径长度° Wails和Pandit认为小世界网络的平 均路能氏度l下降的原因在于两个节点间出现r瑕短路径叮. 每条最短路径都址随机产生的.都仃把网络中分散部分连接 起来的趋势。1999年.Walls发现半p=2/(NK)时.平均路彳仝 氏度L开始卜降这就确保至少条最短路径的存在也就 意味着p依赖于系统的人小反过来说存在一个依赖于p的交 义氏度N如果NVN'L就与N成止比；如果N>N，L与 inN成正比2】°(3) 集群系数。除f小路径的特性小世界网络还具有絞高 的集井系数。WS模型因为亚新连接概率p在人范围内进

15、行波 动而表现出二向件在规则的格/中(p = 0)集胖系数不受格f 大小的影响而仅仅受其拓扑性的影响。由于网络的连接是随机 的因此卩较小时集胖系数始终等于C(O)o值得指出的是 Barrai等给('(p)进行了重新迩义.在p = 0时.毎个节心邯有 2k个邻近节点很容易得到这些邻近节点的连接数为N<, = 3k (k-l)/2;对于 p>O.C(O) = 3(k-l)/2(2k-l)；在 p = 0 时.连 接第i个节点的两个邻近节点仍然是邻近节点！1连接概率为(l-p)X£到1/N阶。个节点的邻近节点Z间的平均连接数就为N“(1 I)J + O(1/N)集群系数

16、C(p)为G的平均率我们用C(P>來衷示：芒(1),贮*(1一1几我 们可以把该式简m的描述为C(p)C(0)(l-p)并IL受N的 影响很小总之.只耍网络足够大水世界行为在0<p<l范围 内存定会出现。3. 3自由标度网络(Scale free网络)尽管小世界模型能很好的刻画现实世界的小世界性和高聚 集性但ER随机网络模型和WS小世界模型的一个共同性质 是：网络连结物的分布在一个平均值处达到高峰并按指数形式 进行衰减也就是说随机网络理论和WS模醴足不JI备帚函数 形式的。而实证结果却衣明人参数人规模网络都是自由林度的.也就是它们的度分布在X k较大时服从算函数形式见衷2所科

17、技信息博士专家论坛2006年第3期格局。为了尽快给农村线培养批留得住、用得上的技术和管 理人才教育部决定利用现代远程技术从今年7月起在全国百 县实施“ 村名人学生计划”。这教育计划的招生对彖主要 是高中毕业或具冇同等学力的农村青年：同时对这部分学生采 取计划单列，注册入学不转户口就地上学，自主学习，累计学 分等特殊政策学生修满规定的学分可颁发国家承认的学方文 凭。这重要的教仔举描将会极人地激活农村教存.促进农村 务项教冇和人力资源的丿发。除此Z外还鉴善于把我们过去经 常性开展的对广人农民进行的政治思想道徳教疗也纳入到人教 育的系统之.中.把这种政治思想的教冇与我们现实的冬种教冇 形式右机地结合

18、起来。耍从农村的实际出发工足于挖掘、利用 和整介现冇的教冇资源.并在此丛础上建立起个开放的、多元 的、允满生机与活力的农村教育体系与格局。譬如当前农村基 础教仃待别圧小学阶段的教仃山】：适龄儿童逐年减少开始出 现r部分教疗资源闲胃的悄况包括部分校舍和师资力量得不 到仃效利川。教育部门应当抓住这样的契机利用闲量教育资源 来满足农村成人教育、枳业教育以及延伸到农村的高等教冇的 需耍以最人限度地发挥现有教有资源的作用和效益。耍打破过 去氏期存< 条块分割、存类教育Z间互不往来的状况使务种不 同的教疔内容和形式都能在开发农村人力资源的实我屮得到统-和协调要改变传统的单、僵化的教育模式，创设多种多

19、样、 生动活泼的教育培训方式和方法，让我们的教育充分地满足和 适应农民的实际需要和学习的可能。坐介教疗资源协调乞方而的教疗行动，构建农村人教疗怡 局地方党委和政府特别是县、乡 级党委和政府必须允分、冇 效地发挥其应有的领导、指导和协调的作用与功能0以全面提高 和改裨农民素质为宗旨的新的人教冇格局相对于过去那种以廉 础教育为主的狭义教育而言匸作的内涵、目标和任务都更为复 杂、艰巨.在我国现冇的情况下离开了地方党委和政府坚强冇 力的领导与协调优先发展教育构建农村人教疗体系的目标就 不可能实现。贫困地区的地方党委、政府应以科学发展观为指 导貞止把全面发展教育促进农民素质的提局弓改善作为第一 耍务切实

20、地抓起來.抓落实。参考文献1 张纯元消除贫困的人口对策研究M 北京，高等教育 IB 版社.19962 刘道兴、张要杰.国家投资战略匝点向农村转移的思考 J.中州学刊.2003(1)温家宝牢固树立和认真落实科学发展观J人民日 报.2004.2.29(1)3科技信息博士专家论坛2006年第3期3科技信息博士专家论坛2006年第3期(I：接第5页)朿连但节点数是不变的；(2)在产生新连结时随 机网络和小世界模型具有相同的概率但在现实网络屮这是不 现实的。Barabasi和Albert “提出在自由标度网络中自组织的 两个部分是増氏的和优先连接的这就揭示了一个爭实，随着新 节点的加入网络不断增加.新的

21、节点优先连接到有)< 量连接物 的竹点上也就足通常所说的”盘人越當”现彖。ba模型n法描 述如下：(1) 增长：开始于较少的节点数§(mo),在每个时间间隔增 添个II有m(ni£m“)条边的新节点连接这个新节点到m个 不同的已经存在于系统中的节点上.(2) 择优连接：在选择新节点的连接点时假设新节点连接 到节点i的概率打取决于节点i的度数即I (ki)=根抑:以上的观则经过I时间间隔后，该算法程序产生具 冇N = i+m"个节点以及mi条边的网络。研究结果衣明：经过 氏时间的演化后模型的度分布是与时间无关的渐进分布且与 系统规模无关，模型中网络具有帚律型分

22、布，幕律特征P(k) k舄指数r = 34总结与展望小世界、自由标度网络理论的提出，便M杂网络的研究显/J < 出极强的生命力从细菌、细胞和蛋门质系统到科学家之间的 合作论文Z间的引证联系以及人熨的Internet和WWW网 络等它们都构成某种网络系统也构成某种父杂网络系统而 复杂网络研究恰恰在这点上发现r他们同时具冇的3个主要特 征，小世界、自由标度和高聚集性。如今科学家正是基于这三个 丛本特征进行深入研究方向上嗖集中在网络的结构和性须、网 络宏观性质的微观生成机制、网络中的动力学行为等方而。网络研究的前铢及其广阔特别是在以下儿个方而还有待 人们进-步的研究：(1)对网络结构和性质的研

23、究有待系统化。 忖前用來刻闻网络宏观结构的咸本持征量主耍冇度分布、平均 最短賂径、聚集系数近年来乂陆续提出新的网络特征量，如相 关系数(correlation coefficient) 和介数(betweenness) ' ，但 是这些特征量能否全而和详细地刻wi结构罪常夏杂的頁实网 络？这都是需要进步研究的。(2探询网络孑种宏观牲质的微 观机制一直是网络研究中-项挑战性的工作目前在对网络的 自由标度性质、小世界性质的微观形成机制有淀的认识，对r 度关联(degree correlation ) H 团体结构(community structure)、分层结构(hierarchical organization)宏观性质的 微观生成机制的探索还需耍进步的研究。(3)研究网络中的动 力学行为就是考察具冇不同结构的网络中发生的乂种动力学过 程的特