（计算机软件与理论专业论文）p2p系统模型的研究.pdf

两华大学硕十学位论文 p 2 p 系统模型的研究 计算机软件与理论 研究生王晓燕指导教师刘克剑 经过大量的研究发现，许多现实系统都可以用一个复杂网络来描述。这些 复杂网络具有一些相同的特征，如网络平均路径长度较小、聚类系数较大、节点 度分度服从幂律分布、小世界以及无标度特性等，这些特性是复杂网络为完成某 些特定功能而逐渐演化的结果。复杂网络逐渐成为研究复杂系统的一种重要方 法，而复杂网络模型是研究复杂网络的重要工具。 p 2 p 网络是一种分布式网络，是目前复杂网络研究的热点，建立体现p 2 p 网 络真实特征的网络模型对研究网络的结构和行为有重要的意义。目前对p 2 p 网 络模型的研究主要集中在p 2 p 的路由网络模型上，路由网络模型的研究旨在为 解决p 2 p 的可扩展性问题、负载问题等，但是它们并不能描述p 2 p 网络特征。 本文提出了一种新的p 2 p 网络模型建立方法： 针对现有的网络模型模拟现实世界的局限性，本文结合现实网络中节点以组 的方式增长、局部择优( 全局择优对于一些大型的网络是不现实的，一般的，新 加入的节点不需要一定要连接到原来网络度数最大的节点上，它可能也没有能力 去完全了解整个网络的情况，或者说了解全局信息的成本太高) 和节点吸引因子 ( 在真实系统中，新增节点不仅与网络中已有的度数较高的节点连接，而且与吸 引因子较大的节点连接。吸引因子也称节点本身具有的吸引力的大小) 的特性， 以新的算法生成改进的网络模型。通过模型的静态统计量( 度分布、平均路径长 度、聚集系数) 参数与b a 模型的参数进行比较，结果证实了改进的网络模型 的拓扑结构更接近于p 2 p 网络。 关键词：复杂网络；p 2 p ：b a 模型；网络模型；静态统计量 两华大学硕士学位论文 s t u d yo fm o d e l s o fp 2 pn e t w o r k s c o m p u t e rs o f t w a r ea n dt h e o r y m d c a n d i d a t e w a n gx i a o y a ns u p e r v i s o r l i uk e j i a n a c c o r d i n gt or e c e n ty e a r s r e s e a r c h e s ，w ef o u n dt h a tm a n yr e a ls y s t e m sc a nb e d e s c r i b e dw i t hac o m p l e xn e t w o r k t h e s ec o m p l e xn e t w o r k sh a v es o m ec o m m o n c h a r a c t e r i s t i c s ，s u c h a ss m a l l a v e r a g ep a t hl e n g t h ，b i gc l u s t e r i n gc o e f f i c i e n t ， p o w e r - l a wd e g r e ed i s t r i b u t i o n ，s m a l lw o r l da n ds c a l e f r e ee t c , t h e s ec h a r a c t e r i s t i c s a r et h er e s u l t so fg r a d u a le v o l u t i o nf o rt h ec o m p l e xn e t w o r k st oa c c o m p l i s hs o m e s p e c i a lf u n c t i o n a l i t y c o m p l e xn e t w o r k sb e c a m ea ni m p o r t a n tw a yt os t u d yc o m p l e x s y s t e m s ，a n df u r t h e r m o r e ，t h em o d e l so fc o m p l e xn e t w o r k sa r ei m p o r t a n tt o o l st o s t u d yt h ec o m p l e xn e t w o r k s p 2 pi sad i s t r i b u t e dn e t w o r k ，i ti st h eh o tp o i n to fp 2 pn e t w o r k t oe s t a b l i s ha m o d e lw h i c hc a np e r f e c t l yd e s c r i b et h er e a l l yn e t w o r k si ss i g n i f i c a n th e l p f u lt ot h e r e s e a r c ho nt h en e t w o r k ss t r u c t u r ea n db e h a v i o r n o w a d a y s , i no r d e rt op r e s e n ta n a v a i l a b l ea n df e a s i b l es c h e m ef o rp 2 ps y s t e m ，t h es t u d yo np 2 pn e t w o r km o d e l m a i n l yf o c u so nt h er o u t i n gs t r a t e g i e s ，a i m e da ts c a l a b i l i t y ，l o a db a l a n c i n g , a gw e l la s t h em a n a g e m e n t b u ti tc a n n o td e s c r i b et h ep 2 pn e t w o r k i nt h i st h e s i s , an e w m o d e la b o u tp 2 pn e t w o r ki sp r e s e n t e d ： r e g a r d i n go fs o m el i m i t a t i o no fe x i s t e dn e t w o r km o d e l st om o d e lt h er e a l i s t i c w o r l d ，s o m ee x t e n d i n gi t sa l g o r i t h m ，an e wn e t w o r km o d e li sb ef o r m e di nt h et h e s i s ， a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fg r o u pg r o w i n ga n dc h o o s i n gt h eb e s tf r o mt h ep a r t o ft h en e t w o r k ( t h eg l o b a lo p t i m u mi ns o m el a r g e - s c a l en e t w o r ki su n r e a l i s t i ca n d u n f e a s i b l e ，i ng e n e r a l ，t h en e wn o d em a yn o th a v et h ea b i l i t yt of u l l yu n d e r s t a n dt h e s i t u a t i o no ft h ee n t i r en e t w o r k ，o rt h ec o s tt og e tt h eo v e r a l li n f o r m a t i o ni st o oh i g h ，s o i td o e sn o tn e e dt oc o n n e c tt ot h el a r g e s td e g r e eo ft h eo r i g i n a ln e t w o r kn o d e s ) ，a n d l i 两华大学硕十学位论文 t h ea t t r a c t i v e n e s sf a c t o ro fn o d e s ( i nt h er e a ls y s t e m ，t h en e wn o d ec o n n e c tt ot h en o d e w i t hal a r g e rd e g r e eo ran o d ew i t hh i g ha na t t r a c t i v e n e s sf a c t o r a t t r a c t i v e n e s sf a c t o r i sa l s ok n o w na st h ea t t r a c t i v e n e s so ft h en o d ei t s e l f ) a f t e rac o m p a r i s o no ft h e i r b e h a v i o rb a s eo nt h ep a r a m e t e r so ft h es t a t i cs t a t i s t i c s ( d g r e ed i s t r i b u t i o n 、a v e r a g ep a t h l e n g t h 、c l u s t e r i n gc o e f f i c i e n t ) ，i tc a nb ee a s i l yf i n dt h a tt h et o p o l o g i c a ls t r u c t u r ea n d d e v e l o p m e n to ft h en e w m o d e li sm o r ec l o s et op 2 pn e t w o r k s k e y w o r d s ：c o m p l e xn e t w o r k ；p 2 p ；s c a l e f r e e ；n e t w o r km o d e l ；s t a t i cs t a t i s t i c s i i i 两华大学硕+ 学位论文 8 声明 本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及取得 的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确地说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成果 归西华大学所有，特此声明。 作者签名：豌摄四年，月2 日 导师签名：弓k 名，l 【 5 3 s 月日日 f 年 a 眄华大学硕十学位论文 9 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅，西华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 i 、保密口，在年解密后适用本授权书； 2 、不保密吖适用本授权书。 ( 请在以上口内划4 ) 学位论文作者签名：王1 琵泰 日期： 0 1 s 、2 6 屈 怍叩f ，9弘 名j 签 。 师 教： 导期指日 两华人学硕士学位论文 i 引言 1 1 研究背景 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述l l j l 2 1 。一 个典型的网络是由许多节点与连接两个节点的一些边组成的，其中节点用来代表 真实系统中不同的个体，而边则用来表示个体问的关系，往往是两个节点之间具 有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点被看作是相 邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络； 计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电 缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、食物链网络等 危占 弋ro 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都 是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态 就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那 么，什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来，对这个问 题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧拉格子，它看起来 像是格子体恤衫上的花纹；又或者最近邻环网，它会让你想到一群人手牵着手围 着篝火跳圆圈舞。到了十九世纪五十年代末，数学家们想出了一种新的构造网络 的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据概 率决定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被 认为是描述真实系统最好的网络。直到最近几年，由于计算机数据处理和计算能 力的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机网络， 而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复 杂网络，对于他们的研究标志着第三阶段的到来。 两华人学硕十学位论文 著名的物理学家霍金认为：二十一世纪是复杂性的世纪。复杂网络的研究是 复杂性理论研究的一部分，作为研究复杂性科学和复杂系统的有力工具，复杂网 络为研究复杂性提供了全新的视角1 3 l i 引。复杂网络借助于图论和统计物理的一些 方法，可以用来捕捉并描述系统的演化机制、演化规律( 结构) 和整体行为( 功 能) ，这是复杂网络的研究蓬勃发展的主要原因之一。 1 2 复杂网络应用及研究意义 复杂网络( 特别是小世界网络和无尺度网络) 刚一提出，就呈现出广阔的应 用前景，其应用领域涉及工程技术、社会、政治、医药、经济、管理等不同方面。 在过去几年里，不同领域的研究者发现，包括万维网、细胞代谢系统、好莱坞的 演员网络在内的许多现实网络，都是无尺度网络，它们由少数几个具有众多连结 的节点所支配，这些重要节点通常称为集散节点。无尺度网络对意外故障具有惊 人的承受力，但面对协同式攻击时则很脆弱。这些新发现极大地改变了人们对复 杂外部世界的认识，让人们认识到了以前的理论尚未涉及的问题：各种复杂系统 具有相同的严格结构，都受制于某些基本的法则，这些法则似乎可同等地适用于 细胞、计算机、语言和社会。认识这些法则，可以将其应用到不同领域，帮助人 们解决一系列重要问题。 首先，复杂网络理论可以用于保护许多现实系统的正常运行。因特网、电力 网、航空网、万维网、电子邮件网【5 j 1 6 l 、食物链网【7 】【8 l 等网络与我们的生活息息 相关，人们对这些网络的依赖程度r 益增强，凸现了一个广受关注的问题；这些 网络到底有多可靠呢? 2 0 0 0 年，爱虫病毒侵犯了英国议会的电子邮件系统，导 致该系统瘫痪；同年，一场暴风雨袭击芝加哥，致使h a r e 机场关闭，由此而影 响了全美航班1 9 l ；2 0 0 3 年美加电网的大崩溃事故让纽约人感到惶恐不安1 9 l ，当前， 人类赖以生存的生态系统不断遭到破坏己经危及到人类的生存环境，等等。从这 些现象可以自然地提出下面的问题：计算机病毒如何在万维网上传播而导致流 行? 病毒如何通过电子邮件传播? 人们如何控制病毒传播i l o l ? 面对黑客的攻 击，应该采取何种对策? 怎样设计出承受意外故障较强的网络( 如电力网、航空 2 两华人学硕：十：学位论文 网) ? 怎样保持当前不断恶化的生态系统的平衡? 这些问题的解决都与复杂网络 的研究有关，开展好复杂网络稳定性的研究，对于互联网、电力网1 1 1 】1 1 2 】、航空 i 双j 1 3 】1 1 4 l 网络的设计保护及基础设施网络的保护1 1 5 】具有重要的意义，也可以有效 地防止黑客侵入互联网、阻止病毒在万维网上传播蔓延。 复杂网络在社会领域也有广阔的应用。传染病( 如艾滋病、非典、禽流感等) 对人类的威胁很大：艾滋病让人们不寒而栗：2 0 0 3 年的非典对于宏观经济和人 类的生命安全都产生了巨大的负面影响。那么在特定的社会网络中，传染病如何 通过接触关系传播而导致流行呢? 决策者如何控制这些疾病，将损失降到最低限 度呢? 这些问题或许可以从复杂网络那里寻找答案。最近几年，科学家们考虑了 不同现实系统的主要特征，提出了许多有针对性的疾病免疫方法1 1 6 - 2 0 、预防和免 疫提供了科学的方案。譬如，用复杂网络理论可以很好地预测非典爆发的多样性 【2 l 捌、了解疾病传播的动态性，为决策者控制流行病蔓延、改善公共卫生提供 有效的手段【2 3 1 。在当今社会，稳定是经济发展的基础，流言飞语往往会影响社 会的安定。复杂网络理论可以用于模拟社会上谣言传播过程，对控制传言的扩散、 降低其负面影响具有一定的借鉴意义1 2 4 h 矧。 除社会领域外，复杂网络在政治方面也开始显示出实际的应用价值。当今世 界上，恐怖主义已被列为2 1 世纪的十大危害之一，发生在美国的9 1 1 事件让全 美至今仍有后怕。对于恐怖主义、犯罪组织这些需要破坏的网络，人们可以利用 复杂网络理论，通过捉拿逮捕其主要人物，就可摧毁网络，使其功能失常，以维 护人类社会政治的稳定。网络理论还可用于揭示政府议员的组织、层次关系，甚 至可以成功模拟政治选举，分析一些因素对选举结果的影响。 复杂网络也为人们认识语言文字、获取知识提供了新的有力工具，是人们研 究知识管理的新途径。语言是人类区别动物的主要标志之一，可是我们今天使用 的语言是如何演化的呢? 为什么只有人类才具有复杂语言呢? 人脑为什么接触 到某一事物后，可以很快的联想到其它事物呢? 现实复杂网络中的语言网作为语 言演化研究的新方法与新尝试，其在认知科学中意义很大，如语言网的小世界特 性可以部分地解释人脑具有很快的联想功能等! 目前正处在信息( 知识) 时代， 信息时代需要时代信息，可是，在信息网络( 如万维网) 中信息如何传播呢? 人 们如何尽快获取所需要的信息呢? 复杂网络不但对于专家领域知识的发现及表 3 两华人学硕十学位论文 示方法有一定的意义哪，而且在知识学习与获取方面，复杂网络也可一显身手。 另外，根据万维网特殊的复杂结构，人们可以提出相应的搜索算法，为获取所需 信息提供方便。 复杂网络在经济、管理领域也有着重要的实际意义。利用复杂网络理论了解 公司、产业与经济之间的连结方式，有助于监控和预防大规模的经济衰退。在管 理领域，复杂网络的演化模型研究决策对经济的发展起着关键性的作用，同一个 人可以在多个组织内兼任董事。建立公司董事网，使得分析决策的动态性成为可 能。另外，研究流行病在复杂网络中的传播现象，为市场人员传播新产品和新时 尚提供了新方法、新理论。许多市场营销专家都在大力研究扩散理论，出于各种 商业目的，他们需要引发流行而不是遏制流行，于是他们提出了所谓的病毒式行 销，这一方法实用可行，但一直没有公认的理论基础，新近的复杂网络研究，为 更严谨地探讨这些现象，提供了一个科学的框架和数学工具。利用网络理论，还 可以分析公司等组织内部及组织之间的信息传播、信息交换、组织的综合评价及 排名。在复杂的市场环境下，复杂网络还可用于对金融产品进行定价等。 除了以上应用外，复杂网络的研究，对于其他许多领域也是有价值的。例如， 将小世界的思想用于b p 网络，可以减少b p 网络的学习时间和学习误差，使得 b p 网可以更好地用于数据挖掘、语音识别、图像处理及模式识别等多个领域； 另外，将复杂网络用于h o p f i e l d 网络，可以改变神经网络的联想记忆功能。特别 地，复杂网络对于系统科学有着极其重要的理论意义和工程应用价值，中国系统 工程学会将复杂网络对系统工程与系统科学的贡献作了深远的展望。众所周知， 结构是客观事物的基本属性，也是各学科领域研究的一个重要问题。虽然每门学 科在其研究对象的结构方面，都有非常丰富的具体成果，但从系统学的高度，横 跨物质系统、生物系统和社会经济系统的具体研究成果，也就是系统学层面的成 果还不多，其系统层面的内涵迄今还没有完备的阐述。 复杂网络是综合以往的自组织理论、非线性理论与复杂性理论研究的成果而 形成的崭新的理论。复杂网络的兴起，为系统科学的研究开拓了视野，提供了全 新的视角。复杂网络作为复杂系统的一般抽象和描述方式，作为复杂系统的结构 形态，它突出强调了系统结构的拓扑特征。可以说，任何复杂系统都可以当作复 杂网络来研究。以复杂网络形式研究复杂系统，可以加深人们对系统结构的深入 4 两华大学硕十学位论文 了解，随着复杂网络研究的深入以及用网络理论研究系统演化工作的深入开展， 复杂系统演化的研究必将出现新的突破性结果；当然也可以从系统科学的角度来 研究网络，这也是网络研究的新视角。可见，利用网络理论对系统进行研究，是 系统科学一种新的研究手段。本文拟以复杂网络的演化模型研究作为切入点，深 入开展复杂系统结构的研究。因此，本文的研究十分有意义。 广泛的应用前景使得复杂网络的研究倍受国内外的密切关注，引起了不同学 科的高度重视。在2 0 0 4 年召开的国际统计物理大会( 每三年召开一次) 上，第 一个报告就是关于复杂网络方面的研究。在国内，包括中国科学技术大学、上海 交通大学、大连理工大学等在内的许多院校，都专门成立了复杂网络研究中心和 研究小组。近些年，国家自然科学基金委员会每年都设置关于复杂网络的基金项 目或重点基金项目。目前，对复杂网络的研究己成为极其重要而且富有挑战性的 前沿科研课题。这些进一步说明，选择从复杂网络入手，研究p 2 p 网络模型作为 硕士学位研究课题具有一定的实际背景，有重要的理论意义和应用价值。 1 3 本文的研究内容与结构 1 3 1 本文的研究内容 目前，复杂网络的研究主要集中在三个领域：一是网络生成机制及演化模型， 通过生成机制建立模型，模拟真实网络行为；二是复杂网络的稳定性，研究限制 条件对网络几何特性的影响，如复杂网络承受意外故障和蓄意攻击的能力等；三 是复杂网络上的动力学，是人们研究复杂网络的最终目标，也就是超越网络扑结 构，掌握建立在这些网络上的系统的工作方式和机理，认识复杂系统内部的难以 理解的动力学：如复杂网络上的同步，疾病、信息、知识、舆论如何复杂网络上 的传播等。 本论文在研究了随机网络拓扑结构、小世界网络拓扑结构、无标度网络拓扑 结构等的基础上，分析了目前复杂网络拓扑结构建模的缺陷与不足，从复杂网络 地动力学角度出发，建立了基于复杂网络理论的p 2 p 网络模型，本文的研究重 5 两华大学硕士学位论文 点主要集中在研究p 2 p 网络的演化机制及模型，再现现实系统的主要拓扑特性。 主要研究内容如下： ( 1 ) 研究分析了的几类典型网络( 随机网络、小世界网络、无标度网络) 的统计 特性及其拓扑结构，主要研究了目前现实生活中普遍存在的无标度网络的拓扑结 构及其生成机理。 ( 2 ) 构造建立了p 2 p 复杂网络模型，并用无标度网络及指数网络进行了验证。从 度分布、最短路径长度等等去比较改进的模型与其它模型的比较。 本文建立的模型并不一定是最优的网络模型，是从现实网络的特性出发，以 便使得改进的模型更具有现实网络的特性。 1 3 2 本文结构 本文各章内容安排如下： 第一章绪论主要介绍了课题背景，概括国内外当前在复杂网络理论及复杂网 络拓扑结构建模研究方面的现状和存在的问题。最后针对研究现状提出本论文的 研究内容以及文章的结构框架。 第二章复杂网络理论基础主要根据目前复杂网络研究的现状及特点，总结介 绍了网络图论的基本理论以及复杂网络的基本概念和理论知识，并介绍了复杂网 络的内在统计特征。 第三章几类网络拓扑模型主要介绍了从十八世纪图论出现以来几类具有代 表性的网络拓扑构造算法及其结构特征。以及几个学者从复杂网络模型处发改进 的几个模型，重点介绍了无标度网络拓扑结构的构造算法结构及其结构的特殊 性。 第四章p 2 p 复杂网络模型的构造，是本文的重点。我们知道p 2 p 是一种复 杂网络，以前对于p 2 p 模型的研究是针对性的解决了p 2 p 路由技术中某几方面 的问题，而我的主要任务是从复杂网络出发，研究p 2 p 网络模型，建立体现p 2 p 网络真实特征的网络模型对研究网络的结构和行为有重要的意义。针对现有的网 络模型模拟现实世界的局限性，在b - a 模型算法的基础上作了修改，本文结合 6 西华大学硕十学位论文 现实网络中节点以组的方式增长、局部择优和节点吸引因子的特性，以新的算法 生成改进的网络模型。通过模型的静态统计量( 度分布、平均路径长度、聚集系 数) 参数与b a 模型的参数进行比较，结果证实了改进的网络模型更接近于现 实网络。 第五章总结本章对研究内容进行了总结，对将来一步的工作进行了展望。 1 4 本文的创新点 本论文的创新点如下： 本文针对p 2 p 网络现有模型的不足，结合复杂网络现有的小世界模型、b a 模型及其演化模型的特点，研究p 2 p 网络的生成机制，考虑到现实网络中节点 以组的方式增长、局部择优和节点吸引因子的特性，以新的算法生成改进的网络 模型。u c i n e t 工具，得出模型的静态统计量( 平均路径长度、聚集系数) 参数与 b a 模型的参数进行比较，结果证实了改进的网络模型更接近于现实网络。 7 两华大学硕+ 学位论文 2 复杂网络理论基础 2 1 网络的定义及表示方式 网络在数学上用图来表示，图的研究最早起源于1 8 世纪瑞士著名数学家 e u l e r 的哥尼斯堡七桥问题。复杂网络可以用图论的语言和符号精确简洁的加以 描述。从统计物理学的角度来看，网络是一个包含了大量个体以及个体之间相互 作用的系统，是把某种现象或某种关系抽象为个体( 顶点) 以及个体之问的相互作 用( 边) 而形成的用来描述这一现象或关系的刚2 6 1 。以社会网络为例，顶点可以代 表不同性别、国籍、地域、年龄、收入等的人，而边可以代表相互间的友谊、职 业上的交往、空间上的接近等关系。一个具体网络可能抽象为一个由点集v 和 边集e 组成的图g = ( v ，e ) 。节点数记为n - i v l ，边数记为m i e i 。e 中每条边都 有v 中一对点与之对应。v 中元素个数和e 中元素的个数分别称为网络的阶数 和边数。阶数和边数都有限的图为有限图闭。 如果任意点对( i ，j ) 与( j ，i ) 对应同一条边，则该网络称为无向网络( u n d i r e c t e d n e t w o r k ) ，否则称为有向网络( d i r e c t e dn e t w o r k ) 。例如个人之间电话或电子邮件 信息传递网络就是有向的。如果给每条边都赋予相应的权值，那么该网络就称为 加权网络( w e i g h t e dn e t w o r k ) ，否则称为无权网络( u n w e i g h t e dn e t w o r k ) 。 如果网络中包含两种不同类型的顶点，边仅存在于不同类型的顶点之间，则 称该网络为隶属网络，或称二部图。例如西华大学的学生与四川大学的学生之间 的友谊关系。图2 1 给出了几个不同类型的网络的例子。除了特殊说明外，本论 文下面所说的网络都是无向无权的网络，并且假设没有重边和自环( 即任意两个 节点之间至多只有一条边，且没有以同一个节点为起点和终点的边) 。 8 两华大学硕十学位论文 o 弋留一一 d ) f i g u r e2 1e x a m p l e so f d i f f e r e n tt y p e so fn e t w o r k s ( a ) as i n g l et y p eo f n o d e sa n de d g e so ft h eu n d i r e c t e dn e t w o r k ； ( b ) d i f f e r e n tt y p e so f n o d e sa n de d g e so ft h eu n d i r e c t e dn e t w o r k ( c ) n o d e sa n dv a r i a t i o n so ft h ew e i g h to ne d g en o n o r i e n t e dn e t w o r k ( d ) d i r e c t e dn e t w o r k 图2 1 不同类型网络的例子 ( a ) 单一类型。1 了点和边的无向网络；( b ) 不同类型节点和边的无向网络； ( c ) 节点和边权重变化的无向网络；( d ) 有向网络 2 2 复杂网络的基本理论和统计特征 2 2 i 复杂网络的基本理论 网络( n e t w o r k ) 是一类描述自然和工程系统的模型。网络可以看作是具有一定 特征和功能的基本个体的集合，而个体间是相互关联、相互影响的。而复杂网络 是具有海量的节点的和复杂连接拓扑结构的网络模型。在现实世界中，有很多系 统都可以看作复杂网络。如图2 2 所示，万维网( w w w ) 可以看作由各个站点 ( w e b s i t e ) 作为节点，链接( 1 i n k ) 作为边的复杂网络；英特儿网( i n t e m e t ) 可以看作由 路由器或网关作为节点，相互连接作为边的复杂网络。再如图2 3 所示，食物链 网是由各种生物作为节点，相互之间的食物关系作为边的复杂网络；科学家合作 9 两华大学硕士学位论文 网是以人作为节点，其合作关系作为边的复杂网络等等。 w o r l 乎w i d ew 朗 l n t e r n e t 赢粝黛 f i g u r e2 2 n e t w o r ks l r u c t u r co f t h c w o r l d w i d e w e b a n d t h e i n t c r n e t ： ( a ) n c l w o r ks u l l c l u eo f t h e w o r l d w i d e w e b ； c o ) n e t w o r ks t r u c t u r e o f t h e i n t e r n e ! 圈2 2 万维两及英特儿网的婀络结构： ( a ) 万维阿的呵络结构凹：( b ) 英特儿网的网络结构倒 ( a ) ( b ) 囊赫 。每 二 f i g u r e2 3 t h r e e t y p e so f n e t w o r ks t m c t u z c ： 0 ) f o o dc h a i nn e t w o r ko f t h eo r g a n i s m i na f r e s h w a t e r l a k e ( b ) a p a r t n e r s h i pb e t w e e ns c i e n t i s t s n e t w o r k i nar e s e a r c h i n s t i t u t e 扣) s e x u a lr e l a t i o n s b e t w e e n t h eh u m a n i n d i v i d u a l s r n e t w o r k 图2 3 三种类型的网络结构：( a ) 一个菠水湖泊中生物的食物链网络： b ) 某一研究机构中科学家之间的台作关系网：( c ) 人类个体之间的性关系网。 1 0 。蟪 ， 两华大学硕士学位论文 对复杂网络研究的已有成果中，科学家发现绝大多数实际的复杂网络都具有 以下几个基本特征【3 2 1 1 3 3 1 ( 1 ) 网络行为的统计性：网络节点数可以有成百上千万，甚至更多，从而使得大 规模性的网络行为具有统计性特征； ( 2 ) 节点动力学行为的复杂性：各个节点本身可以是非线性系统，具有分俞和混 沌等非线性动力学行为； ( 3 ) 网络连接的稀疏性：一个n 个节点的具有全局耦合结构的网络的连接数目为 o ( n 2 ) ，而实际大型网络的连接数目通常为o ( ； ( 4 ) 连接结构的复杂性：网络连接结构既非完全规则也非完全随机，而是还存在 一些其它结构特征； 以上几种特征，反映了实际网络的复杂性。一方面，它具有无序演化的特征， 另一方面，它也具有增加有序程度的演化特征。遗憾的是，就目前而言，科学家 们还没有给出复杂网络精确严格的定义，从这几年的研究来看，之所以称其为复 杂网络，大致上包含以下几层意思：首先，它是大量真实复杂系统的拓扑抽象； 其次，它至少在感觉上比规则网络和随机网络复杂，因为我们可以很容易地生成 规则和随机网络，但就目前而言，还没有一种简单方法能够生成完全符合真实统 计特征的网络；最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此 对它的研究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。 2 2 2 复杂网络的统计特征 用网络的观点描述客观世界起源于1 7 3 6 年德国数学家欧拉解决哥尼斯误七 桥问题。经典图论对于网络拓扑结构的研究是从节点与节点的连接度、构成图的 连通性等方面入手分析随机网络的，而近年发展最快的复杂网络研究是用概率的 方法研究网络的生长演化。为了便于对复杂网络的研究，我们需要找出一些能有 效描述其结构特点的几何量。目前在文献中出现的几何量有：度分布、最短路径、 聚类系数、介数、平均度、平均距离、连通片分布、边密度、相关系数等。它们 】1 西华大学硕十学位论文 分别描述复杂网络不同方面的结构特点，综合起来能够比较全面的描述复杂网络 的内在特征。 随着研究的深入，复杂网络中许多新的概念和度量不同程度地被引入和应用 进来，其中有三个基本的复杂网络统计特征尤为突出：度分布( d e g r e e d i s t r i b u t i o n ) 、聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 和平均路径长度( a v e r a g ep a t hl e n g t h ) 。 实际上，w a t t s 和s t r o g a t z 提出小世界网络模型的初衷，就是想建立一个即具有 类似于随机图的较小的平均路径长度，又具有类似于规则网络的较大的聚类系数 的网络模型。另一方面，b a r a b f i s i 和a l b e r t 提出的无标度网络模型，则是基于许 多实际网络的度分布具有幂率( p o w e r 1 a w ) ? g 式的事实。复杂网络研究的不同之处 在于首先从统计角度考察网络中大规模节点及其连接之问的性质，这些性质的不 同意味着不同的网络内部结构，而网络内部结构的不同导致系统功能有所差异。 所以，对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步，下 面简述之。 l 度和度分布 度是描述一个网络图的最基本的术语，也是单独节点的属性中简单而又重要 的概念。节点 ，；的度k ；定义为与该节点相连接的边的数目。直观上看，一个节点 的度越大就意味着这个节点在某种意义上越“重要 。网络中所有节点h 的度七； 的平均值称为网络的( 节点) 平均度，记为( k ) 。 网络中节点的度的分布情况可用分布函数p ( 七) 来描述。度分布函数反映了网 络系统的宏观统计特征。p ) 表示的是一个随机选定的节点的度恰好为k 的概率 分布。有时度分布也可近似理解为网络中度为k 的节点的个数占节点总个数n 的比例，即p ( k ) = f r e q u e n c e ( 七) 。其中仃e q u e n c e ( k ) 为网络中节点的度为 k 的节点数目。 1 2 西华大学硕七学位论文 v 4 v7 2 f i g u r e2 4as i m p l eu n d i r e c t e dc o n n e c t e dg r a p hw i t he i g h tn o d e s 图2 4 八个节点的无向简单连通图 图2 4 为8 个节点的无向无权的简单连通图。节点集合为 v = l ，l ，v 2 ，v 3 ， ，4 ，v 5 ，v 6 ，y 7 ，) ，节点的度分布为 p ( 4 ) = 1 8 ，p ( 3 ) = 1 4 ，p ( 2 ) = j 8 , p ( 1 ) = 1 2 。 规则的格子有着简单的度序列，因为所有的节点具有相同的度，所以其度分 布为d e t l a 分布，它是单个尖峰。网络中的任何随机化倾向都将使这个尖峰的形 状变宽。e r d 6 s 和r 6 n y ! 矧提出的随机网络中，节点之间以概率p 相连接，节点度 分布服从二项分布或大1 1 极限下的p o i s s o n 分布。其形状在远离峰值仅) 处呈指 数下降。这意味着当k 之( k ) 时，度为k 的节点实际上是不存在的。w a t t s 和s t r o g a t z 提出的小世界网络中，节点连接度分布的形态与随机网络相似，但是当小世界网 络模型初始的节点度相对较大时，它的节点连接度分布呈指数规律衰减 ( p 他) a ，其中0 a 1 d 茸 ( 2 4 ) 壶( + 1 ) 舒 其中，n 为网络节点数。网络的平均路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理，在公式( 2 4 ) 中包含了节点到自身 的距离( 当然该距离为零) 。如果不考虑节点到自身的距离，那么要在公式( 2 4 ) 的右端乘以因子( + 1 ) ( 一1 ) 。在实际应用中，这么小的差别是完全可以忽略 不计的。一个含有n 个节点和m 条边的网络的平均路径长度可以用时间量级为 o ( m n ) 的广度优先搜索算法来确定。 例如，对于图2 4 所示的一个包含8 个节点和8 条边的简单网络，我们有 d = d 弛- - 4 ，l ；2 2 1 4 。在朋友关系网络中，l 是连接网络内两个人之间最短关系 链中的朋友的平均个数。近期研究发现，尽管许多实际的复杂网络的节点数巨大， 网络的平均路径长度却小得惊人。具体地说，一个网络平均顶点度固定，l 的值 随网络大小以对数的速度或慢于对数的速度增长，那么称此网络具有小世界效 应。小世界效应具有很明显的实际意义。 在w a t t s 和s t r o g a t z 关于复杂网络的小世界现象的研究，以及b a r a b 缸i 和 a l b e r t 关于复杂网络的无标度特征的工作之后，人们对来自不同领域的大量实际 网络的拓扑结构特征进行了广泛的实证性研究，表2 1 列出了部分结果。测量的 性质包括：有向或无向、节点总数n 、边的总数m 、平均度数k 、平均路径长度 l 、聚类系数c 。表中的空格表示没有可靠的数据。 1 6 两华大学硕士学位论文 表2 1 各种实际网络的基本统计数据 t a b l e2 1v a r i o u so fa c t u a ln e t w o r kt h eb a s i cs t a t i s t i c a ld a t a 网络 类型nm( k ) lc 社电影演员无向 4 4 9 9 1 32 5 5 1 6 4 8 21 1 33 4 80 7 8 会 合作生物学家 无向1 5 2 0 2 5 11 1 8 0 3 0 6 41 5 5 4 9 20 6 领 域 电子邮件有向 5 9 9 1 28 6 3 0 01 4 44 9 5o 1 6 学生关系无向 5 7 34 7 71 6 61 60 信w w w ( n d e d u )有向 2 6 9 5 0 41 4 9 7 1 3 55 5 51 1 3o 2 9 息 领 引用网络有向 7 8 3 3 3 96 7 1 6 1 9 88 5 7 域 电力网 无向4 9 4 16 5 9 4 2 6 71 9o 0 8 对等网络 无向啪1 2 9 61 4 7 4 2 8 0 0 1 生 代谢网络无向 7 6 53 6 8 69 6 42 5 6o 6 7 物 蛋白质网络无向 2 1 1 52 2 4 02 1 26 8o 0 7 领 域 神经网络有向3 0 7 2 3 5 97 6 83 9 7o 2 8 4 其它特征 上述三种统计特性是复杂网络研究的基础，随着研究的深入，人们逐渐发现 真实网络还具有一些其它重要的统计性质例，例如： 1 7 两华人学硕十学位论文 ( 1 ) 网络弹性 网络的功能依赖其节点的连通性，我们称网络节点的删除对网络连通性的影 响为网络弹性，其分析有两种方式：随机删除和有选择的删除，前者称为网络的 鲁棒性分析，后者称为网络的脆弱性分析。a l b e r t 等人分别对度分布服从指数分 布的随机网络模型和度分布服从幂律分布的b a 网络模型进行了研究，结果显 示：随机删除节点基本上不影响b a 网络的平均路径长度，相反，有选择的删除 节点后，b a 网络的平均路径长度较随机网络的增长快得多。这表明，b a 模型 相对随机网络具有较强的鲁棒性和易受攻击性。出现上述现象的原因在于幂律分 布网络中存在的少数具有很大度数的节点在网络连通中扮演着关键角色，一般也 称它们为h u b 节点。 ( 2 ) 介数 介数分为边介数和节点介数。节点的介数为网络中所有的最短路径中经过该 节点的数量比例；的介数含义类似。介数反映了相应的节点或者边在整个网络中 的作用和影响力，具有很强的现实意义。例如，在社会关系网络或技术网络中， 介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于 在网络中发现和保护关键资源和技术具有重要意义。 ( 3 ) 度和聚类系数之间的