（计算机软件与理论专业论文）复杂网络模型研究与应用.pdf

摘要 近年米的研究发现，许多现实系统都可以用一个复杂网络来描述。这些复杂网络具有一 些相同的特征，如网络平均路径长度较小、聚类系数较人、节点度分度服从幂律分布等，这 些特性是复杂网络为完成某些特定功能而逐渐演化的结果。能够用复杂网络来描述的系统既 有人i ：系统也有自然系统。因此，复杂网络逐渐成为研究复杂系统的一种重要方法，而复杂 网络模型是研究复杂网络的重要工具。 本文详细分析并实现、改进了三个复杂网络模型：小世界网格模型、社会相识网络模型 及无尺度网络模型。在小世界网格模型中，提山并实现了新的根据概率选取长链的方法，该 方法按照与源1 ，点距离的远近把概率累加，简化了长链的选取，取得了预期效果。针对复杂 的社会相识模型，提出并实现了简化的社会模型，其保持了原有模型的大多数性质和行为， 但更易r 实现。实现了无尺度网络模型。最后，针对模拟实验结果对三个模型进行了对比分 析。 关键字：复杂网络平均路径长度聚类系数长链 a b s t r a c t 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 o dw i t | lac o m p l e xn e t 、v o r k t h c 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 ha ss m a l la v e r a g ep a ml e n g 也，b i gc l u s t e r i n gc o e 佑c i e n t ，p o w e r - l a w d e g r e ed i s 廿i b u t i o n ，e t c ，t 1 1 e s ec h a r a c t e r i s t i c sa r ct 1 1 eg r a d u a le v o l v e m e n t s r c s u l t sf o r t h ec o m p l e xn e t w o r k st of i n i s hs o m es p e c i a lm n c t i o n s t h es y s t e m s 血a tc a nb e d e s c r m e dw i mc o m p l e xm m o r k si n c l u d eb o t ha r t i f i c i a ls y s t e m sa r nn a c l l r a ls y s t e m s 、 t h e r e b y ，c o m p l e xn e t 、v o r k sg r a d u a l l yb e c 锄ea i li i n 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 ，甜l dt 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 0 0 1 st os t u d yt h ec o m p l e x n e t w o r k s n l i sp a p e ra n a i y z e di nd e t a i la n dr e a l i z c d 廿l 】汜ec o m p l c xn e 慨o r km o d e l s ：s m a l l w o r l dg r i dm o d e l ，s o c i a la c q u a i n t a n c en e t w o r km o d e l ，s c a l e - 丘e en e t 、v o r km o d e i i nt h e s m a l lw o r l dg r i dm o d e l ，w ep r c s 翩舱da n dr e a l i z e dan e ww a yt os e l e c tl o n gl i n k a c c o r d i n gt ot h ep r o b a b i l i t y ，t h i sm e t l l o da d d su pt h cp r o b a b i l i t yb a s e do nt h ed i s t a n c e b e t w e e n 廿1 es o u r c en o d ea n dt 1 1 ec u r r e n tn o d e ，s i m p l i 6 e dm es e l e c t i o no fm e1 0 n g1 i n k a n da c h i e v e d 也ee x p e c t a n te f f e c t f o rc o f n p l e xs o c i a la c q u a i n t a l l c em o d e l ，w e p r e s e n t e da n dr e a l i z e d as i r n p l cs o c i a lm o d e l ，i tk e e p sm o s tc h 甜a c t e r i s t i c sa 1 1 d b e h a v i o r so fm eo l dm o d c l ，b u ti ti se a s yt or e a l i z e w br e a l i z e ds c a l e f k en e t w o r k m o d e l a tl a s t ，、v eg a v eac o n t r a s t i v ea n a i y s i so ft h et l l r e em o d e l sa c c o r d i n gt ot h e r e s u l t so f t l ee x d e r i m e n t s k e ) 唧o r d s ：c o m p l 强n e t w o r l 【s卵e r a g ep a t hl e n g t hc l u s t e r i n gc o e f n c i e n t l o n gl i n k 创新性声明 y 8 5 9 0 2 3 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切帽关责任。 本人签名日期 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保茁的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：f 蔓：塞 导师签名：! ：家坌兰t 日期竺墅：兰：1 2 日期一? 纱旦 第一章绪论 第一章绪论 1 1 研究背景 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述u n “。一 个典型的网络是由许多节点与连接两个节点的一些边组成的，其中节点用来代表 真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之问具 有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点被看作是相 邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络； 计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电 缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、食物链网络等 等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都 是他们不在意的。在这里，我们把网络不依赖于节点的具体位鼍和边的具体形态 就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那 么，什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来。对这个问 题的研究经历了三个阶段。在最初的一百多年罩，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧拉格子，它看起来 像是格子体恤衫上的花纹；又或者最近邻环网，它会让你想到一群人手牵着手围 着篝火跳圆圈舞。到了十九世纪五十年代末，数学家们想出了一种新的构造网络 的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一 个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一 直被认为是描述真实系统最好的网络。直到最近几年，由于计算机数据处理和计 算能力的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机 网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们 叫做复杂网络，对于他们的研究标志着第三阶段的到来。 1 2 研究现状 复杂网络已经成为当今科学界研究的前沿和热点 3 1 。其研究者来自物理学、生 物学、计算机科学、管理学、社会学以及经济学等各个不同领域。美国科学信息 研究所( i s i ) 的统计结果表明，自1 9 9 8 年以来该领域发表的研究论文数量以指数形 复杂蚵络模型| f i f 究应用 式递增，大量关于复杂网络的文章发表在n a t u r e ，s c i e n c e 等国际一流的刊物上。网 络的结构和性质、网络宏观性质的微观生成机制、网络中的动力学行为是目前本 领域研究人员最为感兴趣的三个方向。网络研究的前景极其广阔，特别是在以下 几个方面有待人们进一步的研究。 首先，对网络结构和性质的研究有待系统化。目前用来刻画真实网络宏观结 构的基本特征量主要有度分布、平均路径长度、聚类系数等。近年来又陆续提出 了些新的网络特征量，如相关系数和介数等，力求更加详细和全面地刻画复杂 系统。然而，这些已有的特征量能否全面地刻画结构非常复杂的真实网络? 或者 说，真实复杂系统是否还具有其它更为重要的宏观性质没有被人们发现? 如果有， 那么如何定义特征量来刻画这些性质? 这都是值得进一步研究的，特别是需要实 验研究的进一步发展。比如说，最近大量的实验结果表明许多真实网络具有分层 结构( h i e r a r c h i c a lo r g a n i z a t i o n ) 。研究指出，处于不同层次的网络结构分别对应于真 实系统中不同的功能单元，如有机化合物分子结构中的官能团。怎样定义特征量 来刻画这种分层结构是当今颇受人们关注的一个问题。 探寻网络各种宏观性质的微观生成机制一直是网络研究中一项有意义且极富 挑战性的工作。虽然现在人们对于网络的无尺度性质、小世界性质的微观生成机 制有了一定的认识，然而对于度关联( d e g r e ec o n 它l a t i o n ) 、团体结构( c o m m u n i t y s t m c t u r e ) 、分层结构等更为复杂的宏观性质的微观生成机制的探索还刚刚开始， 还需要人们进一步的努力。 研究网络中的动力学行为就是考察在具有不同结构的网络中发生的各种动力 学过程的特征。在此方面人们已经开展了很多工作。比如说，对复杂网络中流行 病传播的动力学行为的研究近年来引起了研究者的极大兴趣。研究表明，对于无 尺度网络来说，其传播强度阂值( e p i d e r n i ct 1 1 r e s h o l d ) 趋于零，这就使得在无尺度网 络中采用减小传播强度的方法并不能够阻止传染病爆发。而对于结构化的无尺度 网络而言，传播强度闽值不为零。那么，如何针对不同结构的网络设计行之有效 的免疫策略成为网络研究中一个重要的问题。此外，对不同结构复杂网络鲁棒性 ( r o b u s t n e s s ) 以及脆弱性( l n e r a b i l i t y ) 的研究也是一个具有极其广泛应用价值的课 题。研究指出，由于集散节点( h u b ) 的存在，无尺度网络对于随机性的故障和错误 有较强的鲁棒性，而对于选择性的攻击则体现出其脆弱性的一面。如何系统地研 究大规模真实复杂系统的鲁棒性和脆弱性则被视为当今复杂网络研究中最重要的 问题之一。 1 3 复杂网络应用 网络结构研究固然重要，但其最终目的是通过研究结构来了解和解释基于这些 第一章鳍论 网络之上的系统运作方式，进而预测和控制网络系统的行为。一般将这种建立在 网络上的系统动态性质称为网络上的动力学行为，其涉及面非常之广，如系统的 渗流、同步、相变、网络搜索和网络导航等等。上述研究理论性较强，有一类应 用性很强的网络行为研究已经日益引起人们的兴趣，如计算机病毒在计算机网络 上的蔓延、传染病在人群中的流行、谣言在社会中的扩散等等，实际上它们都是 一种服从某种规律的网络上的传播行为。传统的网络传播模型大都是基于规则网 络的，复杂网络研究的深入使我们重新审视这一问题。下面我们着重介绍这类应 用研究。 网络传播行为的研究最初且仍是主要的目的之一是为了了解疾病的传横机制。 一般爝节点表示痰瘸传染或感染夔个髂，麴鬃秀令令传之鹈霹敷透过蘩零申方式壹 接发生传染与被传染关系，就认为这两个个体之间存在连接，这样就得到了传播 网络的拓扑结构，进而可以建立相关模型来研究这种传播行为。显然，网络传播 模型掰究的关键蔻传槽规则的制定和网络拓扑结构靛选择。 缀燕豹疾痪簧磺模鍪为s 蕊摸鍪_ 茅疆s 承模警，它们郡将辅络拓羚结构麓肇兹霰定 为规则网络或者充分混合均匀网络，区别在于传播规则的不同。s t s 模型中，每个 节点处于两种状态：健康易受感染的和已被感染而具有传染性的；s i r 模型中，节 点还哥戳处于另一耱“免疫”状态，这穆状态下戆苓点甄不会被感染氇不会感染 其它节点，相当予将它从传播嘲络中剔除掉。我们以s i s 模趔为例介绍其研究结果， 首先随机选择网络中一个或若干节点为染病节点，其余为健康节点，狂每一时间 步，染病节点的邻：i 瑗节点以檄攀a 变成染病节点，。称为传染率，两时每个染癖 节点都经菜夺事先浚定鹣痊愈率爹交或键藤节点，主述演纯鬣弱在整个嗣络中被 同时执行。显然，传染率越大，痊愈率越小，疾病就越有可能感染更多的人，一 般定义传染率和痊愈率的比值为传染强度 。研究表明，缀媳s i s 模型存在一个传 染强发瓣篷盖c o ，麴暴i 勋，痰痰传染将一纛持续下去这劐一令稳定熬菠錾，魏 对称染病节点数占憨节点数的浇例为疾病传染豹波及范围；相反，如果 a c ，疾病 持续传染一段时间后最终将全部被治愈。 然露，将疾癍接触网络麓单撼象为规则均匀连接霹络势不德台实际馋涎。m o o r e 等人磷究了，l 、毽癸阚络孛静疾瘸传搐雩亍为，教现疾病在小键界网络中的传播闽值 明显比在规则网络中小，相同的传染强度下，经历相同时间后，疾病谯小世界网 络中的传染范围明照大于其在规则网络中的传染范围，郎：糨对于规则网络，疾 瘸套小整爨网终孛受逶宜簧絷；p 8 s 耗f s 馥孵黯等磅究了在蠢足疫弱终上黔传染霉亍 为，络果令人震惊：无论是规则网络还是小世界网络，总存在正的传染强度闽值， 而无尺度网络中癀瘸传染的闺慎却非常接近于零。对s i r 模型的分析也可以得到类 似的续采。 国予大量馥蜜诞研究表瞬粪蜜毽界网络躐凝有枣整界谯又具有无只发特经，上 复杂网络模型研究2 应用 述结论是相当令人沮丧的。所幸的是，生活中无论是疾病还是计算机病毒的传染 强度都非常小( x ) ； 聚类系数c 劫；当 吁艮大时，节点度分布近似为泊松分布：j d0 一p “ 肛! 。随 机网络模型的提出是网络研究中的重大成果，但它仍不能很好的刻画实际网络的 性质，人们又相继提出了一些新的网络模型。 2 2 1 小世界网络 实证结果表明，大多数的真实网络具有小世界性( 较小的煅短路径) 和聚集性 ( 捆对较大的聚类系数) 【8 】，煲| 表2 1 所示。然愿，翘爨嚼终虽具有聚集性，平均嫩 短潞径帮较天；隧嘏灏列正好辖反，具有小溪界往，餐聚类系数娣稳刍，l 、。 表2 1 ：实际两络的s m a m w o f l d 现象 n o t w o r k s i z e胁， l r 3 喊 c c d w w w s i t el e v e l1 5 3 ，1 2 73 5 2 l3 13 3 50 1 0 7 8o 0 0 0 2 3 i n t e 牲l e t 。d o h l a i nl e v e i 3 0 l5 6 2 0 93 5 2 4 + ll3 7 3 7 66 1 8 6 t 3 0 1 8 一o - 3 o 0 0 l 诚o v i ea e t o r s2 2 5 ，2 2 66 l3 。6 52 。9 拿o 。7 90 0 0 0 2 7 m e d l i n e ，c o a u l h o r s h i p1 ，5 2 0 ，2 5 l 1 8 1 4 64 9 l 00 6 6 1 1 1 0 。 m 舳，c o a u t h o r s h i p 7 0 9 7 53 ，99 58 2o 5 95 4 1 0 5 e 、c o l i ，r e a c t i o ng r a p h 3 1 52 8 32 6 21 9 8o 5 90 0 9 s i l 、v o o dp a r k 岛o dw e b 1 5 44 7 5 3 ，4 03 2 3e 。1 5e 3 w o r k d s ，s y n o n y m s 2 2 3 1 11 3 ，4 84 53 。8 4o 7 0 ，0 0 0 6 p o w e rg r i d4 9 4 12 6 71 8 ，71 2 4o 0 80 0 0 5 c e i e g a l l s 2 8 21 4 2 6 52 + 2 5o 2 80 0 5 f 掭r a n d 为睫钒网终模瓣下的计算，透过趱冼实际网络与撵应随投嘲络( 辗霹的蠢点数矧 逸数) 的缝质，可蓉笈蕊粪实霸络其舂蠢、髓界稻较离聚类系数豹性质。 可见规则网络和随机网络并不能很好服现真实网络的性质，这说明现实世界既 不怒完全确定的也不鼹完全随机的【9 1 。w a t t s 和s t r o g a t z 在1 9 9 8 年提出了一个兼具小 啦界性和高聚集性的网络模型，它是复杂网络研究中的重大突破! 他们通过将规 复杂蚓终模型研究与应用 则网络中的每条边以概率p 随机连接到网络中的一个新节点上，构造出一种介于规 则网络和随机网络之间的网络( 简称w s 网络) ，它同时具有较小的平均路径长度和 较大的聚类系数，而规则网络和随机网络则分别是w s 网络在为o 和1 时的特例。模 型构造过程如图2 1 所示。 2 2 2 无尺度网络 幽2 1 ：w s 小世界网络模型的构造 尽管小世界模型能很好的刻画现实世界的小世界性和高聚集性，但对小世界模 型的理论分析表明其节点的度分布仍为指数分布形式 10 1 。实证结果却表明对于大 多数大规模真实网络用幂率分布 1 1 】来描述它们的度分布更加精确，即：p ( f ， 见表2 2 所示。 表2 2 ：实际网络的s c a l e - f r e e 现象 n e t w o r ks i z e ，。 ，珊 k 。，l 。dl o 。 w w w s i t e3 2 5 7 2 9 4 5 l2 4 52 11 1 t 2 8 3 24 7 7 i m e n l e t r o u t e r1 5 0 0 0 02 6 62 4 2 41 1 1 2 87 4 7 m o v i ea c t o r s 2 1 2 2 5 0 2 8 ，7 8 2 32 34 5 43 6 54 0 1 s p i r e s c o - a u t h o r s5 6 6 2 71 7 3 1 _ 21 242 1 21 9 5 m a t h c o a l n h o r s 7 0 9 7 51 2 02 52 59 58 26 5 3 s e x u a lc o n t a c t s2 8 1 0 3 43 4 e c 0 1 i m e t a b 0 1 i c7 7 87 4 2 22 _ 2 3 23 3 22 8 9 s c e r e v p r o t e i n1 - 8 7 02 3 92 42 4 c i t a t i o n7 8 3 3 3 98 5 73 p h o r l e c a l l5 3 1 0 - 63 1 62 12 1 w b r d s c o - o c c u r r e n c e4 6 0 9 0 27 0 1 32 7 2 7 r 标o u t 、i n 分别表示出度和入度的幂率分布指数，可见很多网络的度分布具有幂率特征。 f 标r e a l 、r a n d 年p o w 分别表示真实网络、随机网络模型和s c a l e - f b e 网络模型中计算的平均路 一 | l r 一黹一一 第一= 章复杂削络概述 静k 腰。 幂率分布相对于指数分布其图形没有峰值，大多数节点仅有少量连接，而少数 节点拥有大量连接，不存在随机网络中的特征尺度，于是b a r a b a s i 等人称这种度分 布具有幂率特征的网络为s c a l e 一仔e e 网络。为解释s c a l e f r e e 网络的形成机制， b a r a b 如i 和a l b e r t 提出了著名的b a 模型，他们认为以f j 仃的网络模型没有考虑真实刚 络的两个重要性质：增长性和择优连接性，前者意味着网络中不断有新的节点加 入进来，后者则意味着新的节点进来后优先选择网络中度数大的节点进行连接。 他们不仅给出了b a 模型的生成算法并进行了模拟分析，而且还利用统计物理中的 平均场方法给出了模型的解析解，结果表明：经过充分长时间的演化后，b a 网络 的度分布不再随时间变化，度分布稳定为指数为3 的幂律分布。 b a 模型的提出是复杂网络研究中的又一重大突破，标志着人们对客观网络世 界认识的深入。之后，许多学者对这一模型进行了改进，如非线性择优连接 1 2 】、 加速增长1 13 1 、重绕边的局域事件 1 4 1 、逐渐老化 1 5 1 、适应性竞争 1 6 等等。需要注 意的是，绝大多数而不是所有的真实网络都是s c a l e 丘e e 网络，如有的真实网络度 分嘶i 为指数分布截断形式等等。 2 2 3 其它网络模型 除了经典的小世界模型、无尺度网络模型之外，学者们也提出了些其它的网 终貘型寒箍述囊实超赛夔弱终结擒。 1 局域世界演化模型 李翔和陈关荣认为择优连接机制不可能在整个网络上都起作用而只会在某个 髑域世冥里被遵守，通过将鼹域世赛的檄念弓l 入8 a 模裂对其终了推广，提出了鼹 谲的局域世赛演化网络模型驻”，其度分稚奔于指数网络和无尺度耐络的度分靠之 间。该模型表明，随着局域世界的扩大，网络演化越不均匀，越接j 髓于b a 模型， 即；局域世赛的规模挟定了网络演化的非均匀性。 2 投重演纯阏终模型 上述研究均将网络看作冤权网，然而现实网络大多为有权网，即网络节点之间 的连接强度是祷区别的。y o o k 等人提出丁一种权重演化模型：假定节点权重正比 予节点蛉度数，也即度数大的节点拥有熨大斡毅数。缕暴表寝，冀发分蠢也雩誓含 鞲撵特征。 3 确定性网络模型 上述所有网络模型都引入了某种程度的随机性，那么是否一定要密随机性爿能 栽瑷出小整羚狡窝无只发穗瞧程? b 翦西犯i 等天援出了一耪其畜罄次结憨豹溺终 模型，它在确定性机制下也能表现出无尺度特性，节点廉分布为p ( 助t “1 。 第三章改进的小世并髑格模型 第三章改进的小世界网格模型 3 1 1 小世界网络概述 3 1引言 所谓小世界现象，或称“六度分离( s i xd e g r e e so fs e p a r a t i o n ) ”，是社会网络 ( s o c i a in e 柳o r k s ) 中的基本问题，即每个人只需要很少的中间人( 平均6 个) 就可以 和全世界的人建立起联系。在这一理论中，每个人可看作是图( g r a p h ) 的节点，并 有大量路径连接着他们，相连接的节点表示互相认识的人。该问题源于社会心理 学家s t a i l l e ym i l g r 锄上世纪6 0 年代作的实验：“追踪美国社交网络中的最短路 径”。他要求每个参与者寄信给。一个住在波士顿附近的“目标人物”，丌始时参与 者被告知目标的一些基本信息名字、地址、职业和其它细节，并且只能把信 发给一个认识的、被认为经由他能最快到达目标人物的人；接下来的收件人遵循 相同的过程，当到达目标时这条链就终止。对于那些完成的链，平均经过的步骤 为6 即所谓的六度分离原则。 这种个体之间存在紧密联系的现象在现实世界中有很多实例【1 8 1 。例如在数学 家的合作论文中，合作者之问存在e r d 6 s 值( e r d 6 sn u m b e r ) ，统计结果表明，任 何数学家，他同e r d 6 s 关联起来的平均值即e r d 6 s 值为3 。1 9 9 8 年，w a t t s 和s t r o 蛆t z 根据m i l g r a j n 的s i x d e 掣e e so f s 印a r a t i o n 假设提出了s m a l lw o r l dn e t w o r k s 理论。 他们统计了电影明星网、电力网、c e l e g a i l s 蠕虫的神经网中节点的平均距离，发 现这些网络中节点之间的平均距离都很小。 小世界现象的存在，对于研究现实世界中疾病传播、通信网络改造、以及计 算机网络中病毒传播都具有深刻的启示意义。 3 1 2 小世界网络特征 l 特征路径长度 在网络中，任选两个节点，连通这两个节点的最少边数，定义为这两节点的 路径长度。网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。 很明显，特征路径长度是网络的全局特征。在朋友( 熟人) 网络中，特征路径长度 就是联系两个人的朋友个数。 2 聚类系数 复杂网络模型研究与应用 假设某个节点有条边，则这条边连接的节点( 个) 之间最多可能存在的边 数为h 一1 ) 2 ，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为 这个节点的聚类系数。所有节点的聚类系数的均值定义为网络的聚类系数。很明 显，聚类系数是网络的局部特征。在朋友( 熟人) 网络中，聚类系数反映了相邻两 个人之间朋友圈子的重合度。 3 1 3 数据分析 规则网络的特征路径长度和聚类系数比较大，( 具有相同节点数和边数的) 随机 网络这两个参数值都比较小，给人的感觉是这两个参数在规则网络向随机网络变 化的过程中具有相同的变化趋势。但实际情况并非如此，见图3 1 。 图3 1 规则网络向随机网络过渡时特征路径长度和聚类系数的变化过程 这里”2 1 0 0 0 ，扣l o 。水平轴采用对数坐标。可以看到，当( 边的) 调整概率很小的时候，特 祉路径长度已经迅速变得很小了，而相对的聚类系数基本未发生变化。这同时也意味着f 在局 部) 几乎无法察觉的就过渡到了小世界。 3 1 - 4 统计结果 w a t t s 和s 拄o g a t z 统计了电影明星网、电力网、c e l e g 姐s 蠕虫的神经网中节点 的特征路径长度和聚合系数，发现它们都和小世界网络模型吻合。这三个实际网 络分别代表三种不同类型的网络：社会网、人造网、生物网。由此可见小世界现 象是普遍存在的。 第三章改进的小世抖嘲格模型 3 1 5 理论应用 从小世界网络模型中可以看到i l ”，只要改变很少的几个连接，就可以剧烈的 改变网络的性能。在疾病传播中，这不是一件好事。但这样的性质也可以应用到 好的方面，尤其是对已经存在的网络( 没有必要从零开始) 进行调整，例如蜂窝电话 网，改动很少几条线路“氐成本、低工作量) 的连接，就可以显著提高性能。也可以 应用到i n t e m e t 的主干路由器上，以改变流量和传输速度。同样的思路也可以应用 到电子邮件的快速传递、特定w e b 站点的定位等等。小世界网络模型的广泛应用需 要人们的进一步工作和思考。 虽然小世界网络模型同实际的网络有很好的近似结果，但对于人造网络的近 似程度不是特别令人信服。另外小世界网络模型中，每个节点的边数是基本相同 的，这就限制了小世界网络模型的应用范围。两个最重要的网络i n t e m e t 和w w w 网络用小世界网络模型来描述存在一些问题，针对这两个实际网络，s c a l e f r e e 网络 ( 无尺度网络) 模型有更好的近似结果。 3 2模型的提出 l 规则网络与随机网络 我稍瑟一维链，二维援方晶格等称为溉刚网络 2 诺。规刚两络怒指对称往晶捂， 任何一个格点的邻居数目都相同。随机网络是另一个极端，由，个丁员点构成的图中， 可以存在c 2 。鬣边，我们从中随机连接埘条边所构成的网络就h q 随机网络。还有一 秘生残琏掇鲻络懿方法是，绘一争疆率筘，对予乎”中经褥一令霹栽豹连接，我粥 都尝试一遍以概率芦的连接。 规则网络与随机网络的熊型几何性艨包括：度分布，平均集聚程度与平均最 短距离。擐剿鼷络赝有顶点鄂相同，嚣姥其度蓬相同，度分舞为鬻态分鑫，其平 均集聚程度懋只需要在个点诗算，萁缀短距离也可以只觚某一个顶点开始计辫 从它到所有其他顶点之间的距离之和，然后计算其平均值。对于随机网络g ( ，p ) ( 越 中 带点数，妒为节点连接概率) ，包含了从空图到完全阁的所有可能情况，因此髓 筏交弱凡援瞧缓霭要霹每一耱胃髓蚕 菝警麓，铡蘩我爨诗算每一秘霹麓强熬豢筑 躐离，然后按照各自如现的凡率做平均。研究结果表明随机网络顶点的度值符合 平均值为洲的泊松分布，疑集聚程度约椁于p ，最短距离如厶( _ ) 。 对比援剃网络与随规鲻终，我们发瑷，平均集聚程度与平均簸短距离，这灏 个静态几弼爨能够很好地葳浃栽刚网络与随视两络豹性质及萁差辩。规赠阚络的 特征是平均集聚程度高而平均最短距离长，随机网络的特征是平均集聚程度低而 复杂网络模型研究，成用 平均最短距离小。规则网络的平均最短距离d l ，而其集聚程度依赖于邻居数目。 而在随机网络中，平均集聚程度非常的小。然而诈是由于其集聚程度非常地小， 所以其平均最短距离小。对于规则网络，也正是由于其集聚程度高，重复率很大， 所以平均最短距离大。如此看来好像这是一对相互矛盾的几何量。那么，是否存 在一个同时具有高集聚程度小最短路径的网络呢? 2 从规则网络过渡到小世界网络 大量实验以及对现实世界的模型的研究表明：小世界网络具有以下特征：同 时具有小的平均路径长度和大的聚类系数。 w a t t 和s t r 0 2 a t z 发现，只需要在规则网络上稍作随机改动就可以同时具备以上 两个性质，从而生成小世界网络。改动的方法是，对于规则网络的每一个顶点的 所有边，以概率p 断开一个端点，并重新连接，连接的新的端点从网络中的其他顶 点罩随机选择，如果所选的顶点已经与此顶点相连，则再随机选择别的顶点来重 连。当p = o 时就是规则网络，p = 1 则为随机网络，对于o 印 1 的情况，存在一个很大 的p 的区域，同时拥有较大的集聚程度和较小的最小距离，即形成小世界网络。 3 支持有效搜索的小世界网格模型 一个可遍历的网络模型有一些基本特征1 2 1 1 。在所有( 或大多数) 节点对之间应该 有短路径。并且其中的节点只了解网络的部分结构：这样，已知部分的信息可以 用来构造使用未知部分信息的路径。很明显这就是m i l g r a m 的实验中发生的事：参 与者使用可用的信息来判断在他所认识的人中通过谁会形成遍历整个网络的最短 路径。 那么w a t t s 和s t m 朗t z 提出的小世界网络模型是不是可遍历的呢? 一个源于他 们提出的模型的简单的变种可以描述如下：在一个p 维网格中，节点只与距离它们 最近的邻居连接，然后从每个节点v 引出k 个长链：链的终点是随机均匀选取的。 根据k l e m b e 增1 9 9 9 年的论文t h es r n a l l - w o r l dp h e n o m e n o n ：a na l g o r i m m i c p e r s p e c t i v e 中的第一个结论，在上述模型下不存在多对数搜索时间的分布式算 法虽然在节点对之间有多对数的路径长度。( “短”路径的标准是：路径的长 度限制在基于f 0 州的多项式范围内，其中为节点个数。这样的函数我们称它多对 数函数) 然而，如果我们稍微改变这个模型，它就能支持有效的搜索。改动为：当 我们为节点v 建立长链( v ，w ) 时，不是均匀随机地选取w ，我们选取w 的概率正比于， 其中踞v 与w 之间的曼哈顿距离( 1 一门2 | 1 定义为两节点”l 和”l 间的曼哈顿距离) ，如 此一束，长链就与网格的几何结构有关。下一节将根据k l e i n b e r g 所提出的模型进 行模拟实验。 第三章改进的小世界阿格模型 3 3 1 算法描述 3 3模拟实验 从出发点踮递一条消息到目的点7 1 ，除了边缘节点，模型中每个节点有4 个邻 居( 边缘上的节点有2 或3 个邻居) 及根据概率选取的远程联系长链。消息传递者 的选耿采用贪婪路由算法：假设当前节点为“，分别计算“的邻居及长链与目的节 点7 的距离，选取距离最小的节点为下一个消息传递者。每个节点的邻居都是初始 化好的，但是节点的长链例外，只有当消息传递到了这个节点，爿为此节点产生 氏链，因为从仿真的角度看，这样就足够了，没有必要开始就为每个节点产生长 链。每个节点掌握的信息有：所有节点的邻居；目标t 的位置。如果它还知道所有 消息传递者的位置及这些节点的长链，那么算法能取得下界结果，否则取得上器 结果。本实验中节点没有第三个条件。 本实验是静态实验，我们考虑理想的情形即网络中不存在任何节点的加入或 者离j r 。当( v 从6 4 到4 0 9 6 变化) 个节点加入网络后，从中随机选取两个节点，其 中一个向另一个发送查询请求。路径跳数在每一次查询中被记录，当5 0 0 次查询完 成后，计算平均路径长度。 对于一节点选择节点v 作为它的长链的概率芦为： p 2 嵌“，v ) 乞硪“，v ) 。 式( 3 1 ) u # v 其中硪“，v ) 是节点“与v 之间的曼哈顿距离。 算法的形式化描述为： p i o c e d u r em a i n i n p u t 门( n 啪b e ro f m en o d e si nu l en e t w o r k ) ，( c x p o n e n tf a c t o