（信号与信息处理专业论文）复杂网络模型及其动力学特性研究.pdf

摘要 摘要 现实世界中复杂网络无处不在，它们由各种实体以及实体间错综复杂的关系构成，其存 在形式既可以是有形的( 输电网络、交通网络、神经网络) ，也可以是无形的( 万维网、社 交网络、文献引用网络) ，复杂网络研究己渗透到社会、自然和人文等多个不同的领域中， 其目的是要揭示隐藏在各种实体关系中的规律性，并探索复杂网络理论在工程技术领域中的 应用。本文主要研究复杂网络模型及其动力学特性，主要研究内容如下： 第一章简要介绍了复杂网络特性、网络生长模型及一些现实世界中的复杂网络，讨论了 复杂网络的研究现状。 第二章讨论了网络的结构特性，包括网络的小世界效应，度分布，度相关性，网络抗毁 性，网络的层次化模块结构及最近发现的拓扑自相似特性，研究表明复杂网络普遍具有小世 界效应、无标度特性和层次化结构，一些网络还具有自相似特性。 第三章研究了包括随机图模型、小世界网络模型、无标度及其扩展模型、规则网络模型 和分形网络模型等典型网络生长模型，提出现有模型存在的不足。e r 模型、w s 模型和b a 模型是研究复杂网络的基本模型，但它们都不能准确描述现实世界网络，尽管分形网络模型 具有无标度分布和分形特性，但不具有小世界效应，只能通过引入长跳问接产生小世界效应。 第四章在一些社会行为的经验观察基础上，总结了网络生长的内在机制，地理约束优先 连接机制和枝权化去活动机制，并提出了一种拓扑分形网络生长模型，统一了著名的k e 模 型和o h o 模型，分析与实验结果表明：在较宽的控制参数范围内，该网络模型度分布服从 指数和幂律的混合度分布，并具有小世界效应，层次化模块结构，更重要的是具有拓扑分形 特性。在拓扑分形网络模型和特性研究基础上，用网络直径和聚类等方法研究了拓扑分形网 络模型在随机攻击和选择攻击下的抗毁性，分析结果表明拓扑分形网络具有较高的抗毁性。 第五章细致研究了网络的生长机制，发现拓扑分形网络模型类似于薄膜生长中的扩散限 制聚集模型，用统计自相似观点多重分形研究了网络更细致的局部特性，集中于网络工 阶邻居节点的增长，反映网络不同层次的统计自相似特性，拓扑分形网络模型及一些现实世 界网络在不同尺度上具有多重分形特性。 关键词：网络，图论，复杂网络，小世界，无标度，自相似，网络模型，渝渗理论 a b s t r a c t a b s t r a c t c 叩l p l 懿眦l l a _ v ea l t 阻c t e d 姐缸氍勰i n gi n t e r e s ta m o n gp h y s i c i s t so w i n gt ot h e j r r e l e r 锄c et o 咖yr e a l 删d 地相，o r i 蹲s u c h 勰w o r l d 州d ew e b ，t h e 如t 哪b i 0 1 0 画c a la n ds o c 谢 饿怕，o r 虹w o f kj nt b i sa r 撇i n l yf o c 璐嚣o nm es 廿i i c l ：u r a lp r 叩觚e so fc 伽叩l e xn 咖o r k s ， 孕佣，l 量l 地t w o f km o d c l s ，觚dd y 删c a lb e i l a _ “o 硌o f t 、v o r k s ，a n dh a sb e e nm o d v a t e dt oal l i 曲 d e 酽b y 脚l p i r i c a ls n j d i 嚣o f 刚s y s t e i m r 豁e a r c h 髓h a v ei nr e c e my c a r sd e w d o p e da 嘶e t y o f t c 蛳q u 嚣粕dm o d e l st oh e l pu su n d e 塔t a n do r 删c tt l l eb e l l a _ v i o ro f t l 】e s es v s t e 娜w 音f o 吼塔 o ng r o w i n gn e t w o f l 【m o d e la n dd ) 删lb e h a v i o ro f c o m p l e xn e t 州) r k s t h em a i nw o r ko f t l l i s t l m i s i sa s i b n o w s f i r s u y ，w e 机哐血。盯s m d y 谢t l l 出er e a r c hb 虹卿d 锄dd e v e l o p m 朋to f 唧l e x n e t w o r k s ，j n c l u d i n g 吐i es 虮l c n 柏mp r o p l e n i e so fc o n l p l e xn 咖o r k s ，g r o w t l ln e 咖r km o d e l s ，锄d s e v e m lr e a l w o d dc o i n p l c xn e 心讹 s e c o n d l y ，w eh a v er e v i e w e dt h e 唧i r i c a l 咖d i 嚣，触i n go na 删m 6 e ro fs 仨m 嘶c a l p r o p e 而镐o f n e 俺r o r k s 出a th v er e c c i v e dp a m c u l 盯a 删o n i m l u d i n gs n l a n w o r l de 丘如d e g 嘴 d i s 砸b u 矗o n s ，c l l l s t 舐n g ，d e g r e ec o r r e l 撕o n s ，n e t 、v o 血r o b u s 协s ，b i e r a r c t l i c a lm o d u l 撕吼龇d m o 坤r e c e n d yd i s c o v e r e dt o p o l o 百c a ls e l f - s i 王】【l i l a r i 哆t h em o s ti 玎邛o r t 缸to b s e r 训t oc o m co l l t o fs t u d i 郎i s 出a tn e 柏，o r ba mg e r 缸1 yv a yf 打丘n mr a n d o nt h e yh a v c n 坼f h n 妇m 翻 p r o p 硎龆 t h i r d l y i n s p i r e db yt h e s c 曲l s e r v 撕。璐m 粕y 增8 r c h e f sh a v ep r o p c 瞎e dm o d e l so f 饿= t v m 血s t l l a t t y p i c a l l ys c e k t o c x p l a j ne i t h e r h o w n 咖0 r _ k s o 呲t o h a v e t h e o b s e r v c ds 岫l c t i l r c0 f w h a t t b e a 【p 斌e dd o f 山a ts 劬l c t u r ew i l lb c w eb a v e 坞v i e w 酣a n dd i 娜s e d 出e 粤啪n 咖啦 瑚d e l s ，c o v c r i n g 豫n d o mg r a p hn 州e 1 ，t t i es m a l l 娟r o d di 瑚d e l ，s c a l c - 白m o d e la n di 协a 曲即菌o n ， r e g ：l l l 缸玳栅，o r km o d e l s 缸l d 击讹l 饿舶r o r km o d e l s ht h ef o u n hc h a p b 鸥w e 面煳五g a t en 咖o d b 乒他m e c l l a n i 锄o ft b e b r 粕c 1 1 i 】呜 d e a 棚v 删g e o g m p i l i c a la t t a c h m e n tp 耐b f c c 恤t1 啪e d 丘o mc e n a i n 唧试c a le v i d 即c eo f s o c 试b c i l a v 主。璐w bp r e s e n tam i l p l em o d e lo f 叫州。画c a l 丘t a l 矾t w o r k 1 1 圮n 耽w o r ky i e l d s 跚幛u w o r l de 丘b c t m i ) 【c dd e 伊d i s 缸b 而o n i l i 豇删c a lm o d u l a r i 劬a n dm o s tj l l 】p o r t a n t t o p o l 晒c a l 丘a c t a ls 蜘l c n 霉j naw i d cm n g eo f d e a c 6 v a 把m t e w bh a v ca l a n a l y z e d 廿l e 删觚d a t 嘶c kt o l 盯a n c eo f 出e 伊西e n tt o p o l o g k a l 丘a c t a l 圳婀y 讲kt h ep i e s tt o p o l o g i c a l 妇t a ln e 哪o r k h 鹪as j g n i f i c a n n yh i g h 阳h 蚓n 船sm 妇碍n d o mf a i l u ”柚d 舢u 增o f t h eh i g i l l yc 0 衄t e dn o d c s f i n a l l y ，t og a j nf h r l h 盯m l d 盯s t a n d i n go fc 伽叩l 懿n e n v 0 f k s ，w ei n v 鹤吐g a t et h em o p 捌c u l 帮l o c a lf e a t i l 瑚o ft h e 地椰饼k s t h ep e 强p e 咖o f t b cs t 撕s t i c a l l f 匆h d l a r i 吼t h c 删j 撕丘a c t a l w e 向c 嘴o nt 量l e 工训盯n c i 舀o o d 口d w i l lo fa 艇怕，o 出a n d 唧l o 坤t t i e s t a d s t i c a ls e l 协i i 玎_ i l a 荫t yo fc o 唧l t w o r l ( s w ed 0 n s n 锄e 也a tt h i s 枷l 碰h c t a l 时c mb e c l d y 曲嘲删i nt o p o l 孵c a l 丘；l c t a l 咖o r k s 缸l d 辨v 酬r e a l 鲫n p l e x 耻t r 础s k e y w o r d s ：n e t w o r k s ，g 印ht b e o r y c 伽叩l e xs y s t e m s ，锄a l l 娟训d ，a l e 一丘，s e l f s i m i l a r i 劬 n 咖o r km o d e l ，p c 托o l 撕t l i e o r y i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：墨 里肇导师签名：堑盘! = 日期：口7 ，务，口 il 第一章绪论 第一章绪论 现实世界中复杂网络无处不在，它们由各种实体以及实体间错综复杂的关系构成，其存 在形式既可以是有形的，例如输电网络、交通网络、神经网络、甚至家用微波炉的电路系统； 也可以是无形的，例如万维网、社交网络、文献引用网络、不同物质间的物理或化学反应网 络。复杂网络的研究已渗透到社会、自然和人文等多个不同的领域中，其目的是要揭示隐藏 在各种实体关系中的规律性。 1 1 研究背景 很多人工的、自然的系统都可以用复杂网络描述，其中节点代表网络中的个体或组织， 边模拟个体之间的相互作用“卅。系统如因特网m ，万维网旧，社会网络m ，食物链网络【8 】， 和生物网络睁1o 】等，都可以用网络图表示。 人们对网络的研究由来已久，图论是最早涉足网络研究的数学理论。图论中网络被称为 图，图是网络的数学表达形式，它由顶点和边构成。图论的起源很早，瑞士数学家e u l 目在 1 7 3 6 年解决了著名的哥尼斯城堡七桥问题，从而使他成为图论和拓扑学的创始人。此后开展 的研究工作大多基于网格等规则网络，直到上世纪五十年代，匈牙利数学家e f d o s 和r y i 创造性的将概率论引入图论并成功地提出了第一个随机图模型一e r 模型”。在过去几十年 中，e r 模型已成为随机图论的研究基础并一直占据着复杂网络研究的主导地位。 近年来，以还原论和整体论相结合为重要特色的复杂性科学的兴起，促使人们开始关注 复杂网络的拓扑结构及其产生机理：诸如因特网等大量新型网络的相继出现使得人们对复杂 网络性质的了解变得越来越迫切；计算机技术的飞速发展为大规模复杂网络的研究提供了有 效的工具，使得人们可以对那些包含上百万乃至于上千万个顶点的网络进行分析，而这在若 干年前还是不可想象的事情；不同领域中反映复杂网络拓扑结构的数据库相继出现为复杂网 络的研究提供了可靠的实验数据，使得研究者能够对不同类型的数据进行分析进而发现复杂 网络所具有的共同特征【】；上述因素加之各学科间的相互融合使得大规模复杂网络的研究得 以快速发展。 通过对现实世界复杂网络的研究，人们逐渐发现它们中的绝大多数并不是完全随机的， 相反在其内部蕴涵着某种有规律的组织原则。在对这种规律性进行探索的过程中，大量研究 成果不断涌现，其中对复杂网络小世界效应和无标度特性的揭示最为重要。自然界很多网络 东南大学硕士学位论文 都是小世界的，具有两大基本特性“。首先，网络的平均最短路径长度工随网络节点数呈 对数增长，二l n ，或更慢，类似于e r d 6 s - r 缸y i ( e r ) 随机网络川，其中表示从一个节 点到达另一个节点所需经过的平均最小边数。其次，网络具有高聚类系数，类似于规则网。 度为t 节点f 的局部聚类系数定义为e = 2 e t ( t 一1 ) ，其中q 是节点f 的砖个邻居之间的 总边数，龟( 岛一1 ) 2 为最大可能的边数。w 挑和s 仃。鲫明小世界特性可以通过一个规则 网络重新连接或增加一些长跳连接而得到( w s 模型) 【，该模型既具有与规则网络类似的 聚类特性又具有与随机网络类似的较小的平均路径长度。但w s 模型顶点的度分布与随机模 型一样服从指数衰减，它们都是同构的，而b m b 矗s i 和a l b e n 研究表明，不依赖于系统及其要 素，网络中一个节点与其它后个节点相互作用的概率p ( 七) 呈幂律衰减，服从p ( | i ) 一七一， 度指数2 ， 3 。这一发现表明网络自组织成一个无标度状态，现有的随机模型不可预测 【“1 ”。受现实世界复杂网络形成机制的启发，b a i ：岫i 等人通过引入生长与优先连接机制成 功地实现了网络顶点度分布的幂律衰减，构造了一个异构的无标度模型( b a 模型) 【“。目 前，e r 模型、w s 模型和b a 模型己成为复杂网络研究的基本模型。 尽管w s 模型和b a 模型都反映了现实世界网络的特性，但每个模型都缺少另一个模型 的特征，而现实世界网络往往同时具有无标度和高聚类特性。r a v 鹄z 等人研究表明这两个 特性是网络层次化组织的结果，可以由局部聚类系数度量，当聚类函数c ( 七) 满足关系式 c ( _ i ) _ j 一9 时，网络具有模块化和层次化拓扑结构“。迄今已提出一系列确定性高聚类 无标度网络模型，如层次化网络模型j 5 t ，伪随机无标度网络和网络树1 ”o 】，a 口o n o n i 觚 网络【2 ”。同时复杂网络的随机进化机制也得到很大研究，特别地，节点老化效应瞄。q 、地 理约束阱刀o ”和有限信息冽等现实世界网络生长的普遍机制引起了研究者很大兴趣。 特别地。最近复杂网络拓扑自相似特性【1 ”的发现提出了网络进化动力学这一根本问题， 尽管以前研究普遍认为分形小世界二分法【”。分形表示网络在尺度变换下具有尺度不变性， 重正化整个网络后盒子数虬和盒子线性大小之间满足尺度关系虬z 口一如，具有有 限的分形维数如“。但是迄今大多数网络模型都不具有分形特性，最近s o n g 等人引入逆重 正化机制提出复杂网络的自相似演化模型，研究表明，网络产生分形结构的最主要原因 是所有尺度上度大的节点之间的强不协调性。在文献中，模型i 生成一个无标度、小世界 网络但不具有分形拓扑结构，而模型产生具有分形拓扑结构的无标度网络，但没有小世界 2 第一章绪论 效应，用非直接方法将模型i 和模型随机结合将生成分形小世界和无标度网络。基于乘性枝 ， 权树，g o h 等人提出一种觑s f 舷。模型同时具有分形尺度和无标度分布，同时也注意到这种分 形树也不是小世界的，只能通过引入一些长跳连接产生小世界效应p ”。 e r 模型、w s 模型和b a 模型是复杂网络研究的基本模型，但它们都不能准确描述现实 世界网络，尽管分形网络模型具有无标度分布和分形特性，但不具有小世界效应，只能通过 引入长跳间接产生小世界效应。因此，复杂网络模型及其动力学特性研究是复杂网络研究的 一个主要方向。 1 2 现实世界中的复杂网络 1 9 9 8 年w 妇和s 们g a 乜关于小世界现象的分析”1 引发了人们对复杂网络研究的新一轮 热潮，不同于过去的是近几年的研究大多是基于对现实世界中复杂网络的分析而展开的，其 目标是探究隐藏在其“无序”现象中的规律性。目前，已得到广泛研究的复杂网络大致可分 为四类：社会网络、信息网络、技术网络和生物网络【2 l 。它们是复杂网络研究的基础，本节 将对其逐一进行分析。 1 2 1 社会网络 社会网络是社会个体或群体以及他们之间各种复杂关系的集合。这里所指的复杂关系可 以是任何能够想象到的社会关系，如人与人之间的朋友关系、血缘关系，公司与公司之间的 贸易关系、物流关系等。在众多学科中，社会学是最早开始对现实世界中的网络进行实质性 量化研究的学科吲，该学科的早期工作包括：m o r e 关于小群体中朋友模式的研究吲；1 9 6 3 年d a v i s 等对美国南部某城市女性社交圈的研究卅；r o e l b l i s b 目g 盱及其同事对2 0 世纪3 0 年代 后期芝加哥工人社会网络的研究0 1 等。 由人与人之间相识关系所构建的相识网络也是社会网络的一种。心理学家m n g r a m 于 1 9 6 7 年对相识网络进行了所谓的“小世界实验”p ”1 ，该实验极大的推动了复杂网络的研究， 该实验试图利用人与人之间的相识关系将信件通过不断转发最终交到目标收件人手中。参与 者在收到信件后可根据自己与目标收件人是否认识而采取两种不同的行动：如果相识就将信 件直接寄给他，否则只能转寄给该参与者本人认识的并且与目标收件人同姓的人。虽然大部 分信件都在实验中丢失了，但仍有2 5 的信件经过转发成功到达目标收件人手中。“小世界 实验”是对相识网中路径长度分布的一次研究。实验指出任意两个美国人通过平均6 个中间 东南大学硕士学位论文 人就可以建立联系。“小世界实验”也是“六度分离( s i ) 【d e 舭so f s e p a r 撕o n ) ”一词的来源， 虽然m i l 哥咖本人并没有直接提出该词。而是在几十年之后由g u a 在文献0 8 1 中首次提出。 对包括相识网络在内的传统社会网络的研究通常都会受到诸如数据规模较小，受参与者 主观因素影响较大以及试验结果精度较低等负面影响【2 】，因此许多学者转而研究那些可以获 得较为可靠数据的现代社会网络。电影演员合作网络是现代社会网络的一个典型例子，该网 络的顶点代表演员，边表示演员间的合作关系h t e r n dm o v i ed a t a b a 提供了自1 9 世纪9 0 年代以来几乎所有电影的详细资料并且还在不断完善之中。w a n s 和s 缸o g a 乜采用该数据库对 电影演员合作网络的性质进行了分析，结果显示该网络的聚类系数是具有相同顶点数和边数 随机网络的l o o 倍并且其顶点度分布服从幂率衰减，因此具有小世界和无标度特征。其他许 多学者也运用该数据库对电影演员合作网络的统计属性进行了深入的研究瞄，捌。 学术合著网络是该类网络的另一个典型例子。该网络中，如果两个作者存在联合发表的 文章，那么他们之间就存在一条边相连“”。b 锄b a s i 等人分别对数学和神经科学类数据库 进行了分析，结果显示它们的顶点度分布均服从幂率衰减。n e 应用l a l a n m 讣r i n t a r c h i v e 、m e d u n e 、s p 也s 以及n c s 也等四个数据库提供的信息对学术合著网络进行了 研究并指出它们均具有较高的聚类系数和较短的特征路径长度i 柏j 。 其它广泛研究的社会网络包括公司主管网络m 、性网络删、商业团体网络删、恐怖 分子网络，音乐家网络旧、摩门教徒网络1 、家庭间的联姻网络【划等。 1 2 2 信息网络 信息网络是另一类较为广泛研究的现实复杂网络。信息网络的顶点可以是各种类型的信 息源，如科学文献、网页和报纸等，边代表同类信息源不同实体间的相互关系。科学文献引 用网络和万维网是研究最为深入的两种信息网络。二者均可以表示为有向图形式，但不同的 是科学文献引用网络中不存在环状结构。 科学文献引用网络由科学文献以及文献间的相互引用关系构成。该网络之所以不存在环 状结构，是因为每篇文献只能引用在其之前发表的相关文献的缘故。六十年代，由于g a r 6 e l d 等人在大规模文献引用数据库建立中的卓越工作，使得人们对文献引用网络的研究得以开 展。p r i c e 在其早期文献”中对文献引用网络进行了初步的研究，并首次指出该网络顶点入 度和出度的分布均遵循幂律衰减。r c n d e r 对i s i 收录的7 8 3 3 3 9 篇文献以及在p h y s i c a l r e v i e w d 上发表的2 4 2 9 6 篇文献分别进行了研究。发现其顶点度分布均服从幂率衰减阁。目前，伴随 4 第一章绪论 着各种引用数据库的相继出现阳，对文献引用网络的研究正在逐步的深入。 万维网由包含各种信息的网页以及网页间的超链接构成5 ”。程序“n e t w kc r a w l ” 被广泛用于获取万维网的结构，该程序会沿着网页间的超链接不断查询新的页面，从而获取 网络的结构信息。自9 0 年代万维网出现以来，对其结构的研究就从未中断过。诸多学者中 a l b e 一5 9 】，e i n b e 瑁【删以及b r o d c 一“1 等人对该网络的研究产生了深远影响。同科学文献引用 网络一样，万维网顶点入度和出度的分布也都遵循幂律衰减。此外，文献【砬删对该网络的其 他性质也进行了探讨。 其它一些信息网络，如美国专利引用网络、点对点网络【”侧、语义词汇网络【”侧等 也得到了不同程度的研究。 1 2 3 技术网络 在众多技术网络中最典型的例子是因特网。它与上述万维网有着密切的关系，但与虚拟 的万维网不同，因特网是一个有形的物理网络，它由大量计算机和通信线路组成。研究中通 常从两个不同的层次对该网络进行定义。一种是将路由器作为顶点，利用不同路由器间的路 由关系来定义边，而另一种则是将自治系统作为顶点，通常个自治系统对应于一个域。 f a l o u 鲫对以上两种定义下的因特网均进行了研究，并且指出无论采用何种定义，其顶点的 度分布都服从幂律衰减f 4 】。另外，b r o i d a 【叫、c h 【7 q 等人也均对因特网的统计学性质进行了 研究。 技术网络的另一个典型例子是电力网( 如图la ) ，它由分布于整个国家或某一地区的高压 输电线路组成。与因特网不同，电力网顶点的度分布服从指数衰减。有关电力网统计学性质 分析的文章很多，例如w 撕s 、s 缸o g a t z 等人的文献p 1 1 和a l m r a l 等人的文献脚】。 其它技术网络还包括：航空网络田】、道路网络嗍、铁路网络【7 3 】、河道网络嗍、电路 网络【明以及大规模计算机软件系统”删等。 1 2 4 生物网络 食物链网络是生物网络的一种，它被按照如下的方式进行定义：网络中的顶点表示不同 的物种，边a b 代表物种a 对物种b 的捕食物关系【踟( 如图l ”。尽管对于食物链网络的重构 是一件非常繁复的事，然而目前已经可以获取几种有效的数据库“。i 。s o l e 和m o 劬) y 通过 对y t h t i i a r y 、s i l w o o dp a r k 和l i 仕l er o c kl a k e 等三个不同地点食物链网络的研究发现其顶 5 东南大学硕士学位论文 点的度分布服从幂律衰减“8 ”。其它对于食物链网络研究还包括c a i l l a c h 0 嗍、d 啦n e 旧、 h a l l 【鼹】以及l u c 吐o v i c h 口9 1 等人的文献。 生物体不同组织的新陈代谢反应可以构成一个较大规模的复杂网络，即代谢网络。该网 络也是生物网络的一种，其顶点表示代谢物质( 如a ：】曙、a d p 、h 2 0 ) ，边代表由不同代谢 物质参与的化学反应。因为大多数物质间的化学反应是不可逆的，因此该网络的边具有方向 性，整个网络被表现为有向图的形式。j e 0 i l g 等人研究了由4 3 种组织构成的新陈代谢网络， 结果表明其顶点的出度和入度分布均服从幂率衰减【9 】。a l b c r t 等人通过对代谢网络的研究也 得到了相同的结果nw g 日和f e n 通过对e h e f i c l l i ac a h 细菌的能量和生物合成代谢网 络的研究发现不仅其度分布服从幕律衰减，而且还具有较大的聚类系数嗍，这说明代谢网络 是一个具有无尺度特性的小世界网络。此外，s t e n i n 矿1 等人对代谢网络的其它统计学性质 也进行了分析。 与新陈代谢网络中的化学反应不同，同样属于生物网络的蛋白质网络则是建立在蛋白质 问的机械物理反应基础上的。该网络的顶点表示蛋白质，边表示两种蛋白质能否结合。对酵 母网络的研究表明其顶点的度分布既不服从指数衰减，也不服从幂率衰减。该网络具有广义 随机图的特征。 其它生物网络还包括神经网络一，血管网络和植物经脉网络【9 ”】、基因调控网络删 等。其中对于生物神经网络的重构工作中最成功的是由w h h 等人完成的对线蠕虫c e l e 驴 神经系统的重构，其中包括多达2 8 2 个神经元f 9 5 】。和s 臼噼在文献旧中对c e l e g a n s 神 经网络进行了分析，结果表明其顶点的度分布并不像大多数现实网络一样服从幂律衰减，但 该网络具有较高的聚类系数。另外，需要指出的是基因调控网络是首先得到大量建模的动态 网络系统之一k m 自h 于1 9 1 6 年首次提出的布尔网络就是基因调控网络的经典模型嗍 a 图1 1 ( a ) 纽约州电力网络， 6 b ( b ) l i t t l er o c kl a k e 食物网络刚 第一章绪论 1 3 本文的主要内容与结构安捧 近几年，复杂网络的研究主要包括以下几个方向：对复杂网络的各种统计学性质进行研 究，例如网络的平均路径长度和顶点度分布等，并在此基础上对各种性质提出有效的测度方 法；对复杂网络进行建模，以帮助理解网络各种性质的实际意义并为理论分析提供平台；根 据网络系统的各种结构特征以及控制单个顶点特征的局部规则对整个网络的行为进行预测 和调控。目前，对于前两个方向的研究已经取得了令人鼓舞的成绩，但网络系统结构对其行 为影响的研究尚处于初期阶段吲，本文集中于网络统一生长机制这一问题，揭示网络的动力 学特性和集体行为的一般来源。复杂网络模型及其动力学特性正是本课题的研究主题。 我们研究现有的复杂网络模型发现，具有幂律度分布的高聚类网络模型或指数度分布的 小世界网络模型都不是自相似的。我们研究了从一些社会行为的经验学习得到地理约束优先 连接机制和枝权化去活动机制，提出了一种拓扑分形网络生长模型，模型具有高聚类系数， 度分布从幂律到指数变化，最短路径长度随网络节点数呈线性到对数增长，特别地，我们发 现在一个宽的控制参数范围内，幂律和指数度分布结合将导致严格的拓扑分形结构。这些结 果在小世界图，无标度网络和拓扑分形网络之间讲理了可靠的联系，并且提出了一种自然的 方法来研究网络动力学行为的一般起源。 为了对复杂网络进一步的理解和认识，我们用统计自相似观点多重分形，研究了网 络更细致的局部特性。多重分形分为规则多重分形和不规则多重分形，这为复杂网络特性研 究和模型构造提供崭新的思路。我们集中于网络阶邻居节点的增长，研究网络不同区域( 层 次) 的统计自相似特性，分析发现，混合度分布拓扑分形网络模型的三阶邻居节点的比例分 布是多重分形的。这种多重分形特性同样可以在一些现实世界网络中清楚地观察到，一些现 实世界网络如万维网，社会网络，蛋白质相互作用网络和新陈代谢网络在不同尺度上具有多 重分形特性。 本文围绕现实世界网络特性，复杂网络模型及其动力学展开分析研究，研究过程中，采 取了理论分析和计算机仿真相结合的手段，在理论和实践方面验证了研究的正确性和可行 性，主要工作包括： 第二章讨论了网络的结构特性，包括网络的小世界效应，度分布，度相关性，网络抗毁 性，网络的层次化模块结构及最近发现的拓扑自相似特性，研究表明复杂网络普遍具有小世 界效应、无标度特性和层次化结构，一些网络还具有自相似特性。 第三章研究了包括随机图模型、小世界网络模型、无标度及其扩展模型、规则网络模型 7 东南大学硕士学位论文 和分形网络模型等典型网络生长模型，提出现有模型存在的不足。e r 模型、w s 模型和b a 模型是研究复杂网络的基本模型，但它们都不能准确描述现实世界网络，尽管分形网络模型 具有无标度分布和分形特性，但不具有小世界效应，只能通过引入长跳间接产生小世界效应。 第四章在一些社会行为的经验观察基础上，总结了网络生长的内在机制，地理约束优先 连接机制和枝权化去活动机制，并提出了一种拓扑分形网络生长模型，统一了著名的k e 模 型和o h o 模型，分析与实验结果表明：在较宽的控制参数范围内，该网络模型度分布服从 指数和幂律的混合度分布，并具有小世界效应，层次化模块结构，更重要的是具有拓扑分形 特性。在拓扑分形网络模型和特性研究基础上，用网络直径和聚类等方法进一步研究了拓扑 分形网络模型在随机攻击和选择攻击下的抗毁性，分析结果表明拓扑分形网络具有较高的抗 毁性。 第五章细致研究了网络的生长机制，发现拓扑分形网络模型类似于薄膜生长中的扩散聚 集限制模型，用统计自相似观点多重分形研究了网络更细致的局部特性，集中于网络 阶邻居节点的增长，反映网络不同层次的统计自相似特性，拓扑分形网络模型及一些现实世 界网络在不同尺度上具有多重分形特性。 第六章为论文工作的总结和展望。 8 第二章现实世界复杂网络特性 第二章现实世界复杂网络特性 现实世界网络的一些共同特性引起了学者很大关注，并且集中于与随机网络不同的特 性。现实世界网络表现出一些共同的结构化特性，包括小世界效应，无标度分布，层次化和 模块化结构和拓扑白相似特性等。本章中，我们将阐明现实世界网络表现出的一些共同特性。 2 1 小世界效应 自然界很多网络是。小世界”的，同时具有以下两个基本特性1 1 “。第一，平均最短路 径长度随网络节点数呈对数增长，f l n ，或更慢，类似于e r d 6 s 一陆y i ( e r ) 随机图。 第二，网络高聚类紧密连接，聚类系数较大，类似于规则网。 2 l 1 平均最短路径长度 1 9 6 0 年心理学家s t a n l e y m i k 妒m 完成著名的。小世界”实验【” ，该实验极大的推动 了复杂网络的研究，该实验试图利用人与人之间的相识关系将信件通过不断转发最终交到目 标收件人手中。参与者在收到信件后可根据自己与目标收件人是否认识而采取两种不同的行 动：如果相识就将信件直接寄给他，否则只能转寄给该参与者本人认识的并且与目标收件人 同姓的人。虽然大部分信件都在实验中丢失了，但仍有2 5 的信件经过转发成功到达目标 收件人手中。而且平均仅仅经过六个人传递，这个实验就是常用概念“六度分离”的由来。 该实验尽管没有构造具体的网络，但阐明了网络的结构。如今小世界效应已被广泛研究，并 且很多不同的网络被证明存在小世界效应。 考虑一个无向网络，我们定义z 为网络中任何一对节点之间的平均最短拓扑距离。 e 2 面吾略雄o + 1 ) 2 留9 ( 2 1 ) 其中秀是节点f 到_ ，的最短拓扑距离。注意到上式中我们包括了节点到它本身的距离为o 。 用广度优先搜索算法，我们给出了不同网络的平均最短路径长度，如表2 1 所示，网络有 以个节点和研条边。 但式( 2 1 ) 存在一个问题，即如果网络中存在多个簇，那么分属于不同簇的两个的顶 点间的最短距离将无穷大。此时对，的计算将失去意义。解决的方法包括将矿定义为网络中 最大簇顶点的集合，或者改为计算厂1 o 东南大学硕士学位论文 11 厂12 丙南；磊。志 ( 一1 ) 台瘩铭nd ( f ，) ( 2 2 ) 依据，网络的小世界效应可以被精确的描述为在顶点平均度不变的条件下，网络平均路径 长度，的增长速度小于或等于其顶点增长速度的对数。 2 1 2 聚类系数 在很多网络中，我们发现如果节点彳与节点口连接并且节点口与节点c 连接，那么4 与c 相互连接的可能性比网络中任取两个节点的大很多。在社会网络中，可以通俗地理解 为“你朋友的朋友很可能还是你的朋友”。而聚类系数c 就是表示节点连接的紧密程度。 节点f 的局部聚类系数e 定义为埘 c 2 志 ( 2 3 ) 其中岛是节点f 的t 个邻居之间的边数，并除以最大可能的值t ( 屯一1 ) 2 。整个网络 的聚类系数c 是所有节点局部聚类系数的平均值。 c = 去；e ( 2 4 ) 表2 1 给出了不同网络的聚类系数c ，一般地，聚类系数比相同节点数和边数的随机图 的聚类系数大很多。在很多现实世界网络中，“你朋友的朋友仍然是你的朋友”的可能性随 着网络增大的极限情况不趋向于o ，因此当万一时，c = d ( 1 ) ；相反，在随机图中， c = d ( ”_ 1 ) 。因此，现实世界网络与随机图的聚类系数值是不同的，这将在3 1 节中进一 步讨论。 2 2 度分布 网络中节点的度为连接到这个节点的边数。我们定义p ( 七) 为度七的节点占整个网络的 比重。也就是说，p ( j j ) 为随机选择一个节点其度为| j 的概率。e r d 6 s 和r 向咖研究随机图 理论，所有边等概率分布，因此在图比较大的情况下，度分布服从二项分布或泊松分布。 表2 1 现实世界网络的一些基本统计。统计特性如下：网络总节点数以；总边数m ；平均度z ；平均最短 1 0 第二章现实世界复杂网络特性 路径长度f ；图的类型，有向或无向图：如果度分布服从幂律分布，度分布指数口( 对于有向网络，入， 出度指数) ，如果不是，则。一”；公式2 给出韵平均聚类系数c ；度相关系数r ；最后一列给出了引用的 参考文献。 嗣络类型 砟，竹z f 口cr文献 社演员网无向 “9 9 1 32 5 5 1 “8 21 1 3 43 鹌2 30 7 8o 2 0 8 【1 2 ，2 3 】 会科学家合作无向 5 2 9 0 92 4 5 3 0 09 2 76 1 9一o 5 60 3 6 3 4 4 - 4 5 】 网公司董事会无向7 6 7 35 5 3 9 21 4 “ 4 6 0一0 船o 2 7 6 【9 8 _ 9 9 】 工万维网 有向 3 2 5 7 2 91 4 9 7 1 3 55 5 51 1 2 72 1 ，2 4o 2 9_ 0 0 6 7【6 ，l 删 程 因特网无向 1 0 6 9 73 1 蜕5 9 83 3 1 2 5 o 3 9 - o 1 8 9 【4 ，l o l 】 网电力网无向 4 9 4 16 5 9 42 6 71 8 9 9 0 吣- o 0 0 3 12 】 生新陈代谢网无向 7 6 5 3 6 晰 9 “2 5 62 2o 6 7- o 2 4 【9 】 物蛋白质作用无向 2 1 1 42 2 4 02 1 26 2 40 0 7 lo 1 5 6 【l o 】 网 食物链网络无向 1 3 55 9 84 4 32 0 5一o 2 3o 2 6 3 嘲 研究一些大的网络数据库如表2 ，l 所描述的演员网，万维网，电力网，图3 1 表示了这 些网络的度分布，表明度分布p ( 七) 随度后呈幂律衰减，服从p ( 七) 一七一，度指数y 通常为 2 ， o ，网络表现出协调混合，而， 0 表示不协调混合，= o 时，网络不具有协调性。 表2 1 给出了不同网络的度相关系数r 值，我们有趣地发现，几乎所有社会网络都表现出协 2 4 网络抗毁性 与网络的度分布、度相关性及结构化特性紧密相关的是网络节点失效下的鲁棒性，这也 是复杂网络研究的一个重要分支。大多数网络其作用依赖于节点的相互连接，也就是节点间 存在的路径。如果一个节点被移走，网络的路径长度将增加，展终节点被相互分离，从而它 们不可能相互通信。 网络节点失效方式有多种，而且不同网络对这种节点失效抗毁性也不一样。例如，我们 1 2 第二章现实世界复杂网络特性 可以从网络中随机移除节点或者有选择性地去除特殊类节点，如度最大的节点。网络的抗毁 性对流行病学的研究很重要，网络节点失效对应于个体对病毒的免疫，疫苗不仅能够使免疫 个体抵抗病毒感染，而且可以阻止病毒传播。研究网络抗毁性可以提出有效的免疫策略从而 改善公共健康。 a 】b e r t 等人研究了不同网络在节点随机失效和选择性攻击情况下的抗毁性”】，测量了 平均路径长度随移除节点的比例的变化，如图2 2 所示口“。由于无标度网络是异构网，网 络在随机攻击下几乎不受影响，而对选择性攻击很脆弱。因为网络服从幂律度分布，网络中 大部分节点的度较低，它们被移除对网络通信影响不大；而随着度大的节点被攻击后网络路 径长度增长很快。随机网络( 指数度分布) 对随机攻击和选择性攻击下表现出相似的鲁棒性， 这取决于网络的同构性，对于指数度分布随机网络，所有节点的连接情况几乎相同，它们等 价地作用于网络直径，因此每个节点的移除都将造成相同程度的毁坏。万维网和因特网的抗 毁性与无标度网络相一致。 ， 图2 2 网络平均路径长度( 直径) d 随移除节点的比例，的变化。( a ) 指数分布的随机网络和无标度网络 的比较，节点数为= 1 0 0 0 0 ，有2 0 0 条边，平均度为( | i ) = 4 。( b ) 因特网在随机和选择性攻击下 网络直径的变化曲线。( c ) 万维网在随机和选择性攻击下网络直径的变化曲线 东南大学硕士学位论文 c o h 等人也定量分析了网络在随机攻击和目标攻击下的抗毁性【】”1 ”。随机攻击下， 网络的阈值为工= 1 一吉，其中蚝= ( 瑶) ) ，( ) 和( 鬈) 分别为网络在初始状态下顶 点度的均值和二阶矩；目标攻击下，网络的阈值为z = p ( 詹) ，相当于在剩余网络中随 机攻撕2 耋器抛然后按蝴黼一。 2 5 层次化模块结构 很多社会和生物网络都存在层次化模块结构，模块内的节点之间相互紧密连接，不同模 块的节点之间稀疏连接，如图2 3 所示。例如，我们可以想象科学引用网络可以划分为不同 组分别代表不同的研究领域，这种现象研究很多。类似的团体结构在万维网中同样存在，新 陈代谢网，神经网络和软件网络中的团体结构反映了网络的功能单元，食物链网的团体结构 反映了生态系统的子系统。 图2 3 具有模块化结构的网络的示意图。在这个网络中存在三个内部节点紧密连接的团体，而团体之间稀 疏连接，整个网络层次化组织 判断网络是否具有层次化模块结构的传统方法是聚类分析法，有时也称为层次化聚类方 法。这一方法表示网络中节点对的连接强度，用聚类系数表示，网络本质的层次化模块结构 可以定量地用节点的聚类系数刻画，度为_ j 的聚类系数c ( 七) 服从尺度关系“嘲 c ( _ i ) 一七， ( 2 7 ) 其中为层次化指数，这种尺度关系量化了节点聚类系数呈层次化分布，一些现实世界网 1 4 豫想 第二章现实世界复杂网络特性 络的局部聚类系数分布都服从尺度关系( 2 7 ) ，表明网络具有层次化拓扑结构，如图2 4 所 示【“。 妒k a 蓉二卜、岛 图2 4 四个大规模网络的聚类系数c ( | i ) 随七的尺度关系。( a ) 演员网络； ( b ) 语义网；( c ) 万维网 ( d ) 自治域的因特网 有关模块化结构的另一个问题是网络中团体结构的检测以及确定节点具体属于哪个模 块。至今也提出了一些解决这一问题的算法，如f 1 a k e 等人提出的最大流量算法“删，n “粕 等人提出的检测团体结构快速算法”，基于特征值方法1