（系统分析与集成专业论文）复杂网络中节点的度的研究.pdf

摘要 摘要 囊杂网络是一种新的系统科学理论，它将宏观结构复杂的蒜统视为网络，从 整傣缝梅的撬焦蠡麓，研究箕藉矜特性、成慰、演纯及盛鬻。官数形成源予瓣 两个著名模型的探讨；w a t t s 藕s 锏g a t z 的小檄綦模型显示了警掳路径长魔旗画 节点均距) 和聚集系数( 刻画局部平均耦合程度) 遮两个指标的重要性，a l b e r t 和 b a r a b 瓤i 抟无标度模型则表明了节点的度分布的蓬要性。这纛个概念是当翦复杂 翳络磷巍鹩孛心润燧，它翻及受冀影璃麓凳舞一些槛矮，搦添了曩杂表象背矮不 复杂的、规律性的一面。找出这些飙律，正是鬟杂朗络研究酌黼的所在。 本文主要关注两个问题：如何测定网络的无标度性并估计幂指数，如何利用 有囱赋毂图的拓挣结梅计算其带点粳羹。关予蓠誊，我们在繁2 章中设计了髓计 幂揍羧麴赢精度方法豢太等缀法，征甓了窀是判定整数黧大榉率幂德照撬量 的充篓条件。并以平均相对误差为耋要评价指标，在相同实骢条件下比较丁多种 方法，诞实其优越性。关于后者，我们在第3 牵中讨论利用度德息计算图的节点 权重p a g c r a n k 算法，它是蓄个也是现存寿命壤长麓、影响豢大酶藏功恕缝摘 信感运澜于大瓣搂工鼗计算豹窭践。我们用m a x k o v 链建立了稠始模型，辨将其 改进为拥有唯一平耩分布的新模型；讨论了p a g e r a n k 迭代的收敛性及收敛速度； 分拼tp a g c r a n k 算法的稳定性，得到对三个融翔条件扰动盛的谡差上界。 关键词：复杂网络，度，平均路径长度，聚巢系数，无标度，幂律，最走等级 法，平均相对误差，p a g e r a n k ，m a r k o v 链，平稳分布 a b s t r a c t a b s t r a c t c o m p l e xn e t w o r ki san e wk i n do fs y s t e m ss c i e n c e i tr e g a r d ss y s t e m sw i t hc o r n - p l e xm a c r o s t r u c t u r ea san e t w o r k , a n a l y z e st h e ms t r u c t u r a lc h a r a c t e r s ，s u c ha st o p o l o g i c a l i n d i c e s ，c a u s eo ff o r m a t i o n ，e v o l u t i o na n da p p l i c a t i o n s p o p u l a r i t yo fc o m p l e xn e t w o r k t h a n k st oe x c e l l e n tr e s e a r c h e so nt w om o d e l s ：o n ei st h es m a l l - w o r l dn e t w o r km o d e f i n t r o d u c e db yw a t t sa n ds t r o g a z ，i tr e v e a l st h ei m p o r t a n c eo fa v e r a g ep a t hl e n g t ha n d c l u s t e r i n gc o e f f i c i e n lt h eo t h e ro n e i st h es c a l e - f r e en e t w o r km o d e li n t r o d u c e db ya l b e r t a n db a r a b 缸i ，i tr e v e a l st h er e l a t i o n s h i pb e t w e e nc o m p l e xn e t w o r k sa n dd e g r e ed i s t r i b u t i o n t h e s et h r e es p e c t a c u l a rc o n c e p t sp l a yak e yr o l ei nr e c e n ts t u d ya n dd e v e l o p m e n t o fc o m p l e xn e t w o r kt h e o r y , t h e ya n ds o m eo t h e rp r o p e r t i e si n f l u e n c e db yt h e mr e v e a lt h e e x p l i c i to r d e r e df a c t sb e h i n dc o m p l e xp h e n o m e n a r e s e a r c h e so fc o m p l e xn e t w o r ka r e a l w a y sa i m t od i s c o v e rt h e s ef a c t s t h i sp a p e rp r i m a r i l yf o c u so nt w op r o b l e m s ：h o wt ov a l i d a t et h es c a l e - f r e ep h e - n o m e n o na n de s t i m a t et h ee x p o n e n t ? h o wt oc o m p u t et h ew e i g h to fn o d e so fd i r e c t e d w e i g h t e dg r a p h s ? f o r t h ef i r s to n e ，w ed e s i g nan e wa c c u r a t em e t h o dn a m e dm a x - r a n k i n g t om e a s u r ep o w e r - l a w as u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no fp o w e r - l a we s t i m a t i o no n o c c a s i o no fh u g ei n t e g r a ls a m p l e si sp r o v e d t h e nw ec o m p a r et h ea v e r a g e - r e l a t i v e - e r r o r b yd i f f e r e n tm e t h o d s ，a n df o u n dt h a tb yt h ea r e o fm a x r a n k i n gi sm i n i m u m f o rt h e o t h e ro n e ，w cd i s c u s st h ea l g o r i t h mo fp a g e r a n k ，w h i c hi st h ef i r s ta n dt h em o s ti n f l u e n t i a li n s t a n c eu t i l i z e st h ei n f o r m a t i o no fs t r u c t u r ei n t ol a r g es c a l et e c h n i c a lc o m p u t a t i o n w ec o n s i d e ri ta sm a r k o vc h a i n ，t h e na m e l i o r a t eo r i g i n a lm o d e lt oan e wo n ew i t hu n i q u e s t a b l ed i s t r i b u t i o n ；w ed i s c u s st h ec o m p u t a b i l i t yo fi ta n dc o n v e r g e n c es p e e do fi t si t e r - a t i o n ；w ea l s or e s e a r c ht h es t a b i l i t yo fi t si t e r a t i o n ，a n dg a i n e dt h r e ee r r o ru p p e rb o u n d s u n d e rd i f f e r e n tp e r t u r b a t i o n so fs e t t i n g s k e yw o r d s ：c o m p l e xn e t w o r k ，d e g r e e ，a v e r a g ep a t hl 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 ， s c a l e f r e e ，p o w e r - l a w ，m a x r a n k i n g ，a v e r a g er e l a t i v ee r r o r , p a g e r a n k ，m a r k o v c h a i n ，s t a b l ed i s t r i b u t i o n 一一 符磅对照表及排版约定 主要符号对照表： 纛p l g e 豁网络 妒雒 穗晟掣 r ( 髫) e r r g = ke m ( a 影( 讳) l l 胁 炎艏 字体排版约定： 符号对熙裹及排版约定 早麴路径羲凌( a v e r a g e 觏熄g t h ) 聚集系数( c l u s t e r i n gc o e 躏c i e n t ) 无标度网络( s c a l e f r e e ) 随视事件黛蹒现的概率 嚣标度鹅终麴凄播数，掣一巍+ l g a m m a 函数，r ( x ) = 铲护q e q d t 平均相对误麓( a v e r a g er e l a t i v ee r r o r ) 点集舞y 选集隽e 的摇努阁g 荚予图g 韵瓣阵，瘸粗斜体大写字母袭暴楚阵 对向量口的第几次迭代，用糨斜体小写字母表示向量 向量或矩阵的嚣范数，雄墩熏，2 ，o o 之一 方阵蠢窿懿特锺 蒸炎 l 。概念。概念黻熏体汉字打印搏麴戳索引。 2 。燮叉饮用。章节的引用名称凼需体汉字及奠数字编号组成。定理、引瑗的引 用名称由楷体汉字及其数字编号组成。定义、假设、图、袭的引用名称由傍 采傣汲字及箕数字编号组残。藁文添文甸子的孳| 阕戳i t a l i c 字薅打印。 3 ，定义及定理。蹩义、假设、算法过程的内容以仿宋体打鞠。定理、弓i 理，推 论的内容以楷体打印。它们的标题都以黑体打印。 4 。注释。注释的掭号按页为攀攮，以汉字注及数字标号组成，链于上标饿置。 5 + 瀚袭。图表赫姆趣和内容孛憋汉予戳髂寒饿打窝。 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护黑识产权的规定，即：砾究生在饺攻 读学位蒲闻论文工作的知识产权单位属于西北工业大学。学校有权保 留并向国家有关部门或机构送交论文的复印件，弼电子版。本人允许论 文被奁阕和曾阅。学校可以将本学旺论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。同时本人保证，毕业后结合学位论文研究谋题再撰写的 文章一律注暖作者单位为疆北工业大学。 保密论文待解密后适用本声明。 学论文作者签名：至堡垒指导教师签名：童：b 兰二 岬年弓月。多日 垆j 7 年川日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交 的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽 我所知，除文中已经注明引用的内容和致谢的地方外，本论文不包含 任何其他个人或集体己经公开发表或撰写过的研究成果，不包含本人 或他人已串请学位或其它用途使用过的成果。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切榴关的法律责任。 学位论文作者签名：打苏 妇7 年月彬慝 第一章绪论 第一章绪论 复杂网络是当前的热点研究谍愿，正以锐不可挡之势渗透到自然科学、社会 科学鬻太文科学磷巍之串。著名理论物理学豢s 阚热睫h a k i n g 赣说，誓t h i r kt h e n e x tc e n t u r yw i l lb et h ec e n t u r yo f c o m p l e x i t y 暇。i 9 8 4 年，耄兰德酗b c l 奖获得者 组建了燕国圣塔菲研究所，邀请闼际上不同领域的科学家联合研究复杂性问题。 我羼魁2 0 0 0 年开始，在国家自然科学基金委员套囊持下设立了“复杂性科学”专顼 羞金，舞展了物蘧、经济帮生物等鞭域的复杂性鼷通翁礴究，广泛深入的搽素王 作已经提到我国基勰研究的日程上了。 1 1 孽l 言 卷多个交互影晌黪个体蕴威的蒸统可竣横麓弼结，诸懿w e b 【1 2 、i n t e r a c t f 2 6 、电力网( 4 8 1 、电话呼叫网f 1 3 ，e m a i l 传递阕【2 4 、文献弓i 用网 4 4 】、蘼词 协同出现的关系网 2 3 、蛋白质交飘作用网【2 9 ，等等。我们或者不自觉地属于 某种天然褥络，藏誊鬻意截遥菜稀入工瓣络。避囊愚说“大是社会关系的惑耩”， 社套关系就包括形形穗色豹网络。遮些网络的熬阍特点是：撬摸相当大，髂构菲 常不规则，总是动卷囊化着的。初被发现时，它们总给人以“复杂”的感觉，难以 用静态的摇拓手 藤论、定性的( 如社会学分析、局部的方法避行研究。 臻在，受益予诗蒸橇性髓翡章越遴步，a 黼幂徨糍够穗确统计复蓉系缓麓拖 扑指桥，而且能探讨深藏其后的动力学成因。爨此出现了一门新的系统科学 复杂网络，它是将复杂( 宏观结构不规则的) 系统视为网络( 图) ，研究其拓扑特 性、藏嚣、演纯及威簏斡褥学理谂。入髑发现，复杂系统并嚣难戳捉攘，宅稍有 着莱望慕性： 1 系统的规模很犬，但任意两个节点间的警均距离却很小。著名案例是由 m i l g r a m 注捷汰的嫡渡分隅”理论，缝进3 0 0 多名恚愿卷绘雾缝酶一位不榴 谖的黢票经鳃a 一封蓿，且嚣糍通过炎际美蓑两黄递壕棒，结果商鳓爹封 信成功送达，因此得出“两个陌生人间所闻隔的人平均为六个” 3 3 1 。更雾研 究袭明，很多髑络也有这种性质，w w w 节点均距是1 6 【2 1 ，i n t e r a c t 路由 器阈麴是1 0 4 5 1 ，冕表l + l 麝蒸； 2 。系统翁总锌结构捆当松散，缀属韶结构却有一定程度的耦畚。也就是说，虽 然系统的整体涟通性很弱，但备点的领域的平均连通性要熙强一些。例如， 正s t a n l e ym i l g r a m ( 1 9 3 3 * 1 9 8 4 ) ，哈佛突攀心理学教授，憾子1 9 6 7 年进嚣黉度分睡”实骚。 黎一章绪论 猩麟友关系麟中，认识同一人的鼹个人闻被此是朋友的可能性更太。w w w 翡平均藕合魔海0 ，l 【1 5 1 ，i n t e m e t 域闯懿怒0 2 4 【4 5 i ，觅褒l 。1 所示，箕孛 耦合度的最大值为l ； 3 。闷络的节点的度服从幂律分布。一定条件下，复杂系统将会出现“两极分 纯”的情况。此时，8 0 熬繁赢的度只有i ，纛2 0 趋繁杰的度和占魔蒽帮 酶8 0 ，这种“二夕律鬣象被发现广泛懿襻在于经济学、雏物学、计雾辘两 络、图书馆攀中。这种现象令复杂系统的结构呈现出独特的稳定性，破坏 8 0 的普通节点并不会使网络瘫痪。但破螺5 的关键节点却足以毙命，即 掰谗“阿嘻琉紫意愚”正 4 7 1 。 以上特点从纷繁的表象中揭示了优美的内瀚，激发了人黼】的研究兴趣。这些 研究发现，现实中的辫数网络是笺杂的，它们商其动力学的成因，它们介于从规 则网格剽完全随辊瀚之阕的菜一瀵毽除段，它懿霹戳用节赢均鼷、平均耦含魔、 幂豫分帮筹工具避褥分析寨分类。这些斡理论幂彀隽我翥l 开辟7 一种薪酶系统稀 学观，而且对一些实际闻题的解决有启发意义( 兕第1 1 3 节) 。 1 。 指标 姘究复杂嘲络，需要借助予一些统计指标及数学的、物避的手段。举节中， 我们介缨这些概念。融有多种指标被提出用来剡厕复杂系统，其中有三种狂最近 的研究中处于核心德曩平均路径长度( 定义1 1 、聚集系数( 定义1 ，2 ) 、麈的 分毒定义l 。3 ，窀翻分粼描述了繁点平均距离、擎麴耦台翟麓瀚节点闻麓楚健差 异。袭1 。l 是关于这三个指标的若干赛例。 网络规模平均路径长聚集系数厦指数a i n t e r n e t ，蜜活域缀 4 5 】 3 2 7 1 l3 5 60 。群l 。l i n t e m e t ，鼙奎器襞 4 5 】 篮嚣鹳3骛。5 l0 。潞董。董 w w w 小范萄【1 5 】 1 5 3 1 2 73 ，重o 1l 魄端l ，l ，a 。一王。4 5 w w 砒太范围 2 1 】 2 1 0 8 1 6 蔫1 1 ，q 。= 1 。7 2 e m a i l 2 4 1 5 6 9 6 94 9 5o 。0 3o ，8 l 影爨合作阑 4 8 ，1 7 】 2 2 5 2 2 6 3 ，6 50 。7 9l 。3 数学论文署名阏1 3 7 3 了秘彳墓9 + 5 00 5 雾重。5 表1 1 若干复杂网络窝例其中曦裘黍入度指数，鳓表示出度措数。数据见 4 7 。1 4 1 我们恕复杂隧络抽象先圈g 一k 霹，其中驴表示节点集，霪表示边集。有 爵怒8 警捧无禽蓬，麴分辑i n t e r n e t 对，毒黠姿熊纛商图，妊分析w e b 黠。鬻l ，l 是i n t e r n e t 在主干i s p 上的拓扑图。 正1 a c h d l e s h e l l ，典j 士 赣希腊神话，特洛伊之战的懿雄阿喀琉斯浑身刀枪幂入，只有脚蹂是死 穴，壤聪娆困被玻人的蒜射串瓣藤藏。该谚语比嗡致鑫秘庭。 一2 一 圈l 。1l n 地椰e t 雀幂丽盎治域( 旺芊同颜色标识) 层次上曲拓扑匿，豢因源子贝尔骏塞的 t h ei n t e m e tm a p p 魄p r o j e c t 硬霪 2 2 1 。 定义| 。l ( 平均路径长度，a v e r a g ep a t hl e n g t h ) 记节点i 和j 蟪距离为它们的通 路长度，即南箩觚瓤，j ) j ，则平均路径长度 t 枷+ j 艘旌南苫铲甄鸯 即a p l 是随机变量d 麴期望。 定义1 2 聚囊系数，c l u s t e r i n gc o e f f i c i e n t ) 藩赢季翥麓豢遗，竣最黄送瓶夺糍 邻点湖建接的边数，记c ；f 箩赢最，表示点邻蜮的连通程度，则聚集暴数 磐南；a 表示节点邻域的早均连通程度其中，可以等价地定义g 堂窖是敲强毳鬻徽。 有趣静是，大多数囊窦复杂网络酶a p l 帮是够奎，僵只鸯其规模麴瓣数缀 第一章绪论 大，即使那些边数远少于正则图( 见第1 1 2 节) 的网络也是如此。同时，它们的 c o 又远大于随机图( 见第1 1 2 节) 下的情况( 口。以一o ( 斋) ) ，显示出局部聚集的 趋势。因此，这样介于正则网格与随机图之间的现象，被w a t t s 和s t r o g a t z 形象地 称为“小世界效应” 4 8 】。真实的复杂网络具有小世界性。 定义1 3 ( 无标度网络，s c a l e - f r e e n e t w o r k )若节点的度满足幂律，即表示度的 随机变量x 服从指数为口的分布： p x z ) = z o ， z 1 ，a 0 那么该网络具有“无标度性”，称它为“无标度网络”其离散形式为 p x = k ) = c 1 其中，k = 1 ，2 ，- ，7 = a + 1 ，g 些赤，( ( 7 ) 是r i e m a n n z e t a 函数 与常见的钟型分布( 如正态分布，p o i s s o n 分布) 不同，幂律分布有一条长长的 尾巴，是一种重尾分布，如图1 2 所示。服从钟型分布的随机量比较平均，值的 相差不很大，而服从重尾分布的随机量有明显的两极分化倾向，如第2 页所述。 换句话说，钟型分布非常“民主”，重尾分布极端“专制”，这使得无标度网络有许 多出人意料的性质，见第1 i 3 节。判定幂律的最直观的方法是在双对数坐标中 ( 1 0 9 l o g ) 作分布曲线，若近似直线则很可能是幂律分布，然后用拟合法求出度指 数。第2 章中将详细讨论度指数q 的精确估计。 1 1 2 模型 图1 2钟型分布和重尾分布的对比 本节介绍几种颇具影响的网络模型。人们曾寄望于正则网络和随机图能够解 释小世界性和无标度性的成因，而当发现它们离真实网络颇有距离后，分别提出 了著名的小世界模型【4 8 】和无标度网络 1 7 】。 一d 一 第一章绪论 一) 正则瞬络 豢篱单豹芷刘阏络是完全潮。其平均路径长度最小，a p l 一董，聚集累数最 大，秽c = l ，因此舆有小世界性。它是稠密的蔗i ，而真实的复杂网络都是稀疏 的，湖此完全图不够逼真。 曼一个被广泛掰窕的歪榭麟络是阑格。嚣黔爨格靛蠢点蓐薅旁翁嚣个赢耱 连，k 是偶数。茹翔，箕c c i 艄，而当| v i o o 对a p l 籍鬻一0 0 a 富不 具备小世界性，因此也不是好的模型。 每煎两者梗魄，星型网络其赣小世界性。窀寤一个孛心繁赢，其余点与中心 煮耨连，它是稀疏黪，尝阿| 哪0 0 时，冀a 矽嚣砷2 ，嚣脚1 。窑是蔓轰瑷想的 模型，虽然现实中很少有网络是严格星型的。 ( 二) 随机图 蘸粼网络的鼹立面裁是隧撬瀚，隧橇匿蘧论巍蹦渤嚣2 霸受魄i 予1 9 5 9 年 剖建的瑶5 】，也被称为至聚模型。谈模型飙若干个孤立的点嚣始，以固定昀概率p 在这魑点间增加边，从而得到一个随机图。研究的主要耳标，就是探索图的某些 拓扑憔震隧p 的演化褥出现或改变的情形。 凝枫圈孛菜煮的度隽纛麴概率是溉= 礤融矿重一p ) l v 融一，剿乎均度为 奄) 一p ( w f 1 ) 。隧机图的度分布是p o i s s o n 分布，设x 是表示度值的随机 变量，则p x 一磨) 一蔷e ，其中a = 脚赢观上有i y i 一( 七胛厶，因此 a 隗一皆。由于莱点数部域态任意两点籀连滟概辜餐是p ，睡毙韶一移陆， 表蟠隧瓿圈没有精豁的耦台性。 ( 三) 小世界模型 耀格有局部耦畚健面没有合理的平均路径长度，随机豳霄辕小的乎均鼹径长 度帮不藕合，焉真寨瓣终既煮较水祷a p l 又鬻念霪的9 0 ，翔魏曛格搂羹耱e r 模型都不太适合。为了描述从网格到随机图的演化，w a t t s 和s t r o g a t z 于1 9 9 8 年 提出了小世界模型，也称w s 模型阿8 1 。以下悬生成w s 模型的算法： l 戳髫酪恿格耱始； ( 匐以概率p 对薄条过进行髓枫囊连，但不褥幽理鸯环和蘸逸。p = 0 对是有序 的网格，p 一1 时是随机图，小世界网络夼予二者问图i 。3 是示意图 w s 模型懿乎均路径长震建妒玉蝴和聚集累羧妇帮瓣键为边重逢凝牵p 的函数。w a t t s 等发现，a p 妇) 和c c ( p ) 是互糊消长的：当筘稍微离开。端，c c 41 设图g = ( k e ) ，潜满足i e i = 0 ( 1 v i ) 贝4g 是稀硫的，若i e i = 0 ( 1 v 一贝! ig 是稠密的。 菇2 p a u le r c l 6 s ( 1 9 1 3 - i 9 9 6 ) ，匈牙剩裔蓑函数攀家，2 0 懿纪最伟大的数学骞之一。 一_ 5 一 第一章绪论 毽1 3子匿醇是一个4 除然友关黎网格，其中每个人只与身边的4 个人交往。予隰( 协 是黠赫接魏率p 避嚣遗譬连君辨缛蟋小避赛逶，嫠褥纛鎏久毒送躐离瞬鼹灰。警裂瓣 是随簧p 增大囊1 新褥麴鲢枫图，蠡然人鸳煮4 夺熬震，瞧都是逸耀藩魏。觅交麸1 4 8 。 几乎不变，a p l 却下降得很快；当p 越发靠近1 端，a p l 几乎幂变，c c 却下降 得缀抉。絮匿1 4 群嚣。 匿1 4盎串对数蹩标o o g - n o r m a l ) 警，a p l ( p ) 和露0 懿瀵装关系。楚文献娜l ， 和e r 模型一样，w s 模型节点的度相差不太，比较民主”，因此被称为同质 性的。n e w m a n 和w a t t s 提出的i t w 模型是w s 的变种，它不熏连边丽是以概率p 添懿逸，当p = 1 盼褥戮完全匿。著p 充分小| y | 竞努大，n w 与w s 等蛰。 鲫) 冤标度模型 e r 模型和w s 模型的度分布都是同质性的，它们在均值她达到峰项，沿两边 数攒鼗缓速度递降，阑越也被稼兔“攘数銎丽络”。然丽，我翻在篓2 夏提劐，真 窭鞠络大多是两檄分纯”蜉无赫鹱麓络。 为了解释这一现藩，b a r a b 矗s i 和a l b e r t 于1 9 9 9 年提出了秃标度模型，即b a 模型f 1 7 ，1 6 。该摸趔基于两点假设： 一 ( | ) 动态增长。网络最初只有蛳个节点，每黼醋阉譬增加一十薪节点，劳毒已 存在的m 1 7 , 0 个点连上边； 一6 一 第一章绪论 犯) 羁太效应五。度数越高的繁点越察舅获得新莲接，已存在嬷赢暮与裁如带点 阉毒遂鸶橇搴瑰一麓。甄。 用平均场理论黛2 解释b a 网络无标度性的成因。考虑点削在第t 步的麋为 8 ，其连续增长率为m i k ，即平均场。西此 掣兰砜= m 筹嬲警 在勃贻条粹粼勰下解褥k , c t ) 一瓣毒- 如的整度函数魏糯= 泰爨 | 节点静麴鏖势布舞： p ( 霹) 警 辫1 一赢 因诧褥，p 鳓= 篓瓷喾烈i 。( k - 3 。 模拟证实，b a 模型生成的阚络有无标度性。例如，当椭一5 ，t 一2 1 0 5 时，魔掇数理= 1 9 。与瓣模相同强平均度相两的隧机图相比，b a 模型不但平均 路程舔度鞍小覆盛蒙纂系数也比较大，因此b a 簇型县有小髓雾健。鼙l 。2 帮将薄 b a 模型的小世界性瓣接一个理论上的证明。 b a r a b 螽s i 等曾将两个条件分别取消。取消第一个后，度分布呈指数速度衰 减；取消第二个蓐，睫藿时闻增加，凄分布逐灏演变巍芷态分簿。因照，燎长乓 马太教照是导致无标凄牲的盛不磷少韵两个因囊。 1 1 。3 瘸示 本第舟绥复杂麟终蘧诗冀枫辩攀、控铡谂、生爨学等提供鹣煮益寝示，摄然 这些研究进展尚不熊深入影响其串锤何一门学科，但毕竟为学辩闻韵交叉研究开 辟了一个新的视野。 ( 绩构稳健憔黪努析 我锏在第2 贾措擞，无标麓随络可能会蹬驽酽两极分霉艺”的媾形。这是巍予当 0 7 0 酵，斓终。死乎基4 没耆主连逮瑰纛2 ；耋髻翱时，矮垫丸乎”只 有唯一的主连通婕； ( 2 ) 辫7 0( 2 + 1 ) 哥戳谶，幂襻、p a r c t o 分意、葱蟮簿冤鸢雾是同一个“太”麴凡令名字，两这个“入”就 是公式( 2 。1 ) 。 2 2 。2 最大等级法的步骤 鼹大等凝法氆蹩公式蒋1 ) 麴舅一个“名字”，趣它提供了巍大样本驹绣台下， 验证熬数型幂律随机数的可靠依据，以及比传统方法更高的估计精度。最炎等级 法有如下步骤： l 捺瘩。蓑浏羹蕊黪降痔排舞，褥到凝痒缝甘量墨焉。命题2 i 表 鞠，这些顺序统计量在帆较大对近似满憩嚣硅一凳。l i 薄就是用该式定义 幂律的，但他们没有给出这样徽的理由； 2 最夫等级化。对予数懂穗等熊样本置一甄串l = 一五嬲，记录箕最大赫 凌痔惫= i + i ，鬻酵去掉重囊样本，褥到严撂下降昀蓐稠甄酶 k 及相应的最大等级序列惫1 k ，其中m n ； ( 3 ) 骏证幂律在l o o g 坐标中，作点( ，概) ，i = 王，2 ，m 。例如，我们对 下载翻酶最誉熬褰酶9 5 1 6 个英文单谲翡紫数燕瞬统计，劳蔫最大等缎法髂 潮，如图2 。2 瀚零； ( 4 ) 估计幂指数。0 n 0 ，则 p x 啪露 一p x 茹一毒一雾茹一壹一茹 也就是说x 哺服从均匀分布u ( o ，1 ) 。记z k = 耳穗。那么磊磊，随机变 量承鹣期望为： e ( 氨) 黑z 王西= 赫扩( 重一霈) n “，( 嚣) 妇 魏l f ( 患书1 ) r ( 张一是书羔 k 一羔! 嚣一秘lr ( n 2 露! 鸯i 稚一鲻! ( k 一1 ) ! ( 托一七) !( 扎十1 ) ! 奄 ：= 一 嚣+ 1 其中，班露) = 铲毒扣1 霹一d t 。当辩辕大时，盈躺方差d ( 氨) 一番耥将很 小a 对垤0 ，依c h e b y s c v 不等式宵p l 磊一簋( 磊) l _ ，廖( 氨) 扣2 ，因此， 可以鼷磊代替e ( 磊，得到鼹嚣穗潜k 。 囵 当测量值是整数鹣l 聪，f l 撇( 2 。1 ) 知x 取1 ，巍- 等鞍小数德韵 概率极太，换句话说崧们的频数最大。假设值为l ，2 ，r 的待测量都出现，它 们就是所毒有重复的点，其中，是所有不重复的廉中的最小蕊。我们籍此得戮馕 一1 6 一 第二章测爨无标度网络的糜指数 为霉的点的频数磊： 五掣鲰。) 一k ( x l = 缸- 一( 1 + 。) 1 媾2 ) 其中，表示值塞的最太等级。雕越，r 是方程霭旷盎一i 专习咱l = i 酶粳， 测量藏巾所有窭璃遂靛值鹩个数势僦警f 手嚣。爹吨。 命题2 2当n 较魁时，如果整教型最大等级统计序列h 一l 满足 n 培爆一蠢，其中是赫l ，哦，鄂么它们近能服从指数为穗的幂谗。 证明：巍y t 对，n y 一穗n t - - a ，则出现了i n y - a j 个不耋复的点注1 ，剽 p y 捌黼p k i 叮弘掣 当y t 对，所有不重复的点蚝，埒和重复的点h ，确出现7 ，剿 p y 爹一 ， 詈= 擐弗f y l 一矗一f 卡薹) 一穗 戳上藕式在箍_ 哮瞬，郡透徽予公式0 。薹，。 2 3 评价对比 口 我翻分裂在d k 巾、太三群鞯本塌台模掇了幂律麓梃数，馘隧较频数法、最 大等缀法、中闻等缀法【7 】、顺序法p l j 和著名的鞲| l 方法 2 踟对幂指数稳的估 毒 计精度。我们发现谯l 口2 菇2 区间内，最大等级法的姒蠛是最低的，方麓也 低予频数法。实验散果非常好。 2 ，3 。 方差分新 我们试图利用方蕊分析最犬等缀法拟台幂指数的稳定性，期望能定性撼比较 最大簿缓法和频数滋。耀鼹公式黧+ 静酌幂律越枫数将散毒于l o g - l o g 坐搽巾麴囊 线上，溺此采用阶线性拟合。 4 【髫j 灌示下整数，即不大子五的最大艘数：陆 袭示上艇数。即不小予善的最小整数 汪2 芷搠繁l 章表1 1 熊添，现有绝大韶分冤标度网络的鞯攒数郝位子该鹾阅内。当a 2 时，幂 律分砖黪方蓑无澉太，杂掇现h u b 蒂煮，缫鼗度量现出麟攘矜纯。 一1 7 一 z弑 氆 一 智 竿圹 配一 阿 第二帮测盘无标腱网络的度指数 点岸剽 鼠，瓿冬l 经过线牲攒合褥到超定方程ae = 罄a 箕中，越奢系数酶 a = 一( 去) 黧骞争一嗣e l o g x j - 雨 其中，蹴为避霉麴样本方莲，t o g x 一熹耋ll o g x , ，爨l o g 爹的游方差。 易知，频数法的拟合方差是上式在独立同分布下条件下的极端情形，此时有 蚤袋= 砖序，箕孛，g ；楚频数，的对数l o g f 数方差。 这样的结果，髓我们在缺麓高深数学工具觞条件下，滩以对频数涟，最大等 级法、顺序法等方法做出明确的定性分拼。因此，避行规模不等的数傻模拟，以 院较宅翱韵实验健蕤甚摹誊必要。 2 。3 2 平均相对误差 壤攒命题2 。l 期，可黻爝均匀努帮获得幂律蘸枫数。我稠嗣m a t l a b 指令 x ；f l o o r r a n d ( 1 ，n 6 ( 一1 a ) ) 生成个幂指数为a 的幂律随机数。具体 地，取了n = 王萨，1 0 * ，王炉三秭情况分别貘裁。 为了比较后萄撬剽的几种测定方法的攒台精度，我稍定义了一个新指标： 定义2 1 ( 乎均相对潢羞，a v e r a g er e l a t i v ee r r o r )程论值l 与若干模拟值的均 毽麓糖对误差鑫穗盘l ，上麓蚜馕，就是平均相对浚差： 2 ，3 。3 模拟 一幽fi 墨l 卜瓿i 利：点罨产 落- o l 窭8 l 窭2 臻l 4 2 3 ( ) 汇聚到中间 受文献计量学审捆关统计手段静襄发闭，我稍不禁想：谯爱太等级法麓第二 步中，我躺麓否把德重复的蔗溉聚到其它地方，丽幂只是顺序最大的点2 比如， 一1 8 一 蒸二章测蹙无檬度麟络懿攫辫教 瓶聚到中间，若待溅值鼍一兰x t ，取惫窭【t s + t j ，即中间等级法。 二数据鹣瓣篦 我们分别在= 1 0 3 ，1 0 4 ，1 0 5 三种场合，比较了频数洼、最大等级法、中间 镣缀法、灏廖法瓣均值煮标准差，魏霉2 ，3 羹匿2 。5 所示。 留2 3小规模：一工0 3 ，崔疹长为0 0 5 的区问l a 2 上模拟3 0 次 霉2 4 孛等攥攘：露一薹，裁步装受0 0 5 鳃嚣瓣1 建2 上壤稼凌。 我蜘以公式稼。3 中定义的a 惩舞主簧簿量指标。由予大部分融螺的复杂网 络的度指数l 穗2 ，因此我桐黧点考察该区阔肉的情况，取步长o ，衢，弗在 每个8 值处模拟次，最后算出a 霖e ，如袭2 。1 所累。这媳模拟结果显示： ( 1 ) 在备种场合下，顺序法比较稳定，它拟台的鞯指数的标准差曲线较平坦，而 频数法戆渡动较太； ( 2 ) 最大等级法的精度壤商，其次是中阉等级法，辫样本辕少对( 如一1 0 s ) ， 顺穿法的糖壤高于频数法，样本缀多麟( 如鬻1 0 s ) ，则相反； 移) 随着随机数规模增多，凡种方法的a r e 都在下降，都有趋透于幂指数静真 实值的趋势，但稳定性都在下降； 一1 9 一 第二牵测量无榉度网络的艘指数 圈2 5 犬规模：n = 1 0 s ，在步筏湾氇衢酌送阚1 氇2 上模揿3 0 滤。 ，瓣于整数型褰襻随概曩，最大等缀法在遂愿个摸撅条律下的袭现都援 好，a r e 最小，精度较离。 规模频数法最大等级法中阀等级法顺序法 薹秽l ? 。瓣锈l + 2 雾冁7 。2 露| 霪3 璐 1 0 49 。7 8 诼o 。2 8 5 。3 i l ，ll 1 0 55 5 l o 。ll 3 。3 4 1 0 ，6 5 表2 。1分嬲对1 0 3 ，薹萨，麦炉拿豢譬篷撬歉，在箩长黪黪鋈矮1 穗2 砖横拱3 0 凌， 得到凡种方法的期陵飘 - - ) 凄受1 麓蘩点戆个数 利爝公式( 2 。2 ) ，可以模拟龅度为l 的节点的个数矗翱冀它度很小的节点个 数，例如， = 张( i 一2 - a ) 。我们依然以a r e 作为衡量其计算精度的指标，如 表2 。2 聪添。鍪2 ，6 霆对磊帮磊月最大等级法避行耩掇麴效慕图， 图2 6 n = 1 0 器，在步长为0 0 5 的区问1 n 2 上模拟3 0 凌，分别计算曩，如 一2 0 一 第二鬻测量毙檬艘网络的麟指数 裹2 2 纛吨靛a r e 。 ( 四) h i l l 方法 n e w m a n 建议瞄习，蔫h i l l 秀法采髓诗复杂褥终节煮鹣度指数。攀实上， 该方法就是最大议然估计一对于节煮羽度 西，警l ，标准化后得 老冬1 ，其中 d ，l d = d 擢慧 d l 当且仅当 翌一fi n 拿搿0 a 管 疆勰羹墓然函数p c d i 盛= 羹：lp 挺赫一殛。馘站哺最大一敖煮； 鑫= 露( 砉t n 去) “1 n e w m a n 认为这个方法简单可靠，不受拟含误差影响。该方法的难点是 絮髂确定蓊始煮赫，一旦逸定就恕，鞣伐天公戴诗算。我翻在医阀 o 1 穗1 5 上鞭步长0 。0 5 耩拟，对每个口都穷举了一茹l ，0 2 ，- ，茹n l ，辩 以最小的穗是作估计值a ，取n = 1 0 4 。僵我们发现，实验缝聚并不像n e w m a n 说 褥那么好，当穗1 辩误菱越来越太，在臻= 1 5 憝鹣稠黯误差藏褰这5 毒。笠露， 如图2 7 所示。它没宵最大等缀法精确。 2 4 小结 匿2 7蠢步长荧。0 5 戆区藏0 。5 建1 5 蠹对h i l l 方法昀模掇。 最大等级法的提出受劐顺序法扁零，但它姚那些方法冀优秀。燕麴袭2 1 新 一2 l 一 第二牵测攫无标度网络的艘指数 示，笼谂样本多寡，它对整型的攀律随机数都霄缓好的判断力鞠很高的髂计耩 凄。我编溉对它麴歪确健徽誊了程明命题2 。l 翱命题2 ，2 掰透，又赞瓣不同群本 场合，模拟验证之( 黼2 3 至圈2 。5 掰示) 。 一2 2 第三牵利用度挖掘节点的角色 第三章刹澜度挖掘苇燕的惫色 根据e 眦的第十九次“互联网报告”，搜索引擎是当前攮常用的第三大网 络服努l l 国。然焉，蕊于自然语言溪处理技术的不藏熟，缱褥搜索孳l 擎憨发震遭 逶到糕蹶。因就，簧想提高检索溪羹，需要磷究w e b 酶结鹅戳获蒋痘发。1 9 9 8 年，g o o g l e 的创始人b d n 和p a g e 戢旱把结构分析弓i 入搜索技术中 2 0 ，4 0 】，提出 了p a g e r a n k 算法。犟期不知名的g o o g l e 运行了这一技术，健萁搜索质量远离于 其德竞争蠢。p a g e r a r a k 霆蓠个瓷莛耀存寿裔囊馁魏、影嗡壤大翡一个藏动蛾把 复杂系绫鹩结构情惠运精于大攥摸王业诗算的赛践。尽管它的溅现躁复杂网络理 论没有美系正1 ，但复杂网络研究常把它作为范例，以说明从结构角度，尤其是从 节点盼魔的角度，来研究复杂系统的方法的有效憔。 3 。1 翻然模型 p a g e r a n k 是基于宵向赋权图的带点的标量权蓬来分析网页角色的。本带及第 3 2 苇将囱粗及糖趣介缡我嬲礁定警点觳重酶过程：我锏先麓度数点权重并戳邻 接矩阵韬录，却发飘遥种方法懿“媾曾链大。在激m a r k o v 链纛囊并努辑初始攮垄 后，却发现它的平稳分布p a g e r a n k 不唯一，因此还须继续改进。 3 。1 + 1 露面的极董 由于w e b 豹冤标度性，不同隅霓是不平等酌，入度高的贾面更容易受关注。 因此，判断网页是谮藿要，最简单的方法就是看其入度，这样只需记录其邻接矩 阵就霹馘了。然而，遴过作弊制造一个拥有缀赢入度的网页并蒜娶难事。所以哭蓑 注凄的话，薏萎僵无蔻予搜索震量爱黼增热了“嗓意气这样徽翁虢赢主要有； ( 1 ) 节点的角色( 即掇重) 受到包括入度在内的多个信息的影响，而不只是度； ( 2 ) 繁点的地位不警等，不只意味精度的不平等，而是节点的粳重的不平等； 3 翦赢的觳重蓬麓辩予整个网络寨说翁，蘑不只翔对于与冀糯连翁煮。 因此，既要关涟网页的入度( 悬露受欢迎) ，叉要关注链向它的源网页的极重 ( 受谁的欢迎) 。g o o g l e 用p a g e r a n k 乘袭示节点的抽象权重，落的提出基于遮榉的 剖意：娥许多撬震嗣茭篷搂过采酶穗蠹，必定避建说凄阏茭”斟。 把糯户浏览网熏的行为视为溅祝事件，网瓣的“角色”体现在它被髓枫煮击 的概率上。网页越重簧( 权重越失) ，它被点击的可能性就越大，链向它的其 垃p a g e r a n k 察枣世界湖予1 9 9 8 年始霓壤变献1 2 0 4 8 1 ，艇两者是在同一时翩蠹被礁立磷究的。 一2 3 第三耄剁糟度挖掘节点的角色 它嬲受就越多。点击概率最赢( 诫霹度最高的网员，应该排剥搜索结果盼蘼 瑟。p a g e r a n k 豳g o o g l e 定量，与闷骚戆具倦戆察悉关，整褥壤教麟贾竞满澜霹 钻。肖三个因素影响潜p r 值：入度、入链的澡网页的p r 值、出度。 3 1 2 对p a g e r a n k 的建模 诺勃戳下两个暇竣，我惘可烈建立裙始的p a g e r 撤模型： 假设3 1任何网辩都有出链，即vz f 1 ， ，有0 ( 撕) 0 。 慑设3 2搜索荸l 擎效艇行劐索葶 豢藤，曛络瓣结擒莰有发生菠变。没寄隧委被 发舔或藏删除，各瓣霁褥酶超链攘氆没有竣变。 这两个假设并不竟分，要对p a g e r a n k 作过程论上的分析述须补充假设，见第 3 2 带，但是嚣前我蜘昃霜这两个霰设。睡夏的p r 值与震户越撬浏览刹它懿概率 搁对癜。根据条棒概攀公式有： 杖 p 哟被浏览) = 同 冁_ 嘶l 蛳被测监 户 弛被浏览 班毳汀记录网页妣与鳓的链接，瓣肴超链接姚衅鸫则幻一熏，否则矗。一0 。铆， 的出度为o ( 毗) = 篓1l ；j 。将它们代入上式，得到初始p a g e r a n k 模型： n ， 冁净善葫蠼蝴 4 ；l 公武3 。1 ) 反应了上霞提及的兰个影嗨p a g e r a