（概率论与数理统计专业论文）复杂网络拓扑特征的理论研究及仿真分析.pdf

摘要 复杂网络能够描述自然和社会中的非常广泛的系统，近年来已成为国际上一 个十分引人瞩目的新兴研究领域本论文主要从概率论、图论和统计物理角度出 发，系统研究了复杂网络的一些重要拓扑特征 本文的主要研究工作如下： 第一章中，介绍了本论文的研究背景、预备知识及本文所作的主要工作 第二章中，从概率论角度出发，讨论了复杂网络稳态度分布的存在性及相关问 题根据复杂网络的定义和性质建立网络马氏链，进而利用马氏链理论中首达概率 的方法和技巧为增长网络稳态度分布的存在性提供严格证明 文中首先分析了一类允许重连的经典模型一一d m s 模型，为该网络稳态度分 布的存在性提供了严格证明另外，文中进一步探讨了一类一般的网络模型一一修 正c o o p e r f r i e z e 模型我们证明了该模型稳态度分布的存在性，并通过数值仿真， 将该模型的度分布及聚集性与b a 模型进行了对比分析 第三章中，主要研究了群体择优模型的一些重要拓扑特征及相应的仿真分析 群体择优模型为复杂网络研究引进了一种新的择优思想一一群体择优思想文中 着重讨论了两类群体择优模型一无权群体择优模型和加权群体择优模璎的拓扑特 征及同步分析 首先，对无权群体择优模型，我们利用率方程方法着重分析了其度分布、度相 关性和聚集性并且在文中我们为该模型提供了广泛的仿真分析，且得出仿真结果 与解析结果完全吻合其次，对加权群体择优模型，我们主要分析了其度分布、点权 及边权分布，研究了群体择优思想在演化过程中对加权网络拓扑结构的影响，并将 其结果与b b v 模型作了比较分析另外，我们还进一步对群体择优模型作了同步 分析，并讨论了网络在随机故障和恶意攻击情形下的同步能力 在文章最后两章中，主要利用复杂网络的研究方法，对社会网络及自然网络作 了一些应用分析 其中在第四章中，我们研究了财富网络模型的拓扑结构及财富分布根据社会 个体和组织之间经济关系的特点，通过考虑财富重分和择优机制等因素对网络结 构的影响，我们建立了对应的财富网络模型文中着重考虑了两类财富网络模型，其 中主要对模型的度分布及其他一些重要拓扑特征作了理论研究和仿真分析 在第五章中，我们研究了一类生物网络模型的拓扑结构及功能通过引进新的 择优思想和演化机制，我们提出了一类新的蛋白质结构域相互作用网络模型同时， 主要研究了该类蛋白质结构域相互作用网络的一些重要拓扑特征，如度分布、聚集 性以及最短路径长度等等 关键词：度分布，度相关性，聚集性，马尔可夫链，幂率分布 a bs t r a c t c o m p l e xn e t w o r kh a sb e c o m eav e r yh o tf i e l do fr e s e a r c hi nr e c e n ty e a r s ，w h i c hc a n d e s c r i b ev e r yb r o a ds y s t e m sb o t hi nn a t u r ea n ds o c i e t y i nt h i sp a p e r ，w es y s t e m a t i c a l l y s t u d yt h et o p o l o g i c a lc h a r a c t e r i s t i co fc o m p l e xn e t w o r k sb yu s i n gm a r k o vc h a i nt h e o r y , k n o w l e d g eo fg r a p ht h e o r ya n ds t a t i s t i c a lp h y s i c s t h ep a p e ri so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w ei n t r o d u c et h er e s e a r c hb a c k g r o u n do ft h i sp a p e r ，s o m eb a s i cc o n - c e p t sa n dt h e o r i e s ，a n do u rm a i nw o r ki nt h i sp a p e r i nc h a p t e r2 ，f r o mt h ep o i n to fp r o b a b i l i t yt h e o r y , w es t u d yt h ee x i s t e n c eo fs t e a d y s t a t ed e g r e ed i s t r i b u t i o no fc o m p l e xn e t w o r k s b a s e do nt h ed e f i n i t i o na n dp r o p e r t i e s o fc o m p l e xn e t w o r k ，w ef i r s tc o n s t r u c tn e t w o r km a r k o vc h a i n t h e nb yu s i n gt h ef i r s t p a s s a g ep r o b a b i l i t yi np r o b a b i l i t yt h e o r y , w ep r o v i d eas t r i c tp r o o ff o rt h ee x i s t e n c e o ft h ed e g r e ed i s t r i b u t i o no fg r o w i n gn e t w o r k s i nt h i sc h a p t e r ，w ef i r s t l yc o n s i d e ra c l a s s i c a lm o d e l ，t h ed m sm o d e l ，a n dp r o v i d eas t r i c tp r o o ff o rt h ee x i s t e n c eo ft h e d e g r e ed i s t r i b u t i o n b c s i d c s ，w ei u r t h c rs t u d yan l o r eg e n e r a lm o d e l ，t h em o d i f i e dc o o p e r - f r i e z em o d e l w ep r o v et h ee x i s t e n c eo ft h ed e g r e ed i s t r i b u t i o n ，ac o m p a r i s o nw i t ht h eb am o d e lo n d e g r e ed i s t r i b u t i o na n dc l u s t e r i n gi sa l s op r o v i d e d i nc h a p t e r3 ，w ed i s c u s ss o m ei m p o r t a n tt o p o l o g i c a lc h a r a c t e r i s t i c so fg r o u pm o d e l s ， a n dt h ec o r r e s p o n d i n gs i m u l a t i o n sa r ea l s op r o v i d e d i nt h eg r o u pm o d e l s ，i ti n t r o d u c e s an e wc o n c e p tt or e a l i z et h ep r e f e r e n t i a la t t a c h m e n ti nt h er e s e a r c ho fc o m p l e xn e t w o r k ， a n di t i sah o l i s t i ca p p r o a c h i nt h i sc h a p t e r ，w ed i s c u s st w ok i n d so fg r o u pm o d e l s ， u n w e i g h t e da n dw e i g h t e d f o rt h ef i r s tk i n do fm o d e l ，w ec o n s i d e rt h et w o - n o d ec o r r e l a t i o na n dt h r e e - n o d e c o r r e l a t i o nb yu s i n gt h er a t ee q u a t i o n a n da l la n a l y t i c a ls o l u t i o n sa r es u c c e s s f u l l y c o n t r a s t e dw i t hc o m p u t e rs i m u l a t i o n s w h a t sm o r e ，w em a i n l yr e s e a r c ht h ed e g r e ed 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 nf o r t h ew e i g h t e dg r o u pm o d e l t h ei n f l u e n c eo fg r o u pp r e f e r e n c em e c h a n i s mo nw e i g h t e d n e t w o r ki sa l s os t u d i e d b e s i d e s ，w es t u d yt h es y n c h r o n i z a t i o np h e n o m e n o nf o rb o t h t h e s et w om o d e l ，a n dd i s c u s st h ei n f l u e n c eo fr a l l d o n lr e m o v a lo fn o d e sa n ds p e c i a l r e m o v a lo ft h em o s th i g h l yc o n n e c t e dn o d e so nt h es y n c h r o n i z a b i l i t yo ft h et w og r o u p m o d e l n 1 c h a p t e r4a n d5a r em a i n l yt h ea p p l i c a t i o no fc o m p l e xn e t w o r k si nr e a ls o c i a la n d n a t u r a ln e t w o r k s i nc h a p t e r4 ，w ec o n s i d e rt h et o p o l o g i c a ls t r u c t u r ei nw e a l t hn e t w o r k w e a l t hi s t h em a i nt a r g e to ft h ee c o n o m i ca c t i v i t i e so fi n d i v i d u a l sa n da g e n t s ，a n di sa l s oo n eo f t h em o s tp o w e r f u lm o t i v e sf o rh u m a nr e l a t i o n s h i pi nas o c i e t y b a s e do nt h ee c o n o m i c r e l a t i o n sb e t w e e nt h ea g e n t sa n do r g a n i z a t i o n s ，w ep r o p o s eag e n e r a lw e a l t hm o d e l ，w h i c h p e r m i t sl o c a lp r e f e r e n t i a la 土t a c h m e n ta n dl o c a lr e d i s t r i b u t i o no fw e a l t h w er e s e a r c h t h ed e g r e ed i s t r i b u t i o na n dw e a l t hd i s t r i b u t i o n ，a n ds i m u l a t i o n sf o rs o m ei m p o r t a n t p r o p e r t i e sa x ea l s op r o v i d e d a n di nc h a p t e r5 ，t h ea n a l y s i so ft h et o p o l o g i c a ls t r u c t u r ea n df u n c t i o nf o rb i o l o g y n e t w o r ki sp r o v i d e d b yi n t r o d u c i n go fn e wi d e a sa n de v o l v i n gm e c h a n i s m ，w ep r o p o s ea n e wk i n do ft h ep r o t e i nd o m a i nn e t w o r k w em a i n l yc o n s i d e rt h et o p o l o g i c a lp r o p e r t i e s o ft h ep r o t e i nd o m a i nn e t w o r k ，s u c ha sd e g r e ed i s t r i b u t i o n ，c l u s t e r i n ga n dt h es h o r t e s t p a t hp r o b l e m k e y w o r d s ：d e g r e ed i s t r i b u t i o n ，d e g r e ec o r r e l a t i o n ，c l u s t e r i n gs p e c t r u m ，m a r k o v c h a i n ，p o w e r l a wd i s t r i b u t i o n 中南大学博上学位论文第一章绪论 第一章绪论 1 1 复杂网络研究概况 我们身处在相互联系、不可避免的网络世界中，无论足那些直接影响我们的， 还足问接影响我们的网络体系 m a r t i nl u t h e rk i n gj r 复杂网络足研究复杂系统的一门新兴学科，近几年受到国内外学者的广泛关 注任何复杂系统都可以从实际背景出发，根据不同的研究角度，抽象成为由相互 作用的个体组成的网络网络遍及自然界、生物系统和人类社会其中深具代表性 并广为人们熟知的网络包括因特网、万维网、电力网、铁路网、公路网、航空网、 蛋白质相互作用网、神经网、人际关系网等等研究这些网络不仅对人们的工作和 生活具有重要的现实意义，而且对了解自然界和生物系统具有深远的科学意义 以复杂网络的角度研究各种复杂系统，将系统作为一个整体，考察系统中个体 问的相互作用模式对系统整体行为的影响这种研究方式打破了过去还原论研究 的局限，从而能够预言系统的各种整体行为以网络的角度研究各种复杂系统足科 学发展的必然趋势 1 1 1 问题产生的背景 万维网( w w w ) 上从一个页面到另一个页面甲均需要点击多少次鼠标? 地球 上任意两个人之间要通过多少朋友才能互相认识? 层出不穷的计算机病毒足如何 在互联网( i n t e r n e t ) 上传播的? 各种传染病( 艾滋病、非典型肺炎等) 是如何在人 类和动物中流行的? 全球或区域性金融危机是如何发生的? 大城市的交通堵塞问 题是如何引起的? 这些问题尽管看上去各不相同，但每一个问题中都涉及很复杂的 网络，包括社会关系网络、经济网络、交通网络等等更为重要的是，越来越多的研 究表明，这些看上去各不相同的网络之问有着许多惊人的相似之处 随着人类认识能力的进一步提高，人们发现自然界、社会生活中、生物系统中 许多大量的复杂系统都可以通过网络的概念加以描述一个典型的网络是由许多 节点( n o d e ) 与连接两个节点之间的边( e d g e ) 组成的，其中节点用来代表真实系统 中不同的个体，而边则用来表示个体间的关系往往两个节点之间具有某种特定的 关系则连一条边，反之则不连边，且有边相连的两个节点被看作足相邻的例如，神 经系统可以看作是由大量神经细胞通过神经纤维相互连接形成的网络；计算机网 中南大学博上学位论文第一章绪论 络可以看作足自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互 连接形成的网络；类似的还有电力网络、社会关系网络、交通网络等等网络的发 展大致经历一下几个阶段： 阶段一；规则图研究 网络足一种由结点和连线组成的几何图形，而几何图形早在欧几里得( e u c l i d ) 时代就足数学研究的重要对象之一但网络作为一门科学，目前公认的看法足应该 从1 8 世纪伟大的数学家欧拉( e i i l e r ) 对著名的“柯尼斯堡( k o n i g s b e r g ) 七桥问题” 的研究 在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下 图所示，a 、b 、c ，d 表示陆地欧拉首先把这个问题简化，他把两座小岛和河的两岸 分别看作四个点，而把七座桥看作这四个点之问的连线那么这个问题就简化成， 能不能用一笔就把这个图形画出来，并且给出了所有能够一笔画出来的图形所应 具有的条件欧拉对七桥问题的抽象和论证思想，开创了数学中的一个分支一一图 论( g r a p ht h e o r y ) 的研究，这也是拓扑学的“先声” c 图1 1 ：哥尼斯堡七桥问题图示 在1 9 世纪和2 0 世纪的前半期，图论中主要研究一些游戏问题，诸如迷宫问题、 博弈问题和棋盘上马的行走路线等等 从1 9 世纪中叶开始图论进入第二个发展阶段，这个时期图论问题大量出现，诸 如由“绕行世界”游戏发展起来的哈密顿问题、关于地图染色的四色问题以及与之 相关联的图的可平面性问题等这个时期也出现了以图为工具去解决其他领域中 一些问题的成果，比如把树的理论应用到化学和电网络分析等直到1 9 3 6 年d 柯 尼希发表了图论的第一本专著有限与无限图理论，这时图论才成为一门独立的 学科，以后图论进入第三个发展阶段由于生产管理、军事、交通运输和计算机网 络等方面提出大量实际问题的需要，特别足许多离散化问题的出现，以及由于大型 高速电子计算机而使许多大规模计算问题求解成为可能 2 中南大学博士学位论文第一章绪论 图论的理论及其应用研究得到飞速发展，尤其足网络理论的建立对网络最早 进行研究的足数学家，其基本理论足图论由于人们认识的局限，经典的图论总是 倾向于用某种规则的拓扑结构模拟真实网络 阶段二；随机图理论 网络的一个重要发展阶段始于2 0 世纪6 0 年代，由两位匈牙利数学家e r d 5 s 和 r 百n y i 建立的随机图理论( r a n d o mg r a p ht h e o r y ) ，被公认为足在数学上开创了复 杂网络理论的系统性研究后来的近半个世纪，随机图一直足科学家研究真实网络 最有力的武器随机网络e r 模型【1 】的描述如下； 给定网络节点总数n ，网络中任意两个节点以概率p 连接，生成的网络全体 记为g ( n ，p ) ，构成一个概率空间由于网络中连接数目足一个随机变数x ，取值 可以从0 到n ( n 一1 ) 2 ，有n 条连线的网络数目为c 碍f 一1 1 2 ，其中一个特定网络 出现的概率为p ( a 。) = p n ( 1 一p ) ( 一1 ) 2 1 一因此，可生成的不同网络的总数为 2 n ( n - 1 ) 2 ，它们服从二项分布，且网络中平均连线数目为p ( 一1 ) 2 e r 模型中节点总数n 足预先给定的，它们足静态的、固定的、平衡的网络，也 有人称之为设计网络同时，e r d f s 和r d n y i 系统性地研究了e r 随机图的性质他 们发现，当一。o 时，e r 随机图的许多重要性质( 如连通性) 都足突然涌现的也 就足说，对于任一给定的概率p ，要么几乎每一个图都具有某个性质，要么几乎每 个图都不具有该性质 阶段三：小世界网络和无标度网络 在2 0 世纪后4 0 年中，随机图理论一直足研究复杂网络结构的基本理论期间， 人们试图揭示社会网络的特征做了一些实验，很著名的有小世界实验( s m a uw o r l d e x p e r i e n c e ) 如2 0 世纪6 0 年代末，t r a v e r s 和m i l g r a m 2 】曾做过的一个所谓“六度 分隔”( s i xd e g r e e so fs e p a r a t i o n ) 实验在m i l g r a m 的实验之后，为检验“六度分隔” 假设的正确性，人们又做了其他一些小世界实验其中一个著名的实验就是“k e v i n b a c o n 游戏”( g a m eo fk e v i nb a c o n ) 当时现有的规则网络模型和随机网络模型 都无法解释这种“小世界效应” 直到最近几年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大 量的真实网络既不是规则网络，也不是随机网络，而足具有与前两者皆不同的统计 特征的网络，这样的一些网络被科学家们叫做复杂网络( c o m p l e xn e t w o r k s ) 在2 0 世纪即将结束之际，对复杂网路的科学探索发生了重要的转变，有两篇开 3 中南大学博士学位论文第一章绪论 鬻囝爨 ( a ) 规则图( b ) 随机图( c ) 小世界图( d ) 无标度图 图1 2 ：几类基本网络图【3 】 创性的文章可以看作是复杂网路研究新纪元开始的标志其一是美国康奈尔( c o r n e l l ) 大学理论和应用力学系的博士生w a t t s 及其导师s t r o g a t z 教授于1 9 9 8 年6 月在n a t u r e 上发表的题为( ( c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s ) ) ( 参见文 献【4 】) 另一篇是美国n o t r ed a m e 大学物理系的b a r a b d s i 教授及其博士生a l b e r t 于1 9 9 9 年1 0 月在s c i e n c e 杂志是发表的题为 e m e r g e n c eo fs c m i n gi nr a n d o m n e t w o r k s ) ) ( 参见【5 】) 这两篇文章分别揭示了复杂网络的小世界特征和无标度特征 性质，并建立了相应的模型以阐述这些性质的产生机理 w a t t s 和s t r o g a t z 提出的小世界网络基本模型，即w s 模型 4 】 描述如下： ( 1 ) 给定规则网：假如我们有一个节点总数为n ，每个节点与它最近邻的k = 2 k 个节点相连线的一维有限规则网，通常要求k 1 ； ( 2 ) 改写旧连线：以概率p 为规则网的每条旧连线重新布线，方法是将连线的一端 随机地放到一个新位置上，但需要排除自身到自身的连线和重复连缘 w a t t s 和s t r o g a t z 在文【4 】中说明了，当p 值较小时，小世界网同时具有大的 群聚系数和短的平均路径，称为小世界现象或效应( e f f e c t ) 他们率先提出的小世 界( s m a l lw o r l d ) 网络模型说明了少量的随机捷径( r a n d o ms h o r t c u t s ) 会改变网络 的拓扑结构，从而涌现出短的路径 a l b e r t ，j e o n g 和b a r a b d s i 【7 通过研究万维网发现，万维网的度分布不像随机 网和小世界网那样有对称的泊松分布，而是偏倚的幂律( p o w e rl a w ) 分布在该网 络中，大多数节点仅有少量连线，而少数节点拥有大量连线，这种节点称为中枢点 ( h u b s ) 在文【8 中，b a r a b d s i ，a l b e r t 和j e o n g 提出了无标度网络模型，其基本模 型是b a 模型，描述如下； ( 1 ) 初始：开始给定礼。个节点； ( 2 ) 增长：在每个时间步重复增加一个新节点和m ( m n o ) 条新连线； ( 3 ) 择优：新节点按照择优概率i i ( k t ) = 选择旧节点i 与之连线，其中是旧 4 中南大学博士学位论文第一章绪论 节点i 的度数 0 岩1t = 2 f = 3t ；4 t、 。 。 譬j n ” 囊 f 25 轧、碧f 。6受v k 7 翻? 芦t = 8 妻i 蛰 黪、 尊7 吒1 x 一。瓤、 喾 禧7 崩 图1 3 ：无标度网络的产生 6 】 他们首次从动态的、增长的观点研究了复杂网络具有幂律度分布的形成机理， 尽管他们并不是第一个发现幂律度分布的作者 图1 3 给出了无标度拓扑结构的简单过程：如图中所示，从三个相互联系的节 点开始，在每个图像中一个新的节点( 空圈) 被添加进网络当决定在何处连接时， 新的节点会倾向在有着更多连边的节点上，这个过程被看作是优先连接由于增长 和优选机制，我们可以观测到一个“富者更富”的过程，这就意味着较之连接较少 的节点，有较多连接的节点更容易获得更多的连接，导致一些高度连接的中心节点 的自然出现节点大小被选择与节点的度成正比，在演化过程中最终导致最大的中 心节点的出现由此产生的网络度分布遵循幂律分布 幂律分布也称为无标度( s c a l e - f r e e ) 分布，具有幂律度分布的网络也称为无标 度网络，这是由于幂律分布函数具有如下无标度性质考虑一个概率分布函数，( z ) ， 如果对任意给定的常数a ，存在常数b 使得函数( x ) 满足如下“无标度条件”； ，( 凹) = b f ( x ) 也就是说，幂律分布函数是唯一满足无标度条件的概率分布函数 接下来，对上述几类基本网络模型的拓扑特征作一个简要总结( 见表格1 ) s 从2 0 世纪末开始，复杂网络研究正渗透到数理学科，生命学科和工程学科等 众多不同的领域，对复杂网络的定量和定性特征的科学理解已成为网络时代科学 研究中一个极其重要的挑战性课题，甚至被称为。网络的新科学( n e ws c i e n c eo f n e t w o r k s ) ”( 见文献 9 ，11 ) 很明显，无论是在自然界还是技术领域，没有哪一个网络系统是完全随机的， 也就是说超越随机性的机制定性了他们的演化从度分布【5 】到度度相关性【1 2 - i s 5 中南大学博士学位沧文第一章绪论 性质 平均路径长度 模型 度分布聚集性 规则网络 占分布 大长 随机网络p o b s o n 分布小 短 小世界网络指数分布 大 短 无标度网络 幂率分布 小 短 表格1 ：几类基本网络模型的拓扑特征比较 和社会团体【i 9 - 2 i ，不同拓扑特征的广泛存在性被作为研究不同现象以及做出预 测的跳板同时，网络系统理论从根本上重塑了我们对于复杂性的认识诚然，虽然 我们对于复杂概率的定义仍然缺乏一致的意见，但足网络在这个领域的作用足十 分明显的：所有的系统都被认为是复杂的，从细胞到因特网，从社会到经济体系，包 含了相当多的通过复杂网络相互影响的成分可以肯定的是，我们早就注意到了这 些网络但是直到最近，我们才开始通过数据和工具来探索他们的拓扑结构，帮助 我们认识到潜在的联系对于系统行为有着重大的影响：除非探讨其网络拓扑，否则 没有办法去理鳃复杂网络 复杂网络的研究工作中最基本的、也足最重要的是对真实网络系统的仔细观 察和实证研究，从中能够促使人们去进一步理解真实网络的形成机制，并捕获它们 的拓扑特征，有共性的，也有个性的 因而，通过一些实际网络的例子将能帮助我们了解复杂网络的理论下面按照 n e w m a n1 2