（概率论与数理统计专业论文）无标度加权网络建模分析.pdf

摘要 中文摘要 复杂网络可以描述自然界和社会中的各种大规模系统诸如万维网、因特网、 国际机场网、细胞网、生态网、科学家合作网等等都可以用复杂网络来刻画其中 网络节点表示系统的元素，两点问的边表示元素间的相互关系 实证研究揭示了实际网络的显著特点，许多现实网络的度分布p ( k ) 具有幂律 分布，即e ( k ) 一j ：一7 ( 对于大馘这种网络常称为无标度网络。其度分布具有重尾 部特征为了揭示这类网络的演化机制，b a r a b a s i 与a l b e r t 提出了著名的b a 模 型，该模型发现了许多实际网络在演化过程中的重要机制增长与择优连接此后， 人们提出了一系列的无标度网络演化模型，并对网络模型的性质作了更加深入的研 究 复杂网络的演化模型备受关注其中加权网络模型是一个重要的研究领域所 谓加权网络即对网络中每条边赋予个权重值因为在实际情形中。系统元素间的 相互作用程度往往也有强弱之分，加权网络在这方面更贴近实际例如t 在科学协 作网中，用两个作者之间合作的文章数来表示边的权重，反映作者间的合作程度i 在国际机场网中，边的权重可以表示两个机场之间的客流量，反映机场问的往来程 度 本文主要研究具有随机权重的加权网络，提出三个加权网络的演化模型，并加 以理论分析 ( 1 ) 提出个权重演化的加权网络模型每个时间间隔增加一个新点，按照依 强度择优的原则，新点与系统中的1 1 1 个旧点连接，同时产生1 2 1 条新边对每条新 边赋予一个随机权重叫，具有分布密度p ( 叫) 同时在系统原有连线中，随机选择1 1 条不同的边，对它们增加个随机权重值a w 研究表明，该模型生成的网络权重 分布具有幂律尾部特征 ( 2 ) 提出个具有多重随机权重的加权网络模型网络中边的权重取自三种不 同的随机分布首先，把网络节点分为a - t y p e 与b t y p e ，每个时间间隔增加个新 点，新点以一定概率为a t y p e 或b t y p e 同时产生m 条新边择优连接系统中的 旧点，并对新产生的连线赋予一个随机权重a - t y p e 节点与b 毋p e 节点间的连线 权重服从分布密度伽( 叫) ( 叫0 ) ia t y p e 节点与a t y p e 节点间的连线权重服从 j 口l ( 叫) ( 硼0 ) ； b - t y p e 节点与b 锣p e 节点间的连线权重服从见( 脚) ( 1 l j 0 ) 由 此演化的网络中边的权重来自三个不同的分布类型，分别取决于连线的节点间的不 福建师范大学陈鹏辉硕士学位论文 同类型研究表明，该模型生成网络的权重分布与度分布都具有幂律尾部特征 ( 3 ) 提出个基于适应度的无标度加权网络模型假设每个点都有一个适应度 工，代表节点本身的能力水平因各个个体能力不尽相同，考虑z 是个随机变量，服 从某种分布那么两点间连线的权重可以取决于这两点的适应度，假设是关于适应 度的函数分析了网络的特性之后，证明网络的强度分布以及度分布都具有幂律尾 部 关键词：复杂网络，无标度网络，加权网络，随机权重，演化模型，强度分布， 权重分布，度分布 i i 中文文摘 中文文摘 复杂网络作为复杂性研究的一部分，巳成为系统科学，生命科学，统计物理学， 计算机科学，数学科学等众多学科的研究热点复杂网络是各种大规模网络的总称， 它可以描述从自然界到社会学领域的各种系统例如。w w w ，i n t e m e t ，基因网络， 食物链网，引文网，科学协作网( s c n ) ，国际机场网( w a n ) 等复杂网络对许多 系统的理解上有重要作用 复杂网络的一个重要特征量是度分布所谓度数即网络中一个点所连接的边 数，而度分布p ( k ) 则表示网络中随机取一点其度数是k 的概率它是个看似简 单但非常重要的统计特征量围绕度分布问题，复杂网络的发展经历了一段漫长的 探索历程 早在复杂网络理论开始的早期，当时著名的数学家e r d i j 8 和r 6 n y i 就提出了 e r 随机图模型的数学理论【1 1 此后近4 0 年间，随机图一直被奉为经典这种模型 下，其度分布服从轻尾部的p o s s i o n 分布 但是后来一项重大发现打破了人们的传统认识，掀起了复杂网络研究的新时 代1 9 9 9 年b a r a b e r i 和a l b e r t 发现，许多实际网络的度分布都具有重尾都的幂律 分布，并称这种网络为无标度网络为了解释这个现象，随后他们指出了很多实际 网络在形成过程中都遵循的普遍规则。增长与择优连接这两个演化机制，由此提出 了著名的b a 模型1 4 1 此后，结合增长性与择优连接机制，人们提出了许多可以产 生无标度网络的演化模型【6 ，7 ，1 0 i ，并对无标度网络的性质及其应用进行了深入的研 究 在简单规则下自然界可以呈现复杂结构，而在复杂背景下自然界可以遵循简单 定律网络演化模型不仅可以捕捉各种微观机制对网络拓扑结构的影响，而且对了 解更为复杂的发生在网络上的动力学行为有着重要的作用因此，探索复杂网络的 演化机理和模型建立倍受人们的广泛关注 本文主要研究无标度加权网络，提出三个具有随机权重的无标度加权网络模 型文章具体结构安排如下。 第一章简要介绍复杂网络以及用来刻画复杂网络性质的一些统计特征量，同时 详细介绍复杂网络的建模方法以及网络性质的解析计算方法，并说明本文的主要工 作 第二章构建个权重随时间增长的加权网络模型，其中边的权重是随机的服从 v 福建师范大学陈鹏辉硕士学位论文 一定分布，且随时间演化而动态变化对该网络的性质进行了理论分析，结果表明 网络的权重分布具有幂律尾部同时，数值模拟结果也验证了这些性质 第三章构造了一个边的权重取自多种不同分布的随机加权网络模型首先把网 络中的节点分为两个类型。a - t 3 m e 与b t y p e a - t 矽p e 节点与b t y p e 节点间的连 线权重服从分布密度p o ( t i j ) ( t t j 0 ) ；a t y p e 节点与a - t 黟p e 节点间的连线权重服 从p l ( t i j ) ( 加0 ) ib t y p e 与b - t y p e 间的权重服从化( 们) ( 叫0 ) 每个时间间隔 增加一个新点，并择优选择m 个旧点与新点相连接利用平均场方法推导了度分 布与强度分布，证实都具有幂律尾部，并求出了幂律指数，y 第四章基于适应度的概念，提出了个与适应度有关的加权无标度网络模型 同样地。该模型产生的网络是无标度网络 v i 摘要 a b s t r a c t i nr e c e n ty e a r s ，c o m p l e xn e t w o r k si sau s e f u lm o d e lt od e s c r i b eaw i d er a n g eo f s y s t e m si nn a t u r ea n ds o c i e t y , w h i c hh a sa t t r a c t e dm u c hm o r ea t t e n t i o n m a n ym o d e l s l i k ew 曲ii n t e r n e t ，w o r l dw i d ea i r p o r tn e t w o r k s ，c e l l u l a rn e t w o r k s ，e c o l o g i c a ln e t - w o r k s ，s c i e n t i f i cc o l l a b o r a t i o nn e t w o r k s ，e t c ，c a l lb ed e p i c t e db yt h en e t w o r k s ，w h e r e t h en o d e sa r et h ee l e m e n t so fs y s t e ma n de d g e sr e p r e s e n tt h ei n t e r a c t i o nb e t w e e n t h e m e m p i r i c a lr e s e a r c hr e s u l t ss h o wt h a tm a n yo ft h e s er e a ln e t w o r k sa r es c a l e - f r e e ：t h ed e g r e ed i s t r i b u t i o nh a sap o w e r - l a wt a i l ，i e ，p ( k ) 一a k f o rl a r g ek ， w h e r ea ，qa r ec o n s t a n t t oi n v e s t i g a t et h em e c h a n i s m sr e s p o n s i b l ef o rt h ep r o p e r t i e s b a r a b a s ia n da l b e r tp r o p o s e db am o d e li n1 9 9 9 ，w h i c hi n t r o d u c et h ec o n c e p t so f g r o w i n gn e t w o r k sa n dp r e f e r e n t i a la t t a c h m e n t i nt h ew a k eo ft h e i rw o r k s ，m a n ym o r e s c a l e f r e em o d e l sa r ep r o p o s e dt oi n t e r p r e tt h ec o m p l e xn e t w o r k s o n em a j o ra s p e c to ft h er e s e a r c hi sw e i g h t e dn e t w o r k i i nw h i c he a c hl i n ki nt h e s y s t e mi sa s s i g n e daw e i g h t i ti sw e l lk n o w nt h a ti nm a n yf i e l d st h ei n t e r a c t i o n s t r e n g t hc a nv a r yw i d e l y s ow e i g h t e dn e t w o r ki sab e t t e rm o d e lt od e s c r i b e f o re x - a m p l e ，i nac o l l a b o r a t i o nn e t w o r k s ，t h ew e i g h to far i n kb e t w e e nc o - a u t h o mm e a s u r e s t h es t r e n g t ho ft h ec o l l a b o r a t i o ns u c h 踞t h en u m b e ro fj o i n t l y - a u t h o r e dp u b s c 即 t i o n s i nt h ea i r l i n et r a n s p o r t a t i o nn e t w o r k ( w a n ) ，t h ew e i g h to fal i n kb e t w e e nt w o a i r p o r t sg i v e st h ep a s s e n g e rc a p a c i t yo nt h i sr o u t e i nt h i sp a p e r ，w ef o c u so nw e i g h t e dn e t w o r k sa n dp r o p o s et h r e ee v o l v i n gn e t w o r km o d e l st h a tc a np r o d u c ew e i g h t e ds c a l e - f r e en e t w o r k sa n da n a l y z et h en e t w o r k s b yt h ec o m b i n e dn u m e r i c a la n da n a l y t i c a la p p r o a c h ： ( 1 ) w ep r o p o s eam o d e lo fw e i g h t e dn e t w o r k sw h e r ew e i g h t so fl i n k se v o l v ew i t h t i m e a te a c ht i m es t e p ，an e wn o d ei sa d d e dw i t hs o m ee d g e st h a tl i n kt h en e wn o d e t oe x i t i n gn o d e sp r e f e r e n t i a l l y m e a n w h i l et h e s en e w e d g e sh a v ew e i g h t sd r a w nf r o m c e r t a i nd i s t r i b u t i o n p ( w ) ( w 0 ) t h e ns o m ee d g e sa r er a n d o m l ys e l e c t e d ，a n da d d s o m ew e i g h t a wa l s od r a w nf r o mt h es a m ed i s t r i b u t i o n w ec a l c u l a t et h ed i s t r i b u t i o n d e n s i t yo ft h ew e i g h ta n dd os o m es i m u l a t i o na sat e s t i m o n y i nt h i sc o u r s ew ea t t a i n ap o w e r l a wt a i lw h e r e1 2 ( 2 ) aw e i g h t e dn e t w o r km o d e lw i t hm u l t is t o c h a s t i cw e i g h t si sp r o p o s e d ，w h e r e i i i 福建师范大学陈鹏辉硕士学位论文 t h ew e i g h t so fl i n k sa r ed r a w nf r o ms e v e r a ld i f f e r e n td i s t r i b u t i o n s n o d e si nt h es y s - t e r na r ed i v i d e di n t ot w ot y p e s ：a t y p ea n db - t y p e a te a c ht i m es t e p ，an e wn o d e e i t h e rao rb - t y p ei sa d d e dt ot h es y s t e m ，w i t hmn e we d g e sc o n n e c t i n gt h ee x i s t i n g n o d e s m e a n w h i l e ，e a c hn e wc r e a t e de d g ei sa s s i g n e dc e r t a i nr a n d o mw e i g h t t h e w e i g h tb e t w e e na - t y p en o d ea n db - t y p en o d ei sd r a w nf r o mp o ( w ) ( w 0 ) ；w i t h i n a - t y p en i d e sf r o mj d l ( ) ( 叫0 ) ；w i t h i nb t y p en o d e sf r o m 助( t i j ) ( t i ，o ) t h u s t h ew e i g h to fe a c hl i n ki sf r o mt h r e ed i f f e r e n td i s t r i b u t i o n s ，r e l y i n go nt h et y p e s o fn o d e s a n a l y t i c a lr e s u l t ss h o wt h a tt h em o d e lc a np r o d u c ean e t w o r kw i t ht h e p o w e r l a wd i s t r i b u t i o n so fs t r e n g t ha n dd e g r e e ( 3 ) w ep r o p o s eaw e i g h t e dn e t w o r kb a s e do nt h ei n t r i n s i cf i t n e s s i nt h em o d e l ， e a c hv e r t e xh a saf i t n e s sd r a w nf r o mc e r t a i nd i s t r i b u t i o n ，w e i g h t so fl i n k sd e p e n d i n g o nt h ef i t n e s so fb o t he n d s t h e nw ec a l c u l a t et h ed i s t r i b u t i o no ft h ew e i g h ta n dt h e d e g r e ew i t ht h em e a n - f i e l dt h e o r y i nt h i sc o u r 舱w ea t t a i nap o w e r l a wd i s t r i b u t i o n a n dd e d u c et h ec o m m o nf o r m u l ao f - y k e y w o r d s ：c o m p l e xn e t w o r k s ，s c a l e - f r e en e t w o r k ，w e i g h t e dn e t w o r k s ，s t o c h a s - t i cw e i g h t ，e v o l v i n gm o d e l ，s t r e n g t hd i s t r i b u t i o n ，w e i g h td i s t r i b u t i o n ，d e g r e ed i s - t r i b u t i o n s i v 福建师范大学陈鹏辉硕士学位论文 福建师范大学学位论文使用授权声明 本人( 姓名)陈鹏辉学号至q q 鱼q 鱼鱼垒专业概率论与数理统计 所呈交的论文( 论文题目，垂握廑盘f i 杈网络的建模分析) 是本人在导 师指导下，独立进行的研究工作及取得的研究成果尽我所知，除论文 中已特别标明引用和致谢的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果对本论文的研究工作做出贡献的个人或 集体，均已在论文中作了明确说明并表示谢意，由此产生的一切法律结 果均由本人承担 本人完全了解福建师范大学有关保留、使用学位论文的规定，即t 福 建师范大学有权保留学位论文( 含纸质版和电子版) ，并允许论文被查阅 和借阅；本人授权福建师范大学可以将本学位论文的全部或部分内容采 用影印、缩印或扫描等复制手段保存和汇编本学位论文，并按国家有关 规定，向有关部门或机构( 如国家图书馆、中国科学技术信息研究所等) 送交学位论文( 含纸质版和电子版) ( 保密的学位论文在解密后亦遵守本声明) 学位论文作者签名1 东鹏辉指导教师签名 签名日期 ( 9 7 、石7 签名日期o 4 7 绪论 网络的概念最早可以追溯到1 8 世纪欧拉创立的图论一般而言，自然界许多 系统都存在着很多个体和彼此之间的连系而网络是由点和边组成的集合，节点和 边分别表示系统个体和个体之间的相互作用这样，许多自然和人造系统都可以用 网络来表示，复杂网络则是指由大量节点构成的，具有更加复杂的拓扑结构和动力 学行为的大规模网络，它是由大量节点通过边的交叉相互作用连接而成的图如生 态系统中，物种之间的相互关联可以描述为复杂的食物链网络；细胞被完美地描述 为通过化学反应连接化学物的网络或者如万维网、因特网、引文网、新陈代谢 网，基因网、蛋白质相互作用网，国际机场网，科学家合作网、电力网以及社会网 等等都可以用复杂网络的图形刻画 为了了解实际网络，人们总在试图揭示它的拓扑结构特征、网络的演化过程， 特别是发生在网络上的动力学行为于是提出了网络结构的几个度量标准度分布 ( d e g r e ed i s t r i b u t i o n ) 、平均路径长度( a v e r a g ep a t hl e n g t h ) 和集群系数( c l u s t e r i n g c o e i 五c i e n t ) 等等网络的度分布p ( k ) 是随机选择的节点具有k 条边的概率；平均 路径长度是网络中所有节点对的距离的平均值，其中网络中两个节点的距离定义为 连接它们的最短路径的边数；网络的集群系数则定义为一个节点的两个邻居之间也 是邻居的概率，它反应了网络内在的群聚倾向 实际网络结构复杂，节点间相互作用的情况呈现多样性，为了了解网络是如何 演化成人们所观察到的形态，许多学者先后提出了各种网络演化模型，以期更好地 再现实际网络下面就复杂网络的几个发展阶段做个简要回顾 ( 1 ) 规则网络 这一阶段始于1 8 世纪欧拉创立的图论，最初主要集中探讨具有规则结构的图 形在很长一段时间里，人们都在用规则网络来刻画实际网络。如一维链，二维平 面上的欧几里德网格等常用的规则网是由个点构成的环状网络，每个节点与 最近的耳个节点相连接，左右两边各有k 2 条边在这样的规则网络中，每个节 点的度、集群系数等网络性质都一样，节点的度分布为石函数，即尸( 七) = 以集 1 福建师范大学陈鹏辉硕士学位论文 群系数为c = 渊后来人们逐渐发现，用这种规则网络刻画复杂的现实系统在 很多情况下并不具备合理性 ( 2 ) 随机网络 2 0 世纪5 0 年代末，数学家e r d s s 和r d n y i 开始应用概率论方法研究图论问 题，提出了随机图的概念，并进一步推广建立了随机图理论【1 1 ，提出了著名的e r 随机图模型定义如下给定个节点，每一对节点之间以概率p 相互连接 由此在e r 图中，总边数n 是个随机变量其期望值j e 7 ( n ) = p n ( n 一1 ) 2 设g o 是一个有个节点仃条边的图，按上述图的生成过程，获得g o 图的概率 为tp ( c o ) = p n ( 1 一p ) ( u - 1 ) 2 一这种图常记为g c n ，p ) 此后近四十年里，e r 随机图模型成为人们研究复杂网络的基本模型 e r d s s 和r d n y i 在文章【1 】中深入研究了随机图的结构性质，最主要结果是随 机图的相变现象随机图的主要结构特征为一( 1 ) 平均路径短，它的平均路径长度 f r 口，l d i n ( n ) 增长十分缓慢，反映了实际网络的短路径特征；( 2 ) 集群系数小。它 的集群系数g 矾d 一- 1 随网络规模无限增大而趋于零，不能反映实际网络的 群聚特性；( 3 ) 它的度分布为二项分布，在大n 的情形下，它可以近似为p o i s s o n 分布，该分布有一个显著的峰值，并具有轻尾分布长期以来人们一直在用e r 模 型刻画现实世界的大规模网络因为当时技术的局限，没有一个人能检测出现实的 大规模网络是否真的符合e r 模型 ( 3 ) 小世界网络 1 9 9 8 年，w a t t sa n ds t r o g a t z 在n a t u r e ，上发表了开创性论文，提出了小 世界网络( s m a l l - w o r l dn e t w o r k s ) 概念 2 1 过去许多实际网络的拓扑结构被假定 为完全规则网或完全随机网但是实证研究表明许多生物网络、技术网络和社会网 络却介于这两种极端网络之间 3 1 w a t t s 和s t r o g a t z 在他们的文章中探究了能够直 达这两种极端网络中间地带的模型，提出了著名的w s 模型【翻从而引发了研究小 世界网络的一股热潮w s 模型的演化算法如下 ( 1 ) 从规则网络开始：从具有个节点的环状规则网络开始，其中每个节点都 与k 个最邻近的节点相连接( 左右两边各k 2 个) 为了获得个稀疏但连通的 2 网络，要求l n ( n ) 1 ( 2 ) 随机化网络的每条边以概率p 重新随机连线，边的一个端点不变，顺时 针方向的端点改连到环上随机选取的一点( 不允许自连接和重边) 通过改变p 的值，可得到介于规则网络( p = 0 ) 和随机网络( p = 1 ) 之间的各 种网络这过程通过重新连接规则网中节点间的连线来增加该网络的无规则性 模拟结果显示这些网络能像规则网络那样有较高的集群系数，又可以像随机网那样 具有短的平均路径长度 在生物系统、社会系统和人造系统中存在大量的小世界网络研究表明小世界 网络显示出能够增强信号的传播速度、提高计算能力和同步能力特别地。传染性 疾病在小世界网络中传播比在规则网中要容易得多 小世界网络虽然同时具有短路径与高集群特征，但是其度分布与p o i s s o n 分布 相近，是轻尾部的因此，在小世界网中也不存在有大量连接边的中枢点 ( 4 ) 无标度网络 随着计算机通讯的发展，网络的研究方法发生了根本性的改变，人们开始有能 力对具有大量点边的大规模图形的统计属性进行研究1 9 9 8 年， b a r a b6s i 和 a l b e r t 等开展了描绘万维网( w 、7 v w ) 的项目时，原以为会发现一个类似e r 模 型的结果，然而现实却推翻了这个预测在这个项目中，他们设计了一个软件，可 从个网页跳转到另一个，尽可能地收集网上的所有连结，这个虚拟机器人组合出 来的图景解释了令人惊异的事实- 基本上，万维网是由少数高连结性的页面串连起 来的8 0 以上页面的连结数不到4 个，然而只占节点总数不到万分之一的极少 数点，却有1 0 0 0 个以上的连结他们把这种特性叫做网络的无标度( s c a l e - f r e e n a t u r e ) 性质网络的无标度特性是复杂网络的一个重大发现，它将人们对现实网 络的认识提高到了一个全新的高度这是新的研究方法带来的突破 1 9 9 9 年，a l b e r t ，j e o n g 和b a r a b6s i 在s c i e n c e 上发表了一篇开创性 的文章 4 1 ，指出w w w 网具有重尾特征的度分布，提出了无标度网络( s c a l e - f r e e n e t w o r k s ) 的概念，并揭示了无标度网络演化背后的关键机制t增长( g r o w t h ) 和择优连接( p r e f e r e n t i a la t t a c h m e n t ) 3 福建师范大学陈鹏辉硕士学位论文 他们认为网络中的点并非固定不变的，网络是个动态的演化系统而且在不 断的增长过程中，存在着择优选择的原则这就是著名的b a 模型通过理论分析 与数值模拟，得出了b a 模型的几点特征- ( 1 ) 具有幂律度分布，是无标度网络；( 2 ) 平均路径短l ( 3 ) 集群系数小；( 4 ) b a 网络中存在中枢点与富者愈富现象，幂律度分布的重尾部特征将导致无标度网络存 在少数具有大量连接边的中枢点，择优连接必然产生富者愈富现象 这些性质和实际网络的许多现象基本一致b a 模型的提出对复杂网络的发展 具有划时代的意义只是b a 模型是可以生成的最简单模型，相对于各种复杂的实 际网络，它有着明显的局限性此后为了刻画更多的现实网络，人们开始不断探索 网络的演化机理，建立符合实际网络的演化模型 本文主要考虑的就是在b a 模型基础上，关于无标度加权网络的模型构造问 题所谓加权网即对网络中的边赋予一定的权重值，而无标度加权网则是具有重尾 部分布的加权网络我们将构造一些网络演化的生成机制，并借助理论分析计算网 络的度分布，权重分布与强度分布第1 章，详细介绍相关的背景知识、研究方法 第2 章到第4 章主要讲述构造模型，并分析计算网络的度分布，权重分布与强度分 布第5 章对本人的科研成果做个总结和展望，包括一些不完善的地方和目前尚 未解决的问题 4 第1 章引言 第1 章引言 近年来，复杂网络引起了国际学术界的广泛关注，正以蓬勃发展的态势成为系 统科学，生物与生命科学统计物理学、计算机科学、数学科学以及社会科学等众 多学科的研究热点 1 1 复杂网络概述 复杂网络就是具有复杂拓扑结构和动力学行为的大规模网络，它是由大量节点 通过边的相互作用连接而成构成的图如：万维网、因特网、引文网，新陈代谢网， 基因网、蛋白质相互作用网、国际机场网、科学家合作网、电力网以及社会网等等 其中节点表示系统的元素，边为元素间的相互作用例如，在社会网络中，节点表 示个人，而边表示人与人之间的社会关系；在万维网中，节点表示各个网页，边表示 网页问的相互关系，如链接关系；在引文网中，节点表示各篇论文，有向边表示论 文对论文的引用而且网络通常还可以分为非加权网络( 二元网络) 与加权网络在 二元网络中，两个节点问有连边只表明这两个节点之间存在相互作用，而在加权网 络中，除了定义节点与连边外，还对每条边赋予权重例如，在社会网络中，边的 权重可以表示人与人之间的认识程度i 在国际机场网中，边的权重可以表示机场与 机场之间的客流量；在科学家合作网中，边的权重可以表示两个作者合作过的文章 数量 为了了解实际网络，人们试图揭示实际网络的拓扑结构特征、网络的演化过程， 特别是发生在网络上的动力学行为为了表征网络的结构特征。人们提出了几个常 用的网络性质的度量标准度分布( d e g r e ed i s t r i b u t i o n ) 、平均路径长度( a v e r a g e p 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 ) 等 度分布p ( k ) 是个重要的统计特征节点的度指与该节点连接的边的数目 网络的度分布p ( 七) 为随机选择个节点的度为七的概率 网络中两个节点的距离为这两个节点间的最短路径，即从个节点到达另外一 个节点所要经过的边的最小数目，所有节点对中最大的距离称为网络的直径，整个 5 福建师范大学陈鹏辉硕士学位论文 网络的平均路径长度就是所有节点对距离的算术平均值 集群系数是刻画网络特性的个重要参数单个节点的集群系数定义为与该节 点连接的另外两个节点也相互连接的概率，整个网络的集群系数为各个节点的集群 系数的算术平均值集群系数显示网络的群聚倾向，衡量了网络的集团化程度 早期研究复杂网络的学者热衷于讨论规则的图形或者e r 随机图模型，取得了 丰富的成果近几十年，随着数据库容量的持续增加以及计算机存储和操作能力的 增强，使得人们对大规模复杂网络的实证研究成为可能人们开始做各种实验观察 网络他们发现现实世界的复杂网络，诸如w w w ，i n t e m e t 等，并不具备规则图或者 e r 模型所描述的那样性质这一发现导致了网络研究方向的个巨大变化 大量的实证研究显示了实际网络的众多共同特征- ( 1 ) 复杂性t 网络具有较大规模，结构复杂，节点之间呈现多样性的相互作用 ( 2 ) 动态性网络是具有动态性，节点间的相互作用不断地发生演化，不断地 增长 ( 3 ) 随机性- 许多网络的演化过程存在随机性，节点与节点之间的相互作用很 难完全确定 ( 4 ) 小世界特性：虽然网络规模大，但是节点与节点间存在短路径，整个网络 的平均路径长度随着网络的增大呈对数增长l 网络的集群系数较大( 特别是社会网 络) ，呈现群聚现象 ( 5 ) 无标度特征- 众多网络的度分布呈现幂律尾部，即p ( 七) 一a 七一幂律分 布是个重尾分布，它与e r 图的度分布( 近似泊松分布) 有本质区别重尾部幂律 度分布使网络表现出特殊的结构特征，例如网络的少数节点具有很大的度，而大 部分的节点只有少数连接边，于是造成网络对随机攻击具有很强的承受性，而对蓄 意攻击却很脆弱 事实上，许多实际网络既不是绝对规则也不是绝对随机的，不是e r 随机图或 者规则图所能完全刻画的为了探索实际网络的客观规律，用更加准确的数学模型 描述网络，人们做了很多的努力复杂网络的研究进入了一个全新的时代，研究工 作相当活跃，成果斐然 6 第l 章引言 当前，复杂网络的主要研究工作集中在以下几个领域。 ( 1 ) 对实际网络的实证研究实际上小世界网络与无标度网络的提出正是源 于研究人员在观测实际网络时的新发现 ( 2 ) 网络生成机制及网络演化模型即通过构造一个生成机制来构建网络演化 模型，观察网络结构的变化情况，模拟真实网络 ( 3 ) 网络的拓扑结构现实网络结构复杂，为了更清楚地认识网络，人们一直 在努力寻找新的表征网络结构特征的统计属性 ( 4 ) 网络功能理解分析网络的结构与功能，研究发生在网络上的动力学行为， 如网络上的同步现象、病毒传播、渗流过程、相变等，以及研究网络的弹性，既研 究网络承受各种攻击的能力 ( 5 ) 数学方法复杂网络的研究还处于初级阶段，至今还没有形成套系统的、 有效的数学方法，只有找到有效的数学工具。复杂网络的研究才能得到更迅速的发 展，得到更深刻的结果 ( 6 ) 复杂网络理论的应用，复杂网络理论的应用领域十分广泛，涉及工程技术、 社会、政治，经济，医学、军事、管理等不同领域，人们研究复杂网络理论的动力 和最终目的正是它的广泛应用 1 2 无标度加权网络 ( 1 ) 无标度网络 近几十年，随着数据库容量的增加和计算机存储、操作能力的增强，人们对大 规模复杂网络的实证研究有了可能也为研究大规模复杂网络的拓扑结构提供了机 会逐渐开展了用图论方法对实际网络的研究此时的研究开始用系统的眼光来看 待这些庞大的数据集合，试图寻找这些在复杂系统演化背后的规律和模式因此， 网络的研究方法发生了根本的改变从对含点数少的小型图以及图中个体点或边的 属性分析转变为对含大量点边的大规模图形的统计属性进行研究 1 9 9 9 年，b a r a b 酗i 和a l b e r t 发现娟雨网页的度分布并不像想象中的呈现 p o s s i o n 分布 4 】，而是具有幂律尾部，即p ( k ) 一a k 一，并且发现w w w 基本上是 7 福建师范大学陈鹏辉硕士学位论文 由少数含有大量超级链接的网页窜连起来的，且大多数的网页的连接都很少他们 把这个特性称为无标度性质网络的无标度特性导致了复杂网络的个重大发现， 这也是新的研究方法带来的突破他们于是定义具有幂律尾部的网络被称为无标 度网络w w w 和i n t e m e t 等许多现实世界的大规模网络都是无标度网络 为了揭示无标度网络的自然规律b a r a b 芭s i 等人创造性地构建了一个演化模 型其中，他们把网络理解成动态的演化系统指出动态的演化过程中的两大关 键机制增长( g r o w t h ) 和择优连接( p r e f e r e n t i da t t a c h m e n t ) 确实如此很多实际网络都是通过不断增加新节点与新连线而增长的开放系 统，而且网络在增加新连线时通常不是完全随机的，往往带有某种偏好例如，在 引文网中，新的文章不断出现，而新文章更可能引用那些已经被大量引用的著名文 章；在万维网中，新网页和新链接时刻在增加，而网页在选择链接时往往偏好那些 比较出名的网站；在国际机场网中，经常出现新机场与新航线，而在开辟新航线的 时候更倾向选择大城市结合增长性与择优连接，b a r a b & i 和a l b e r t 提出了著名 的b a 模型1 4 i5 1 ，算法如下t ( 1 ) 增长t 开始于少量节点( f r 0 个) ，每个时间间隔，增加一个新节点，连接到 m ( m 0 ) 个不同的已有节点上 ( 2 ) 择优连接- 在选择新节点的连接点时，假设新节点连接到旧点i 的概率 依赖( 正比) 于旧点i 的度数乜，即 ( ) 2 彘 ( l 2 1 ) 经过t 时间步后，b a 模型演化成个具有n = 仇o + t 个点和m t 条边的网 络 结合增长性与择优连接，科学家们后来提出了许多可以产生无标度网络的模 型，并对无标度网络的性质及其应用进行了深入的研究 根据b a 模型的演化规则，b a r a b k s i 和a l b e r t 利用平均场方法( m e a n f i e l d a p p r o a c h ) i s l 分析了网络的动力学性质，推导出网络度分布的解析表达式t p ( k ) 2 m 2 k 一，七m ，7 = 3 ( 1 2 2 ) 8 第1 章引言 从而，网络度分布p ( k ) 是幂律分布，其中，y 称为度指数且与参数m 无关 ( 2 ) 无标度加权网络模型 近来，关于加权网络的研究非常活跃加权网络所携带的网络信息要比非加权 网络( 二元网络) 多，在二元网络中两个节点之间是否连接只表明这两个节点问是 否存在相互作用，然而，在加权网络中，边的权重可以刻画节点间相互作用的其他 信息，例如，在社会网络中，边的权重可以表示人与人之间的认识程度；在国际机 场网中，边的权重表示机场与机场之间的客流量；在科学家合作网中，边的权重可 以表示两个作者合作过的文章数量实际网络中节点间的相互作用程度不尽相同， 因此加权网络可以更好地描述实际情形在无标度加权网络中，原来b a 模型中的 按度数择优连接的准则推广成了按强度择优连接，即新点连接旧点的概率与旧点强 度成正比 1 3 - 2 0 l ，这也导致了加权网络的强度分布p 0 ) ，边的权重分布尸( 叫) 以及 度分布p ( k ) 都具有幂律尾部 构建加权网模型的个主要同题是。边的权重是如何产生的，取决于哪些因素? 许多文章在这方面作了不同的假设首先y 0 0 k ，j e o n g 和b a r a b a s i 1 3 1 最早提出了 无标度加权网，它们是在非加权网的基础上，按照节点度之间的关系给边赋予权值 形成加权网后来，a n t a l 和k r a p i v s k y 提出了不一样的模型 1 4 1 他们认为，加权 网络中边的权重是取自某种概率分布的随机变量，即p ( 伽) ( t t j o ) ，结果也都推导 出了网络的强度分布p ( s ) 以及边的权重分布p ( w ) 以及度分布p ( k ) 具有幂律尾 部 实际上，在复杂的世界中，权值的影响因素非常多甚至权值在网络演化过程 中还可能改变，其动态演化过程甚至和网络拓扑演化样复杂如何确定加权网络 的演化行为成为了研究复杂网络的一大课题 1 3 统计特征量及其解析计算方法 ( 1 ) 网络的矩阵表示 网络通常用图来表示，图中的点代表系统中的元素，连接两点的边表示元素之 间的相互作用一般用邻接矩阵w 来表示一个图，在二元网络中，若节点i 与歹 有连接边，则w 的元素w i j = 1 ，否则t 协= 0 加权网络可以用加权邻接矩阵 9 福建师范大学陈鹏辉硕士学位论文 来表示其中w 的元素撕j 等于节点i 与歹之间连线的权重为了简单起见，本 文只考虑无向网络，即w i j = 屿i 的情况 ( 2 ) 度数与强度的概念 网络中节点的度数指与该节点连接的边的数目在加权网络中，节点i 的强 度指的是与该节点连接的边的全体权重之和即s i = 邑p ( t ) ( 其中( ) 表示节 点t 的所有邻居) 节点强度是度数乜的直接推广，是一个重要的数量，它结合了节 点的连线以及这些连线的权重信息例如，在国际机场网中强度s t 表示机场i 的最 大客流量，而在科学家协作网中，强度s 等于作者i 与别人合作过的文章数量为 了表征加权网的结构特征，人们引入了下面几个常用的统计特征量 1 度分布( d e g r e ed i s t r i b u t i o n ) 节点的度为与该节点相连接的边的数目，而网络的度分布p ( k ) 为随机选择一 个节点的度为k 的概率实证研究表明，众多实际网络的度分布具有幂律尾部，即 p ( k ) 一a k - 口( 当七较大时) ，其中q 称为度指数 下面介绍几种度分布的计算方法先来看它的几个定义 定义1 4 1在t 时刻从网络中随机选择一个节点，它的度为k 的概率设为 p ( k ，t ) ，则称 p ( 七，t ) ，k = 0 ，1 ，2 ， 为t 时刻网络的度分布如果存在极限 p ( k ) = j i mp ( k ，t ) 七= 0 ，1 。2 ， ( 1 3 1 ) 则【尸( 七) ，k = 0 ，1 ，2 ，) 为该网络的度分布 2 1 , 2 2 1 在平均场方法i s 中首次使用上