（概率论与数理统计专业论文）具有集团性质的无标度网络建模分析.pdf

福建师范大学硕士学位论文 摘要 复杂网络可以描述自然界和社会中的许多系统，如万维网、因特网、国际机场 网、细胞网、生态网、演员合作网、科学家合作网等等实证研究表明，众多实际网络具 有无标度特性t 网络的度分布p ( k ) 具有幂律尾部，即当k 很大时，p ( k ) 一a k ， 其中a ，口为常数1 5 8 】为了探索实际网络，研究人员已经提出了许多网络演化模型， 以解释实际网络所呈现出来的各种特性 本文主要研究集团网络，提出两个具有集团性质的无标度网络演化模型，并加 以理论分析： ( 1 ) 基于现实世界网络的集团特性，考虑到网络中节点与节点之间，集团与集团 之间的相互作用程度也有强弱之分，以及权重的作用，提出一个依权重择优的加权 集团网络模型并对该网络的性质进行了理论分析，结果表明该网络的强度分布、 权重分布以及度分布都具有幂律尾部 ( 2 ) 基于现实世界的合作网络，如好莱坞演员合作网，科学家合作网等，考虑 到合作网络也具有集团性质，提出一个具有集团性质的合作网络模型并对该网络 的性质进行了理论分析，结果表明该投影网络的度分布具有幂律尾部 关键词：复杂网络，无标度网络，加权网络，集团网络，合作网络，演化模型， 强度分布，权重分布，度分布 福建师范大学硕士学位论文 中文文摘 复杂网络是具有拓扑结构和动力学行为的大规模网络，它可以描述自然界和社 会中的各种系统，如万维网、因特网、国际机场网，科学家合作网、细胞网、食物链网 络、演员合作网络、生态网等等1 9 6 0 年，著名的数学家e r d s s 和r 6 n y i 应用概率 方法建立了随机图论，提出了著名的e r 模型【2 3 】2 3 从此，研究人员开始用数学方法 比较系统地研究复杂网络1 9 9 8 年w a t t s 和s t r o g a t z 提出了单参数的小世界网络 模型( w s 模型) 【4 8 l ：既像规则网络那样具有高度的集群性，又像随机图那样具有短 路径特征小世界网络可以探索规则网络和无序随机图之间生成的各种网络1 9 9 9 年b a r a b d s i 和a l b e r t 提出了著名的以增长和择优连接为基本机制的无标度网络的 b a 模型【1 一此后人们提出了许多可以产生无标度网络的演化模型 2 0 , 2 1 , 3 1 一她3 7 , 删， 并对无标度网络的性质及其应用进行了深入的研究从此，复杂网络研究进入了一 个崭新的时代 s t - s e 在简单规则下自然界可以呈现复杂结构，而在复杂背景下自然界可以遵循简单 定律网络演化模型不仅可以捕捉各种微观机制对网络拓扑结构的影响，而且对了 解更为复杂的发生在网络上的动力学行为有着重要的作用因此，探索复杂网络的 演化机理和模型建立倍受人们的广泛关注m 本文主要研究集团网络，提出两个具有集团性质的无标度网络演化模型 文章具体结构安排如下t 绪论简要介绍复杂网络的研究背景及发展历程 第一章预备知识介绍用来刻画复杂网络性质的一些统计特征量，同时详细介绍 复杂网络的建模方法以及网络性质的解析计算方法，并说明本文的主要工作 第二章基于现实世界网络的集团特性，考虑到网络中节点与节点之间，集团与 集团之间的相互作用程度也有强弱之分，以及权重的作用，本文提出一个依权重择 优的加权集团网络模型并对该网络的性质进行了理论分析，结果表明该网络的强 度分布、权重分布以及度分布都具有幂律尾部 第三章基于现实世界的合作网络，如好莱坞演员网，科学家合作网等，考虑到 合作网络也具有集团性质，提出一个具有集团性质的合作网络并对该网络的性质 进行了理论分析，结果表明该投影网络的度分布具有幂律尾部 最后，对本论文作了总结与展望。 福建师范大学叶苏寒硕士学位论文 a b s t r a c t c o m p l e xn e t w o r k sd e s c r i b eaw i d er a n g eo fs y s t e m si nn a t u r ea n ds o c i e t y s u c ha sw o r l dw i d e 、7 ，e b ，i 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 ，m o v i ea c t o rc o l l a b o r a t i o nn 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 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 e s 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 e 后，w h e r ea ，口a r ec o n s t a n t s s 】r e s e a r c h e r sh a v ep r o p o s e dm a n ye v o l v i n gn e t w o r k m o d e l st 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 sf o u n di nm a n y n a t u r a ln e t w o r k s i nt h i sp a p e r ，w ef o c u s e do nt h en e t w o r k sw i t hc o m m u n i t ys t r u c t u r e ，p r o p o s e d t w oe 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 es c a l e - f r e en e t w o r k sw i t hc o m m u n i t y s t r u c t u r ea n da n a l y z e dt h en e t w o r k sb yt h ec o m b i n e dt h e o r e t i c a la n da n a l y t i c a l a p p r o a c h ： ( 1 ) m a n ys o c i a la n dn a t u r en e t w o r k sc o n s i s to fc o m m u n i t i e s ，a n dt h ew e i g h t e d d y n a m i c a le v o l u t i o n c o n s i d e r e df o rt h ee f f e c to fw e i g h ta n dt h ed i f f e r e n c e so fr e l a - t i o n sf r o mv e r t i c e st ov e r t i c e sa n df r o mc o m m u n i t i e st oc o m m u n i t i e s ，w ep r o p o s e d aw e i g h t e de v o l v i n gn e t w o r kw i t hc o m m u n i t ys t r u c t u r e t h es t r e n g t h ，d e g r e ea n d w e i g h td i s t r i b u t i o n so ft h i sn e t w o r km o d e l sw e r ea n a l y z e db a s e do nt h em e a n - f i e l d m e t h o d t h e o r e t i c a lr e s u l t si n d i c a t e dt h a tt h i sn e t w o r km o d e lh a ds c a l e f r e ep r o p - e r t i e s ( 2 ) ac o l l a b o r a t i o nn e t w o r km o d e lw i t hc o m m u n i t ys t r u c t u r ew a sp r o p o s e d b a s e do nt h ec o l l a b o r a t i o nn e t w o r k si nn a t u r ea n ds o c i e t ys u c ha st h em o v i ea c - t o rc o l l s b o r a t i o nn e t w o r k sa n ds c i e n t i s tc o l l a b o r a t i o nn e t w o r k sc o n s i d e r e df o rt h e o n e sw i t hc o m m u n i t ys t r u c t u r e t h e o r e t i c a la n a l y s i so nt h en e t w o r kp r o d u c e db y t h i sm o d e lw a sc a r r i e do na n dt h er e s u l t ss h o w e dt h a tt h ed e g r e ed i s t r i b u t i o no ft h e p r o j e c t e dn e t w o r kw a ss c a l e - f r e e 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 ，c o r n - m u n i t yn e t w o r k s ，c o l l a b o r a t i o nn e t w o r k s ，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 i 福建师范大学叶苏寒硕士学位论文 福建师范大学硕士学位论文独创性和使用授权 声明尸明 本人( 姓名) 叶苏寒，学号2 q q 鱼q 鳗垦，专业概率论与数理统计 所呈交的论文( 论文题目：具有集团性质的无标度网络建模分析 ) 是本人在导师指导下，独立进行的研究工作及取得的研究成果尽我所 知，除论文中已特别标明引用和致谢的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果对本论文的研究工作做出贡 献的个人或集体，均已在论文中作了明确说明并表示谢意，由此产生的 一切法律结果均由本人承担 本人完全了解福建师范大学有关保留、使用学位论文的规定，即：福 建师范大学有权保留学位论文( 含纸质版和电子版) ，并允许论文被查阅 和借阅；本人授权福建师范大学可以将本学位论文的全部或部分内容采 用影印、缩印或扫描等复制手段保存和汇编本学位论文，并按国家有关 规定，向有关部门或机构( 如国家图书馆、中国科学技术信息研究所等) 送交学位论文( 含纸质版和电子版) ( 保密的论文在解密后应遵守此规定) 擀翥罕- 拶黼鹩 绪论 绪论 近年来，复杂网络引起了国际学术界的广泛重视，已经成为系统科学、生物与 生命科学、统计物理学，计算机科学、数学科学以及社会科学等多个学科的研究热 点众多科学家们致力于探索复杂网络的演化规律、结构功能和动力学行为1 5 9 1 现实世界的许多系统都可以用复杂网络来描述，例如，万维网、因特网、引文 网、新陈代谢网、基因网，蛋白质相互作用网、国际机场网、科学家合作网、电力 网以及社会网等等网络通常用图来表示，图中的节点表示系统元素，边表示元素 间的相互作用，例如，在生命系统巨型遗传网络中，节点表示蛋白质，边表示蛋白 质和蛋白质之间的相互作用；在社会网络中，节点表示个人，而边表示人与人之间 的社会关系；在万维网中，节点表示各个网页，边表示网页间的相互关系，如链接 关系；在引文网中，节点表示各篇论文，有向边表示论文对论文的引用网络通常 可以用非加权网络( 二元网络) 或加权网络来表示在二元网络中，两个节点间有连 边只表明这两个节点之间存在相互作用，而在加权网络中，边的权重可以携带更多 的网络信息，例如，在社会网络中，边的权重可以表示人与人之间的认识程度；在 国际机场网中，边的权重可以表示机场与机场之间的客流量；在科学家合作网中， 边的权重可以表示两个作者合作过的文章数量 为了了解实际网络，人们试图揭示实际网络的拓扑结构特征、网络的演化过程。 特别是发生在网络上的动力学行为为了表征网络的结构特征，人们提出了几个常 用的网络性质的度量标准t 度分布( 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 ( k ) 为随机选择一个节点的度为k 的概率 网络中两个节点的距离为这两个节点间的最短路径，即从个节点到达另外一 个节点所要经过的边的最小数目，所有节点对中最大的距离称为网络的直径，整个 网络的平均路径长度就是所有节点对距离的算术平均值 集群系数是刻画网络特性的一个重要参数单个节点的集群系数定义为与该节 福建师范大学叶苏寒硕士学位论文 点连接的另外两个节点也相互连接的概率，整个网络的集群系数为各个节点的集群 系数的算术平均值集群系数显示网络的群聚倾向，衡量了网络的集团化程度 虽然现实网络形态各异，表征内容不尽相同，但是大量的实证研究发现，许多 实际网络表现出众多共同特征 ( 1 ) 复杂性网络的规模很大，结构复杂，节点之间的相互作用呈现多样性 ( 2 ) 动态性网络是一个动态演化的系统，网络节点间的相互作用不断地发生 演化，不断地增长，呈现动态性 ( 3 ) 随机性：许多网络的演化过程存在随机性，节点与节点之间的相互作用不 是完全确定的 ( 4 ) 小世界特性虽然网络的规模很大，但是节点与节点之间存在短路径，整 个网络的平均路径长度随着网络的大小呈对数增长；网络的集群系数较大( 特别是 社会网络) 。呈现群聚现象 ( 5 ) 无标度特征一众多网络的度分布具有幂律尾部，即p ( k ) 一a k 一幂律分 布是个重尾分布，它与随机图的度分布( 近似泊松分布) 有本质区别重尾部幂律 度分布导致网络呈现非平衡状态，网络表现出特殊的结构特征，例如：网络存在少 数节点具有很大的度，而大部分的节点只有少数连接边，从而造成网络对随机攻击 具有很强的耐受性。而对蓄意攻击却很脆弱，网络呈现复杂的相关性特征 复杂网络的研究经历了几个阶段最初，人们用规则网来刻画实际网络，如二 维平面上的欧几里德网格，显然这与观察到的实际网络不相符合从二十世纪5 0 年 代末到9 0 年代末，e r d s s 和r ，6 n y i 提出的随机图成为人们研究网络的主要工具 直到最近几年，人们发现许多实际网络既不是完全规则也不是完全随机的，它们具 有许多与这两者完全不同的统计特性，由此，先后提出了小世界网络和无标度网络 的概念此后复杂网络的研究进入了一个全新的时代，研究工作相当活跃，成果 丰富 目前，复杂网络的研究工作主要集中在下面几个领域t ( 1 ) 实际网络的实证研究实际上，小世界网络与无标度网络的提出正是源于 研究人员在研究实际网络时的新发现 2 绪论 ( 2 ) 网络生成机制及网络演化模型即通过生成机制构建网络演化模型，观察 网络结构的变化情况，模拟真实网络 ( 3 ) 网络的拓扑结构现实网络结构复杂，为了清楚地认识网络，人们一直在 努力寻找新的表征网络结构特征的统计属性 ( 4 ) 网络功能研究发生在网络上的动力学行为，如网络上的同步现象、病毒传 播、渗流过程、相变等，以及研究网络的弹性，既研究网络承受各种攻击的能力 ( 5 ) 数学方法复杂网络的研究还处于初级阶段，至今还没有形成一套系统的、 有效的数学方法，只有找到有效的数学工具，复杂网络的研究才能得到更迅速的发 展，得到更深刻的结果 ( 6 ) 复杂网络理论的应用，复杂网络理论的应用领域十分广泛，涉及工程技术、 社会、政治、经济、医学、军事、管理等不同领域，人们研究复杂网络理论的动力 和最终目的正是它的广泛应用 本章主要参考文献【5 7 - 5 9 3 福建师范大学叶苏寒硕士学位论文 _ = ：；i = = = = = = j 目目目；目= = = = = = = = = = = = = = = = ；= = = ；= = = = = ；= = = ；= = ；= = = = = = = = = = = = = = = = = = = = = = = = ；= 第1 章预备知识 1 1 网络的统计特征量 网络通常用图来表示，图中的点代表系统中的元素，连接两点的边表示元素之 间的相互作用一般用邻接矩阵w 来表示一个图，在二元网络中，若节点t 与j 有连接边，则w 的元素毗，= 1 ，否则t i 切= 0 类似地，加权网络可以用加权邻接 矩阵彬来表示，其中的元素蚴等于节点i 与j 之间连线的权重为了简单起 见，本文只考虑无向网络，即批，= 叫社的情况网络中节点的度指与该节点连接 的边的数目在加权网络中，节点i 的强度8 i = j ，( ) w o ( 其中| ，( ) 表示节点i 的所有邻居) 是度的直接推广节点的强度是一个重要的数量，它结合了节点的 连线以及这些连线的权重信息例如，在国际机场网中强度8 i 表示机场t 的最大客 流量，而在科学家协作网中，强度8 i 等于作者i 与别人合作过的文章数量为了表 征网络结构特征，人t f 弓l 入了下面几个常用的统计特征量 度分布( d e g r e ed i s t r i b u t i o n ) 度分布是一个重要统计特征一个节点的度表 示与该节点连接的边数度分布则表示节点度的概率分布p ( k ) 它指的是网络上 随机取一点的度数为k 的概率 权重分布( w e i g h td i s t r i b u t i o n ) t 网络中边的权重表示赋予该边的权值具有 不同权重的网络称为加权网络权重分布表示边的权重的概率分布尸) ，它指的 是网络中随机选择一条边的权重为u 的概率 强度分布( s t r e n g t hd i s t r i b u t i o n ) t 一个节点的强度表示该节点连接的所有边 的权重总和强度分布则表示节点强度的概率分布p ( s ) ，它指的是网络上随机取 一节点的强度为8 的概率 无标度网络( s c a l e - f r e en e t w o r k ) t 网络的度分布 p ( 尼) ) 具有幂律尾部： p ( k ) 一k 一， k 1 ，y 1 则称这类网络为无标度网络，其中1 称为度指数 平均路径长度( a v e r a g ep a t hl e n g t h ) 一从节点i 到歹所要经历的边的最小数 4 第1 章预备知识 目称为节点i 到歹的距离岛，则所有点对的距离的平均值 k 耦争 被称为网络的平均路径长度，其中珏为网络的总点数 集群系数( c l u s t e r i n gc o e f f i c i e n t ) ，设网络上节点i 的度数为，则节点i 的 k i 个邻点之间可能存在的连接边数为觑( 一1 ) 2 ，如果这个邻点之间实际存在 的边数为最，那么它们的比值 g = 鼎 被称为节点t 的集群系数因此，网络上所有节点的集群系数的平均值 c = 磊1 g n ， 被称为网络的集群系数，其中n 为该网络的总点数 除了上述几个重要的刻画网络性质的统计特征量外。人们也引入了其它的网络 特征度量，如介数及其分布、最大连通分支的规模分布、度相关性、模块性等，这 里不作详细介绍，具体内容详见相关参考文献【4 ，8 ，2 4 ，3 9 ，4 1 ，4 4 】 1 2 复杂网络演化模型的研究概况 实际网络结构复杂，节点间相互作用的情况呈现多样性，为了了解网络是如何 演化成人们所观察到的形态，学者们先后提出了各种网络演化模型，以期更好地再 现实际网络下面对复杂网络演化模型的研究进行简要介绍 1 - 2 1 规则网络 在很长一段时间里，人们认为真实系统各因素之间的关系可以用一些规则网络 表示，如一维链、二维平面上的欧几里德格网等用的最多的规则网络是由n 个 节点组成的环状网络，网络中每个节点只与它最近的k 个节点连接在这样的规 则网络中。每个节点的度、集群系数等网络性质都一样，节点的度分布为6 函数， 即p ( 七) = 6 ( 惫一k ) ；节点簇系数为c = 笔篆等 为网格维数) ，聚集程度较高 5 福建师范大学叶苏寒硕士学位论文 一维规则网络的平均路径长度l 较大，与节点数成线性比例关系，即l 一豢很 显然，用规则网络刻画复杂的现实网络在很多情况下都是不合理的 1 2 2 随机网络 二十世纪5 0 年代末，匈牙利数学家e r d s s 和r 6 n 妒提出了随机图的概念( 捌， 此后近四十年里，随机图成为人们研究网络的主要工具，他们提出的随机图模型常 称为e r 模型e r 模型定义为t 网络有个节点，从最多可能的n ( n 一1 ) 2 条边 中随机选择n 条边构成网络，从而，有n 个节点和n 条边的网络总共有( n - 1 ) 2 个，构成一个概率空间，每个图出现的概率都一样这种图常记为g ( n ，n ) e r 模型的另一种定义是二项式模型s 给定个节点，每一对节点之间以概 率p 相互连接因此，总边数n 是一个随机变量，期望值为e ( 亿) = p n ( n 一1 ) 2 设g o 是一个有个节点n 条边的图，按上述图的生成过程，获得g o 的概率为t p ( g o ) = p n ( 1 一p ) ( n - 1 ) 2 这种图常记为g ( n ，p ) 若仃= p n ( n 一1 ) 2 ，这两个 图g ( n ，n ) 和g ( n ，p ) 等价，生成的网络的性质类似人们往往根据实际情况，交 替使用这两种模型 下面简要介绍与复杂网络有直接关系的e r 随机图的三个统计特征量t ( 1 ) 度分布：根据随机图演化过程，每个节点与其它节点的连接都是等概率的 因此，随机图的度分布p ( k ) 服从二项分布b ( n 一1 ，p ) ，即 p ( k ) = 一1 p 七( 1 一p ) 。1 。知 对于大的情形，它可以被近似为p o i s s o n 分布。 聊) 竺譬e 邶) 其中平均度( k ) = p ( n 一1 ) 型n p p o i s s o n 分布对于大k 衰减很快，其尾部比指数尾部收敛更快，所以随机图的 度分布是轻尾分布p o i s s o n 分布在k - - - - - 处有一个显著的峰值，导致所有节 点所连接的边数都接近于平均度 因此，随机图是相当均匀的 ( 2 ) 平均路径长度t 随机图的平均路径长度有如下估计式t ln(n)lr a n d ”可丽 6 第1 章预备知识 所以，相对于图的规模，随机图的平均路径长度是很小的，呈对数增长 ( 3 ) 集群系数t 考察随机图中的一个节点和它的邻点，任意两个邻点之间存在 连接的概率总是连接概率p 因此，随机图的集群系数为 c ，a d = p 型等 显然，g 叽d 随无限增大而趋于零，表明随机图不能反映现实网络的集群特性 1 2 3 小世界网络 1 9 6 7 年，美国社会心理学家m i l g r a m 通过”小世界试验”，提出了 六度分推 断”，即世界上任意两人之间的平均距离为6 正如m i l g r a m 所说，地球变得越来 越小。变成个地球村，也就是说，变成个小世界1 9 9 8 年，w a t t s 和s t r o g a t z 在n a t u r e 上发表了开创性文章，提出了小世界网络的概念和模型( w s 模型 ) 【勰1 模型演化算法如下t ( 1 ) 从规则网络开始：以具有个节点的环形网络开始，其中每个节点都与它 初始的k 个最邻近的节点相连接( 在每一边有k 2 个邻点) 为了获得一个稀疏 但连通的网络，要求k l n ( n ) 1 ( 2 ) 随机化；以概率p 为网格的每条边重新随机布线，边的一个端点不变，顺 时针方向的端点随机改到环上的任意一点，不允许自连接和重复边 随着随机改线概率p 的变化，w s 模型可以在规则网络= o ) 和无序随机图 = 1 ) 之间生成各种网络，因此我们就能够探索还知之甚少的中间区域( 0 警) - 1 一而m 而 t ，j m 由于度是离散的( 以1 为单位) ，则t 时刻网络的度分布表示为： 脚) = 掣= 丽2 m t 两1 令t _ 0 0 ，则网络的度分布为 p ( 局) = 墨恐尸( 后，t ) 2 m 2 七一1 ，k m 。7 = 1 + 云= 3 ， + d 即度分布p ( k ) 服从幂律分布，其中度指数，y 与网络的参数m 无关 ( 2 ) 率方程方法 第1 章预备知识 k r a p i v s k y 等提出了率方程方法i s 3 ( r a t e - e q u a t i o na p p r o a c h ) ，考虑亡时 刻网络中度数为惫的节点个数的平均值m ( 亡) ，建立n k ( t ) 的变化率方程，计算网 络的度分布 对于b a 模型，当一个新节点进入网络时，n k ( t ) 满足如下率方程， 掣= m 坚氅筋掣+ 南一 其中右边第一项对应于度为k - 1 的节点与新节点相连接，其度变成忌，引起d 噍( ) 的 增加；第二项对应于度为尼的节点与新节点相连接，其度变成是+ 1 ，引起i ( t ) 的减 少；第三项对应于度为仇的新节点可能引起帆( 亡) 的增加当k = m 时如，饥= 1 ， 否则以m = 0 ，总度数e 七k n k ( t ) = 2 m r 注意到，帆( t ) t 为时刻网络中出现度为七的节点的频率的平均值设p ( k ，亡) 表示t 时刻网络的度分布，则n k ( t ) t p ( k ，t ) 假设存在极限 聊) = l i r ap ( k 舰华，k m 当充分大时，n k ( t ) t p ( k ) ，代入率方程，得到 2 p ( k ) = ( 七一1 ) p ( k 一1 ) 一k p ( k ) + 2 ( f k ，m ，k m 从而，p ( k ) 满足如下递推关系式t p c 庇，= 兰 一1 ) 二三二+ 1 p ( k ) = 2 m ( m + 1 ) k ( k + 1 ) ( 克+ 2 ) k 仇 与平均场方法得到的度分布相比，数值模拟结果更接近由率方程得到的度分 布，但是当k 很大时，两个分布的值十分接近 ( 3 ) 主方程方法 1 3 福建师范大学叶苏寒硕士学位论文 d o r o g o v t s e v 等提出了主方程方法 2 0 ( m a s t e r - e q u a t i o na p p r o a c h ) ，研究 单个节点在t 时刻度为k 的概率，进而得到网络的度分布 在b a 模型中，设v ( k ，如，t ) 为节点i 在t 时刻度为七的概率，利用概率论中的 全概率公式可以得到如下主方程 脚。+ 1 ) = 等p ( k - i , t i , t ) + ( 1 一龛) p k 玑七m 上述主方程的边界条件为p ( k ，t ，t ) = 以，m 根据定义1 3 3 ，t 时刻网络的度分布为 p ( 七，亡) = 妄p ( t ) ，七m 从而，整个网络的度分布为 p ( k ) = j i mp ( k ，t ) ，七m ， + 而且需要假定 1 i mt ( p ( k ，亡+ 1 ) 一p ( k ，t ) ) = 0 关于上述假定条件，从实际网络的性质来理解，一般是会成立的，但是难以从理论 上给予证明在原文【2 0 】中作者没有注意到这个问题 对主方程两边关于t 求和，可以得到： 2 p ( k ，t + 1 ) + k p ( k ，t ) + 2 t p ( k ，t + 1 ) 一p ( k ，t ) 】= ( k 一1 ) p ( k 一1 ，t ) + 2 以，m ， 令亡一o o ，则有 p ( k ) = 从而，得到网络的度分布 p ( k ) 锚p 2 m + 2 ( k 一1 ) ，k m + 1 2 m ( m + 1 ) 七= m 七( 尼+ 1 ) ( 尼+ 2 ) k 仇 因此，主方程方法与率方程方法所得到的结果相同 1 4 第1 章预备知识 ( 4 ) 马氏链方法 史定华与陈庆华提出了一种计算网络度分布的新方法( 马氏链方法) 【1 6 ，硼 他们首次发现无标度网络与马尔可夫链之间的内在关系对于b a 模型，设( t ) 表示节点t 在t 时刻的度，他们证明了随时间变化的度序列 ( t ) ，t = t ，i + 1 ，) 是个非齐次马氏链，并给出了具有时间相依的一步转移概率矩阵p i + 1 ) ， = 1 ，2 ，根据马氏链理论，由转移概率矩阵只 + 1 ) 给出了网络在t 时刻的度分 布p ( k ，t ) 的矩阵运算表达式由于矩阵p i ( 亡+ 1 ) 具有特殊的结构，利用矩阵运算 性质，他们提出了一种度分布数值计算的新方法，简称马氏链方法具体内容详见 文献【1 6 ，4 t i 本章主要参考文献 5 7 - 5 9 1 4 本文主要工作 复杂网络的研究如火如茶。复杂网络各个方向的研究都取得了丰富的成果，特 别是复杂网络生成机制的研究最为活跃，根据这些生成机制建立的模型称为复杂 网络演化模型许多实际网络具有集团特性，那么具有集团性质的网络是如何形成 的7 其演化机制又是什么? 本文主要针对这些问题提出两个可以生成具有集团性质 的无标度网络模型t ( 1 ) 基于现实世界网络的集团特性，考虑到网络中节点与节点之间，集团与集 团之间的相互作用程度也有强弱之分，以及权重的作用，本文提出一个依权重择优 的加权集团网络模型并对该网络的性质进行了理论分析，结果表明该网络的强度 分布、权重分布以及度分布都具有幂律尾部 ( 2 ) 基于现实世界的合作网络，如好莱坞演员网，科学家合作网等，考虑到合 作网络也具有集团性质，提出一个具有集团性质的合作网络并对该网络的性质进 行了理论分析，结果表明该投影网络的度分布具有幂律尾部 1 5 福建师范大学叶苏寒硕士学位论文 第2 章依强度择优的加权集团网络 2 1 引言 由于加权网络给边赋上了权重，与实际网络更加接近，更能刻画实际网络的特 性以及动态演化 y o o k ，j e o n g 和b a r a b d s i 【删对加权的演化网络理论进行了探 讨它是在无权网络基础上，按照节点度之间的关系给边赋上权值而形成的加权网 络 b a r r a u ta ，b a r t h e l d m ym 和v e s p i g n a n ia 【i i , 1 2 根据国际航空网的统计性 质，提出了著名的b b v 模型，掀起了加权网络的研究热潮然而，以前这些模型 只是描述在非集团网络中由于新节点的加入而引起权重的动态变化，也就是说，只 是体现了节点与节点之间的相互作用，而没考虑到集团网络中集团与集团之间的相 互作用，不能很好的刻画实际网络的性质 本章提出个加权集团网络的演化模型，其演化机制不仅包含新节点与集团内 的旧节点之间的连接，还包含了新节点与其它集团的节点之间的连接分析结果表 明，该模型生成的网络的强度分布，度分布，权重分布都是具有幂律尾部的，即具 有无标度特性 2 2 依强度择优的加权集团网络演化模型 1 初始条件 有两个集团a 和b ，每个集团有m o 个节点，是全连通的，两个集团之间有1 条边，每条边的权重都是1 2 增长 ( 1 ) 每个时间间隔，添加1 个新点，新点随机地属于两个集团中的一个，且与 该集团中的m ( m 刀) 个节点依强度择优连接，不妨设新点掣属于集团a ，则集 团a 中的节点i 与新点t ，连接的择优概率为 1 6 a 土p = s0 第2 章依强度择优的加权集团网络 赋予新边的权重为1 ，同时再赋予该集团叫。个权重，所增加的权重依边的权重择优 分配到该集团的各个边上，择优概率为 舰t 2 蕊7 1 3 8 t 8 , t ea i j e a ( 2 ) 新点p 又以较小的概率p 与另一个集团( 不妨设为b ) 中的节点连接一条 边，这个连接也是依强度择优连接的，即该集团中的i 点与新点z ，连接的择优概率 为 赋予新边的权重为i 同时，两集团之间相互影响的权重增加了叫2 ，增加的权重是 依权重择优分配到新点所属的集团上，择优概率为 舰t 一再u ) s t s , t ea i j a ( 3 ) 重复以上两步这样，经过t 时间步，该模型生成一个具有n = 2 m o + t 个节点的加权集团网络。其中某一集团增加的平均总权重为 = 【扣+ m ) + 三脚m 2 3 解析分析 根据平均场的方法m ，把时间看成是连续的，同时，把s ( t ) 和( t ) 理解为平 均值这样，就可以推导该模型的强度分布，度分布，权重分布由于模型是集团 网，所以不妨只讨论集团a 的网络拓扑结构 2 3 1 强度分布 定理2 3 1 由该模型生成的网络的强度分布具有幂律尾部，即 邱) 譬s 专l ，口= 两l m + 石1 u 3 1 蕊+ p t 0 2 1 7 b 土p l i 仉p 福建师范大学叶苏寒硕士学位论文 证明：设某节点i 是集团a 的，且该节点在t i 时刻进入网络在t 时刻，节点 的平均强度是s t ( 亡) 考虑节点i 平均强度的变化，每个单位时间，新点根据强度择优连接到网络中 的旧点旧点一旦连接，其强度增加，增加量来自新点与其连接以及集团a ，b 的 权重增加量的分配由此得如下方程： s 卅1 ) _ s 水) = 三仇袁 则有 + 蛳 i j + 丢( 1 一