（通信与信息系统专业论文）复杂网络中链路预测问题的研究与实证.pdf

论文题目： 学科专业： 研究生： 指导教师： 复杂网络中链路预测问题的研究与实证 通信与信息系统 商超签名： 王林教授签名： 摘要 舢f i | f i i i l l l | i l i i i f f i f l f l i | | i i i j y 2118 0 6 4 近年来复杂网络的研究受到了越来越多不同领域学者的共同关注，而网络中的信息检 索和恢复也是长久以来备受关注的话题之一，其中链路预测便是近几年来的一个新兴和热 门方向，对它的研究有着重要的理论和现实意义。 网络中的链路预测通俗地讲，就是指怎样通过网络的已知信息来预测在没有直接连边 的两个节点之间产生一条新连边的可能性。 在计算机领域，对链路预测问题的研究主要是提出了一些基于马尔科夫链和机器学习 过程的算法作为探讨的思路和方法，但是这些方法在物理上不简洁。从复杂网络的角度来 研究链路预测是一种全新的方法，它利用了网络拓扑结构中所包含的隐藏信息资源，来帮 助我们挖掘和预测网络的连边情况。最重要的是，这种方法比较简单可靠且具有很大的普 适性。 本论文基于复杂网络背景来研究链路预测问题，给出了问题的描述和评价方法，详细 介绍了一些基于相似性的预测算法，最重要的是基于b a 模型构造了静态的无标度网络和 基于收集到的论坛数据建立了一个动态的b b s 兴趣网络，并分别在这些网络上实现了链 路预测的数据处理过程，最后给出了预测的准确率，并对结果进行了相应的分析。通过研 究和实证，我们发现采用了相似性算法的预测效果都好于随机预测，这有利的证明了网络 的拓扑结构中确实包含有关于网络连边的隐含信息，可以用来进行链路预测。同时对于具 有无标度特性的网络来说，c n ，l p ，p a 和k a t z 都是优秀的算法，但应尽量避免使用 l h n i 和l h n 1 i 算法。 关键词：复杂网络；信息检索；链路预测；无标度；拓扑结构：相似性 西安理工大学硕士学位论文 t i t i e ：t h er e s e a r c ha n de m p i r i c a is t u d yo fl i n kp r e d i c t i o np r o b i e mo n c o m p i e xn e t w o r k m a j o r ：t b i e c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s n a m e ：c h a os h a n g s u p e r v i s o r ： p r o f l i nw a n g a b s t r a c t s i g n a t u 陀 s i g n a t u r e v t h er e s e 锄c ho fc o m p l e xn e r kh a sr e c e i v e dm o r ea n dm o r ea t t e n t i o ni nr e c e n ty e a r s o n eo ft i l el o n gd i s c u s s e dt o p i c si st t l ei n f o m a t i o nr e t r i e v a la n dr e c o v e r yi nr l e t 、o r k t h e p r o b l e mo fl i m ( p r e d i c t i o ni sa 眦w 锄dh o td i r e c t i o nn o w i th 嬲i i i l p o r t a m 也e o r e t i c a la u n l d p r a c t i c a ls i g i l i f i c a n c et os t u d y l i m 【d r e d i c t i o ni st oe s t i m a t et h el i k e l i h o o do ft h ee x i s t e n c eo fo n ee d g eb e t w e e nt 、 ，on o t d i r e c t l yc o n n e c t e dn o d e sm r o u g ht h el ( 1 l o 帅i n f o m a t i o no fc o m p l e xn e 阳，o r k i nm es c i e n c eo fc o m p u t e r s o m ea 1 2 0 r i t b m sb a s e do nm 矾( o vc h a i n sa i l dm a c k n e l e 锄i n gp r o c e s sh a v eb e e np r o p o s e d 髂t h em a i n i yi d e a l s 觚dm e t l l o d st 0s o l v et l l i sp r o b l e m b u tt h e s ew a y sa r en o tc o n c i s ep h y s i c a l l y f o 姗t h e 弱p e c to fc o m p l e xn e t 、v o r kt 0s t u d yl i n i 【 p r e d i c t i o np r o b l e mi sak i n do fb 咖d n e wm e t h o d t h i si d e a jc o n s i d e rt h ec h a r a c t e r i s t i c so f n e t w o r ks t n j c m r ec a r e 凡l l y u s i n gt h eh i d d e ni b m a t i o nc o n t a i n e di nm es t l l l c t u r e ，w ec 觚 m i n e 锄df o r e c 勰tm es i t u a t i o no fl i l l l ( s t h em o s ti m p o n 锄ti st h a ts t r u c t u r ei i l f o 肿a t i o ni s e 雒i e rt 02 e t 锄dm o r er e l i a b l e a tt h es 锄et i m e ，i th a sm o r eu n i v e r s a l i t y i i lt h i sp a s s a g e ，w es t u d yt h el i m 【p r e d i c t i o np r o b l e mb a l s e do nt l l ec o m p i e xn e t 、o r k b a c k 汀o u n d t h ed e s c p t i o l l s 鲫dt h em e t h o do fe v a l 眦i o na b o u tt i l ep r o b l e ma r eg i v e n a1 0 t o fl i n kd r e d i c t i o na l g o r i t h m s 硼ei n t 刚u c e dc 锄e 允l l y w bc o n s t m c t e ds t a t i cs c a j e f r e en e r l ( s b a s e do nt i l eb am o d e l ，锄de s t a b l i s h e dad y n 锄i cb b si n t e r e s tn e t w o r kb a s e do nt h ec o l l e c t e d d a t a i i lt i l e s en e t 、o r k s 、v e l l i e v e dt l l ew h o l e 纰p r o c e s s i n ga b o u tl i m (p r e d i c t i o n r e s p e c t i v e l y f i n a l l yw eg o tt h e 觚c u m c yo np r e d i c t i o n ，锄d 锄a l y z e dt l l er e s u l t s t h r o u g ht l l e 陀s e 纠汜h 锄de m p i r i c 出s 砌y w ef o u n dt i l a ta h n o s ta l l 出g o r i t h r i l s 啪g e tb e t t e re f r e c tt l l a l l m d o mp r e d i c t i o n t m sd r o v e dm a tt 量l et o p o l o g i c a js 仃u c n l r eo fn e t w o d ( i n d e e dc o n t a i ns o m e i m p l i c i ti n f o n n a t i o na b o u te d g e s f o rt l l es c a l ef r e en e t w o r i 【 c n ，l p p aa 1 1 dk a t za 陀e x c e l l e n t o n e s b u tw es h o u l da v o i dt ou s el h n ia 1 1 dl h n - i i 1 ( e yw o r d s ：c o m p l e x 眦似，o r k ：证f o 册a t i o nr e t r i e v a j ；l i n kp d e d i c t i o n ；s c a i ef k e ；t o p 0 i o g i c a l 蛐m c t u r e ； s i m i l 撕t ) r i i 1 绪论 1 绪论 1 1 课题背景 近年来，学界关于复杂网络的研究正方兴未艾。 世界上任意两个陌生人要经过多少个朋友才能相互认识彼此? 我们每天接触的网络 上从一个页面到另一个页面需要多少次超链接? 大城市中的交通堵塞问题为何如此严重， 有没有解决的办法? 各种各样的信息是如何在人们之间传播的? 以及大面积的流行病是 如何在人类和动物之间流行传染的? 这些问题虽然看上去各不相同，但每一个问题中都涉 及到很复杂的网络，包括社会关系网络、1 1 1 t e m e t 、城市交通网络、生物网络、经济网络、 电力网络等等。而且，越来越多的研究表明，这些表面看上去各不相同的网络之间竟然有 着许多的相似之处。 从上世纪九十年代以来，以互联网为代表的信息技术的快速发展使人类社会大步的迈 入了网络时代。从科研合作网络到各种社会关系网络，从互联网络到大型交通网络，从大 脑神经网络到各种生物网络，人们已经完全生活在一个充满着各种各样的复杂网络的世界 中，人类社会已经网络化。这既给人类社会生产和生活带来了极大的便利，提高了人类生 产效率和生活质量，同时也给人类社会生活带来了一些负面的影响，如传染病的大肆蔓延， 谣言的大面积传播等。因此，人类社会的日益网络化需要人们对各种不同的人工或自然的 复杂网络的行为有更好的认识。长期以来，社会网络、生物网络、通信网络分别只作为社 会学、生命科学、通信科学等不同学科的研究对象，而对于各种看上去互不相同的复杂网 络之间共性和处理它们的普适方法的研究正是复杂网络理论所要关注的。也是从上世纪末 开始，对复杂网络的研究正逐步渗入到数理学科、工程学科和生命学科等众多不同的学科 领域。对复杂网络的定量与定性的科学研究，已经成为网络时代科学研究中一个极其重要 的挑战性课题，甚至被称为网络的新科学( n e ws c i e n c eo f n e t w o r k s ) 。 值得注意的是，国际上有两项开创性的工作掀起了对复杂网络研究的热潮，带领人们 重新认识了我们所熟悉的网络。打破了人们一贯以来认为理所当然的随机图理论从2 0 世 纪6 0 年代开始长达4 0 多年的统治地位，宣告了现代复杂网络这一新学科分支的诞生2 1 ， 被认为是复杂网络研究新纪元开始的标志。一是1 9 9 8 年学者w a t t s 和其导师s t r o g a t z 在 n a t u r e 上发表的题目为“小世界 网络的集体动力学的文章1 ，提出了著名的小 世界( s m a l l w o r l d ) 网络演化模型，指出它是从完全规则网络到完全随机网络过程中的转变。 小世界网络的特性既包括有与规则网络类似的聚类性又包括有与随机网络类似的较小的 平均路径长度。然而，传统的规则网络和随机网络的演化机制无法用来建模重现真实网络 的这两个特性，于是认为，小世界网络模型能更加充分地描述真实网络的属性，是对真实 网络更加精确的匹配。二是b a r a b 6 s i 教授和他的学生a l b e n 于1 9 9 9 年在s c i e n c e 杂志 上发表了题目为随机网络中标度的涌现的文章“1 ，文章中指出许多实际的复杂网络的 连接度分布并非是泊松分布，而是具有幂律( p o 、e r - l a w ) 形式的，网络中节点的度分布 西安理工大学硕士学位论文 严重不均匀，其中绝大部分节点的度值都很小，却也存在有少量度值相对很大的节点。由 于幂律分布严重不均匀，并不会表现出明显的特征长度，因此将具有此种特性的网络又称 为无标度( s c a l e 舶e ) 网络，同时他们还根据优先连接的偏好依附机制构造了无标度模型 来重现真实网络的这一特性。 随后，学者们又对各种复杂网络的种种特性进行了相应的研究，国内科学界也注意到 了这种趋势，并且也已经开始加入到了这一队伍中，展开了一定的讨论。可以说，加入复 杂网络圈进行研究的学者主要来自图论、统计物理学、社会学、计算机科学、生物学以及 经济学等学科领域；所涉及的网络包括社会网络、i n t e m e t 网络、各种生物网络( 细 胞网络、蛋白质相互作用网络、神经网络、食物链网络) 等；研究中所使用的方法主要是 理论数学中的图论知识、物理学中的统计物理学方法以及社会学中的网络分析方法。 总的来说，目前对复杂网络的研究在理论和实证两方面都取得了很大的进展，复杂网 络已经成为分析复杂系统的必不可少的有力工具之一，对它的探讨已经吸引了越来越多学 者的兴趣和注意。然而有关网络分析的另一个重要问题信息检索及恢复却始终没有引 起足够的重视。狭义的信息检索指的是从信息集合中找出所需要信息的过程，也就是我们 常说的信息查询( i n f o m a t i o ns e a r c h ) ；它还可以被理解为是对字词或文献之间连接预测 的处理，或者更进一步扩展为对一些链路挖掘问题的研究。对链路预测问题的认识就属于 信息检索领域的一部分内容，通过已知信息挖掘未知信息，这在现代信息科学中是一项长 期的挑战5 1 。 1 2 课题目的和意义 目前对于网络的进化，结构和功能的研究6 1 ，许多物理学家已经给予了充分的说明， 无论在理论还是实证方面都取得了很大的进展。如发现了网络的小世界特性，无标度特性， 以及集聚性，自相似性等。其中特别是网络中无标度( s c a l e 舶e ) 性质的提出，开辟了复 杂网络研究的新天地。 复杂网络从一种新的思维角度来研究复杂系统，是一种新方法。同时，随着计算技术 的快速发展，人们对大规模数据的处理能力有了很大程度的增强，为通过收集多种不同的 网络数据来进行比较研究和综合概括提供了可能性，这样就可以更好的揭示和理解这些网 络的内部结构，形成机理以及它们所呈现出来的各种统计特征。其实，从理论和实际应用 两方面来说，对复杂网络的研究都有着十分重要的意义和前景。一方面，对网络的研究可 以帮助我们更好地了解和解释人们置身其中的现实世界：另一方面，我们还可以把理论研 究的成果应用到具体实际问题当中，使得网络理论可以为我所用，从而更好的指导实践。 链路预测( 1 址p r e d i c t i o n ) 是复杂网络研究的一个新兴问题，受到物理学界的关注得 益于2 0 0 8 年学者c l a u s e t ，m o o 陀和n e 、n 孤在 自然杂志上发表的题为 网络中的分 层结构和缺失链接的预测h 1 的论文，以及r e d n e r 在 自然上发表的题为 ( 七) 时，网络中存在的度值为k 的节点会很少，有时甚至可以忽略这些节点的存在， 认为几乎不存在这样的节点。具有这种度分布特质的网络因此也被称为均匀网络 ( h o m o g e n e o u sn e t 、o r k ) 。 随着研究的深入，近年来学者们通过对大量真实网络进行深入研究后发现，绝大多数 网络的度分布与匀质的泊松分布明显不同。统计显示，包括互联网，万维网，以及新陈代 谢网在内的大多数现实网络，他们的度分布函数都存在有一条长长的幂律尾部，更适合用 幂律分布函数尸( 七) 芘七一r 来进行描述，如图2 2 ( b ) 所示。幂律分布曲线比指数分布曲线的 下降要缓慢得多，因而网络的度分布表现的并不均匀，在一个大规模的节点众多的网络中， 节点的度值相差悬殊，绝大部分节点的度值都很小，但同时也存在有少量度值相对很大的 节点。因为幂律分布没有明显的特征长度，因此也将幂律分布称为为无标度分布，将度分 布具有幂律分布形式的网络也称为无标度网络。幂律特性表明了无标度网络是非均匀 ( i n h o m o g e n e o 惦) 的，其中存在的那些少量的度值相对很高的节点就成为了网络的中心 节点，有时也称为h u b ( 集线器) 节点。 度分布还有另外一种表示的方法，称为累积度分布函数，用如下公式表示： e = ：尸( 后) ( 2 3 ) 七= 七 从表达式中可以看出，它表示的是节点的度值大于七的概率，这种表示方式具有可以 包括所有的原始数据的优点。研究发现，如果度分布函数为幂律分布，且幂指数为) ，的话， 那么相对应的累积度分布函数也为幂律分布，且其幂指数为 ，一l ；如果度分布为指数分 布，那么累积度分布函数也是指数分布，并且两个函数的指数是相等的。指数分布和幂律 分布在正常坐标系下不容易分辨出来，但是通过分别采用半对数坐标系和双对数坐标系就 可以很容易的将两者分辨开来，因为指数分布在半对数坐标系中近似表现为一条直线，而 幂律分布在双对数坐标系中也会近似的对应于一条直线。 西安理工大学硕士学位论文 o ( a ) 泊松分布 ( b ) 幂律分布 图2 2 泊松分布和幂率分布 f i g 2 - 2p o i s s o nd i s t r i b u t i o na n dp o w e r - l a w d i s 仃i b u t i o n 2 3 2 平均路径长度 网络中，连接两个节点的路径一般会有很多，其中必然存在有一条最短的路径，我们 定义这条最短路径上的边的数目为这两个节点之间的距离，并将节点i 和i 之间的距离用 吐，来表示。网络的直径定义为所有节点对之间的距离的最大值，用大写字母d ( d i 锄e t e r ) 来表示。网络的平均路径长度用l 来表示，有时也称其为网络的特征路径长度，它的大 小等于所有节点对之间距离的平均值。用平均路径长度可以描述出网络的大小，或者说是 网络中节点间的分离程度。 网络直径d 和平均路径长度l 的公式分别表示如下： d = m a x 吒 ( 2 4 ) 1 j 扛r - 吒 ( 2 5 ) 主( “) 陀7 其中n 表示网络中节点的总个数，同时假设节点到自身距离的大小为0 ，即d ，= 0 。 平均路径长度l 和直径d 有时也被用来作为衡量网络的效率和传输性能的参数。 通过对大量复杂网络的研究，人们发现了一个重要的现象，那就是现实世界中的绝大 多数大规模的真实网络，它们的平均路径长度远比人们想象的要小的多。大家很容易想到， 随着网络规模的增大，平均路径长度当然也会相应的增大，但是研究证实它的增长速度却 非常的慢，只是l n 的阶次- ，与网络规模的增长速度相比较，其增长速度明显的缓慢很 多，这也就是所谓的著名的“小世界 现象。这一提法开始于著名学者m 订鲈锄所做的“小 世界”试验，试验的具体内容是将一封信通过多名参与者来进行传递，并最终传递到指定 的收信人手中，同时要求参加实验的每个人拿到这封信后只需将其传递给他们认为有可能 与收信人熟悉的一个人，想用这样的方式来找出熟人网络中路径长度的分配情况，结果显 示平均只需要通过6 个人，这封信就会成功到达收信人的手中，而并非需要通过大量的中 1 2 2 复杂网络基础理论 间传递者，由此我们不得不感叹于这个世界真小，这也就是我们后来经常提到的“六度分 离 学说。 2 3 3 聚类系数 网络的紧密程度，或者说网络中节点的聚集情况是用聚类系数c 来描述的。研究发 现，几乎所有的社会网络都会呈现出小集团形态的共同特征，这里小集团的具体表现为朋 友圈或者熟人圈，在圈子中的任意一个成员与圈中其他的每个成员都认识。聚类系数通俗 的说指的就是你朋友的朋友可能也是你的朋友的情况，或者你的两个朋友之间也可能彼此 是朋友的情况。这是一种内在的群聚倾向，可以用群系数来进行量化。计算聚类系数的方 法为：我们让网络中的一个节点i 与其他七，个节点相连接，即节点i 有七，条边，那么如果 假设这t 个节点之间的任意两个节点都是相互连接的，显而易见在这毛个节点之间最多可 能存在着七，( 七，一1 ) 2 条边，然而实际上在这七，个节点之间却只存在着e ，条数目的边的话， 则将e 与七，( t 一1 ) 2 的比值定义为节点i 的聚类系数q ，即 g = 2 巨( 七，( 屯一1 ) ) ( 2 6 ) 知道了网络中每个节点的聚类系数，就可以计算出整个网络的聚类系数c ，它定义 为网络中所有节点i 的聚类系数c 的平均值，即： c ：丢兰q ( 2 7 ) n 急l 很明显，当且只有当网络为全连通网络时，即网络中的每个节点与网络中的其他所有 节点都有连边时，整个网络的聚类系数才能达到最大值，等于l ，一般情况下它的取值均 小于1 而对于完全随机的网络来说，经计算其聚类系数c 等于l 。学者们通过实证表 明，几乎在所有的大规模真实网络中，它们的节点都是倾向于聚集在一起的，表现在聚类 系数上就是尽管c 的值会远远的小于1 ，但也都会远远地大于完全随机时的取值l 。 在此还有一种特殊的情况，当节点的度值为0 或者l 时，那么分子和分母都会为0 ， 此时我们认为c = o i 艮显然，聚类系数有一个取值空间，0scsl 。要使整个网络的聚类 系数c = 0 那么只有在网络中的所有节点均为孤立节点的情况下，因为此时网络的总边 数e = 0 ，从而使得整体取值为0 ；同时也只有在网络是一个全局耦合网络的情况下，即 网络为全连通网络时，才会取得最大值c = l 。 2 3 4 协调性系数 协调性系数是用来刻画网络中邻居节点之间度值相关性的一个参数，也被叫做度一度 相关性( d e g r e e d e g r e ec o 玎e l a t i o n ) 。使用协调性系数可以帮助人们解决这样一类问题 度值较大的节点到底是倾向于连接与自己一样度值较大的节点昵，还是倾向于连接一些度 值较小的节点呢? 其实，现实中以上这两种情况都是有可能发生的“。因为节点的度是 西安理工大学硕士学位论文 用来描述网络的一个重要拓扑参数，自然与度有着紧密关系的协调混合性也是吸引了越来 越多研究人员的注意力。 关于怎样来衡量一个网络的协调性，前人也提出了一些相应的指标。例如学者m a s l o v 和s n e p p e n 就提出了一种通过画出网络中每一条边的两个端节点的度二维图的方法和思 路，同时他们也使用这种方法在互联网络和蛋白质相互作用网络上对协调性进行了实证研 究。上面的方法比较复杂，著名学者n e 、m a n 则提出了一种比较简单的方法，他通过定 义一个系数，直接来描述网络的协调混合性，并且规定如果这个系数大于零，则说明网络 是正相配的，度值大的节点之间倾向于互相连接：否则，该网络是负相配的，度大的节点 反而倾向于和度小的节点相连。 按照协调性所表现出来的特征我们可以将网络分为两大类。一类称为同配网络，此类 网络表现为它的协调性是随着度值k 的增加而相应增加的：另一类则称为异配网络，表现 为网络的协调性随着度值k 的增加反而是减小的。同时通过观察，人们还有一个很有趣的 发现，那就是几乎所有的社会网络都表现出了同配性，而几乎所有的生物网络，技术网络 和通信网络都不约而同的表现出了异配性。但到目前为止，科学家们还没有完全弄清楚造 成这种奇怪现象的原因，然而通过观察协调性是同配的还是异配的却能给人们提供一种简 单的用来区分社会网络和技术，生物网络的方法。 协调性系数r 的概念是由学者n e 、唧a i l 在2 0 0 2 年时提出的，r 用公式表示如下： m _ z t _ 【肘一专( z + t ) 】， ，= 1 _ _ 垒i _ 一 ( 2 8 ) 肘_ 。去( 笄+ 砰) - 【m 一。吉( z + t ) 】2 在上面的公式中，和t 分别表示的是第i 条边两端节点的度值的大小，其中 i = l m ，m 是网络中边的总数。计算得到r 的值后，若厂 0 则对应的是同配网络，自然若 ， k ，保证这个网络尽可能的稀疏。 ( 2 ) 随机化重连：以给定的概率p 随机地将网络中的每条边重新连接一次，即让选 中边的一个端点保持不变，而让另一个端点是以随机地在网络中其他的节点间挑选而产生 的，并最终要求保证没有自环和重边产生。 其实，网络中这些重新连接的边一般都是一些“长程连接”，它们可以使网络的平均 路径长度大大的缩小，而对整个网络的聚类系数却只有很小的影响。 诚然，在以上构造算法中，只要简单的通过调节连接概率的p 值，就可以很容易的实 现从完全规则网络到完全随机网络的演化过程，其中当p 等于0 时对应于规则网络，当p 等于l 时对应于随机网络，当p 取0 和l 之间的任意值时就可以得到一个具有小世界特征 的复杂网络。这一过程如图2 5 中所显示。 1 7 西安理工大学硕士学位论文 规则网络 小世界网络随机网络 。一器 p = op = l 图2 5 规则网络到随机网络的演变过程 f i g 2 - 5t h ee v o i u t i o n a 叫p r o c e d u r e0 f 他g u i 盯n e t w o r k 锄d 砌d o mn e t 、) i ，o r k 由于小世界网络的特殊性，因此它会具有一些自身独有的统计特性。研究表明，对于 使用以上算法构造的小世界网络，其聚类系数和平均路径长度都表现为随机化重连概率p 的函数。当p 较小时( o p 1 ) ，通过重新连边后得到的网络，在局部属性上与原始 规则网络的差别不太大，这就使得网络的聚类系数变化也不会太大，但是网络的平均路径 长度却减少的很快，会变的很小，因此就变成了一个具有小世界特性的网络。 到目前为止，对于小世界网络的平均路径长度学者们还没有得出精确的解析表达式， 而n e w m 粕和w a n a g e 利用重整化群技术，给出了如下的计算公式： 三( p ) ：三芋( 脚2 ) ( 2 1 0 ) 公式中的厂 ) 是一个普适标度函数，它满足 似，_ 淼霉 亿 在平均场理论的基础上，普适标度函数的近似表达式为： m ) 丽鼍a r c 蝴壶 ( 2 1 2 ) w s 小世界网络的聚类系数可以解析为：， c ( 加黼( 1 刊3 ( 2 1 3 ) 它的取值保持在一个较高的水平上。 与e r 随机网络相类似，人们发现，w s 小世界网络中所有节点的度值都近似相等， 表现为一个同质网络，它的度分布函数也可以用泊松分布来表示，该曲线在平均度值 处有一个峰值，在此度值两边则按照指数趋势快速衰减。 当度值七k 2 时得出： m ) ：，篓驯刊z 一踹p 碳心 ( 2 1 4 ) 尸( 七) = q ，：( 1 一p ) p 刖2 1 等专每孓p 碳心 ( 2 1 4 ) 1 8 2 复杂网络基础理论 而当度值七 k 时，网络的度分 布可以表示为： 附) = 靠k ( 鲁广一等广“r ( 2 1 6 ) 而当七 k 时，度分布p ( 七) = o 。 2 4 4 无标度网络 1 9 9 9 年1 0 月，美国圣母大学物理系的教授b a r a b d s i 和他的博士生a l b e n 在s c i e n c e 杂志上发表了一篇题目为随机网络中标度的涌现“1 的文章，在这篇文章中他们不仅 揭示出了真实复杂网络所拥有的无标度特性，同时还建立了著名的b a 无标度网络模型， 以此为标志，使得复杂网络的研究进入了一个全新的繁荣时代。 实证研究表示，包括新陈代谢网，万维网，i i l t e m e t 在内的许多真实复杂网络，它们 的度分布函数并非具有泊松分布特性，而是有着幂律分布的形式，由于幂律分布缺乏一个 明显的描述问题的特征尺度，故将此类网络称为无标度( 尺度) 网络。人们发现无标度网 络有着实际复杂网络所拥有的最常见的两个基本重要特性，即同时拥有增长特性和优先连 接特性。首先对真实网络的增长特性来说，这意味着网络是开放的，即网络的规模并非固 定不变，而是不断有新的节点和边增加进来，不断扩张的，例如万维网上每天都会产生大 量的新的网页和链接，而在科研引用网中每个月则都会有大量的论文被发表：其次针对真 实网络具有的优先连接特性，即当网络中要增加一个新节点时，这个节点往往更倾向于优 先与那些具有较高连接度的节点生成新连边，这种优先连接的性质就会直接导致产生所谓 的“富者更富 或者叫“马太