（信息与通信工程专业论文）复杂网络模型及其结构检测研究.pdf

摘要 摘要 由于复杂网络和许多现实网络有着紧密联系，复杂网络的研究引起了不同学科的广泛重 视和关注。最近的研究结果表明网络中的核心节点受到攻击时，具有分形拓扑结构的网络比 非分形拓扑结构的网络有更强的鲁棒性。因此，研究具有分形拓扑结构的网络生长机制对于 提高网络鲁棒性具有十分重要的意义。 首先，本文回顾了复杂网络的特性、网络生长模型及一些现实世界中的复杂网络，讨论 了复杂网络的研究现状及其研究意义。 其次，本文详细描述了复杂网络的平均最短路径长度，聚类系数，度分布，拓扑自相似 性质等基本特性，重点阐述了三类复杂网络模型，小世界网络模型，无标度网络模型和分形 网络模型。研究表明复杂网络不是随机网，而是具有一些重要特性的网络。虽然e r 模型、 w s 模型和b a 模型是研究复杂网络的基本模型，但它们都不能准确描述现实世界网络。尽 管分形网络模型具有无标度分布和分形特性，但不具有小世界效应，只能通过引入长跳，间 接地产生小世界效应。 接着，我们分别从分形几何和复杂网络两个方面详细介绍了分形生长模型。一方面，我 们介绍了分形几何中的规则和不规则分形，包括如c a n t o r 集、k o c h 曲线、s i e r p i n s k i 图形、 扩散受限聚集模型、反应限制聚集模型和团簇团簇聚集模型；另一方面，我们又介绍了复 杂网络中的确定性和随机分形网络模型，包括s i e r p i n s k i 网络模型、自相似层次化网络模型、 伪分形网络模型、自相似动力学演化模型、i n - s i l i c o 模型和混合度分布模型。同时，我们还 详细讨论了分形维数在分形几何和复杂网络中不同的测定方法。 最后，我们详细介绍了分形几何中扩散受限聚集模型。然后，我们从扩散受限聚集模型 出发，通过研究其生长机制，提出了一种拓扑分形网络生长模型。该模型不仅具有拓扑分形 结构，而且还具有层次化的模块结构，同时聚类系数可调。同时，我们还讨论了拓扑分形网 络的鲁棒性，研究了拓扑分形网络模型在随机攻击和选择性攻击下的抗毁性，实验表明拓扑 分形网络具有较高的抗毁性。 关键字：复杂网络，图论，小世界，无标度，扩散受限聚集模型，拓扑分形，鲁棒性 a b s t r a c t a b s t r a c t d u et ot h ec l o s er e l a t i o n s h i pb e t w e e nc o m p l e xn e t w o r k sa n dm a n yr e a l i s t i cn a t o r k s ，t h e s t u d yo f c o m p l e xn e t w o r k sh a sr e c e n t l ya t t r a c t e dc o n s i d e r a b l ea t t e n t i o ni np h y s i c sa n do t h e rf i e l d s r e c e n t l ys t u d i e so nc o m p l e xn e t w o r k sh a v es h o w nt h a ts e l f - s i m i l a r i t yo fs c a l e - f r e en e t w o r k s m a k es u c hn e t w o r k sm o r er o b u s ta g a i n s tas i n i s t e ra t t a c ko nn o d e sw i t hl a r g ed e g r e e a sc o m p a r e d t ot h ev e r yv u l n e r a b l en o n - f r a c t a ls c a l e f r e en e t w o r k s n 忙r e f o r e i ti sw o r t hs t u d y i n gt h en e t w o r k g r o w t hm e c h a n i s mw i t hf r a c t a lt o p o l o g yt oe n h a n c en e t w o r k sr o b u s m e s s f i r s t l y , w eb e g i no a rs t u d yw i t ht h er e s e a r c hb a c k g r o u n da n dd e v e l o p m e n to fc o m p l e x n e t w o r k s ，i n c l u d i n gt h es t r u e t u r a lp r o p e g i e so fc o m p l e xn e t w o r k s , g r o w t hn e t w o r km o d e l s ，a n d s e v e r a lr e a l - w o r l dc o m p l e xn e t w o r k s s e c o n d l y , w eh a v er e v i e w e dt h ee m p i r i c a ls t u d i e so r ls t a t i s t i cc h a r a c t e r i s t i c so fc o m p l e x n e t w o r k s ，i n c l u d i n ga v e r a g ep a t hl e n g t h ，c l u s t e r i n g , d e g r e ea n di t sd i s t r i b u t i o n , t o p o l o g i c a l s e l f - s i m i l a r i t ya n ds of o r t h a l s o , w eh a v er e v i e w e dt h r e ei m p o r t a n tm o d e l si nc o m p l e xn e t w o r k s , i n c l u d i n gt h es m a l l w o r l dm o d e l , t h es c a l e f r e em o d e la n dt h ef r a c t a ln e t w o r km o d e l s t h e s e s t u d i e ss h o wt h a tn e t w o r k sa g e n e r a l l yv e r yf a rf r o mr a n d o m m e a n w h i l e , s t u d i e si n d i c a t et h a t b a s i cm o d e l s ，s u c ha se rm o d e l 。w sm o d e la n db am e d e l ，c a n n o td e p i c tr e a l - w o r l dn e t w o r k s p r e c i s e l ya n dt h a tt h ef r t a ln e t w o r km o d e lc a l lo n l yp o s s e s ss m a l l w o r l de f f e c tb yi n t r o d u c i n g g l o b a ls h o r t c u t s t h e n , w ef o c u so nt h ef r a e t a lg r o w t hm o d e li nf r a c t a lg e o m e t r i e sa n dc o m p l e xn e t w o r k s r e s p e c t i v e l y o nt h eo n eh a n d , w eh a v er e v i e w e dt h er e g u l a ra n di r r e g u l a rf r a c t a lm o d e l si nf r a c t a l g e o m e t r i e s ，s u c ha sc a n t o ra g g r e g a t i o n , k o c hc a i v e ，s i e r p i n s k ig r a p l l d l a ，r l a ，a n dc c a ；o n t h eo t h e rh a n d w ei n t r o d u c et h ed e t e r m i n i s t i ca n dr a n d o mf r a c t a ln e t w o r km o d e l si nc o m p l e x n e t w o r k , s u c h 舔s i e r p i n s k in e t w o r km o d e l ，f r a c t a lr e c u r s i v es c a l e - f r e en e t s ，p s e u d o f r a c t a l n e t w o r km o d e l ，d y n a m i cs e l f - s i m i l a re v o l v i n gn e t w o r k s ，i n - s i l i c om o d e la n df r a c t a lm o d e lw i t h m i x e dd e g r e ed i s t r i b u t i o n m e a n w h i l e w ei l l u s t r a t ed i f f e r e n tm e t h o d st om e a s u r et h ef r a c t a l d i m e n s i o ni nf r a e t a lg e o m e t r i e sa n dc o m p l e xn e t w o r k sr e s p e c t i v e l y i nt h ee n d ，w eh a v er e v i e w e dt h ed i f f u s i o n - l i m i t e da g g r e g a t i o n ( d l a ) m o d e li nf r a c t a l g e o m e t r i e s t h e n , w ep r o p o s eam o d e lf o rg r o w i n gf r a c t a ln e t w o r kb a s e do nt h em e c h a n i s m s l e a r n e df r o md l am o d e li nf r a c t a lg e o m e t r i e sf r o mt h ev i e w p o i n to f n e t w o r k t h em o d e ls h o w sa m i x e dd e g r e ed i s t r i b u t i o n ( e x p o n e n t i a la n da l g e b r a i c d e g r e ed i s t r i b u t i o n ) a n dt h e f r a c t a l d i m e n s i o na n dc l u s t e r i n gc o e f f i c i e n tc a l lb et u n e dt h r o u g hc h a n g i n gv a l u e so fp a r a m e t e r s a tt h e s a m et i m e ，t h et h e s i sd i s c u s s e st h ew o r ko nd y n a m i c a lb e h a v i o r so fc o m p l e xn e t w o r k s w eh a v e a n a l y z e dt h ee r r o ra n da t t a c kt o l e r a n c eo ft h ep r e s e n tt o p o l o g i c a lf r a c t a ln e t w o r k t h ep r e s e n t t o p o l o g i c a lf r a c t a ln e t w o r kh a sas i g n i f i c a n t l yh i 曲r o b u s t n e s su n d e rr a n d o mf a i l u r ea n df a i l u r eo f t h eh i g h l yc o n n e c t e dn o d e s k e y w o r d s ：c o m p l e xn e t w o r k s ，g r a p ht h e o r y , s m a l l w o r l d ，s c a l e f r e e ，d i f f u s i o n l i m i t e d a g g r e g a t i o n ( d l a ) ，t o p o l o g i c a lf r a c t a l ，r o b u s t n e s s i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：拯磊 日期：丝丝： 衫 研究生签名：擞磊 日期：巡： 硝 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：烂 导师签名：- 型茛扯日 期：皿曩，矿 东南大学硕士论文 第一章绪论 第一章绪论 现实世界中复杂网络无处不在，它们由各种实体以及实体间错综复杂的关系构成，从 i n t e r n e t 到w w w ，从大型电力网络到全球交通网络，从生物体中的大脑到各种新陈代谢网 络，从科研合作网络到各种经济、政治、社会关系网络等，可以说，人们已经生活在一个充 满着各种各样的复杂网络的世界中。复杂网络的研究已渗透到社会、自然和人文等多个不同 的领域中，其目的是要揭示隐藏在各种实体关系中的规律性。 1 1 研究背景 近年来复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络行为之 间的关系。要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一工 具。这种工具在数学上称为图。在任何一个网络都可以看作是由一些节点按某种方式连接在 一起而构成的一个系统。具体网络的抽象图表示，就是用抽象的点表示具体网络中的节点， 并用节点之间的连线来表示具体网络中节点之间的连接关系。 实际网络的图表示方法可以追溯到1 8 世纪伟大的数学家欧拉( e u l e r ) 对“k o n i g s b e r g 七 桥问题，的研究。欧拉对七桥问题的抽象和论证思想，开创了图论的研究。因此，欧拉被公 认为图论之父。在欧拉解决七桥问题之后的相当长一段时间里，图论并未得到足够的发展。 直到1 9 3 6 年才出版了图论的第一部专著，此后图论开始进入发展和突破的快车道。2 0 世纪6 0 年代，匈牙利数学家e r d 6 s 和r n y 孢u 造性的将概率论引入图论并成功地提出了第一个随机图 模型- - e r 模型1 1 】o 在过去几十年中，e r 模型已成为随机图论的研究基础并一直占据着复杂 网络研究的主导地位。 在2 0 世纪即将结束之际，对复杂网络的科学探索发生了重要的转变，复杂网络的研究也 不再局限于数学领域。人们开始考虑节点数量众多，连接结构复杂的实际网络的整体特性， 在从物理学到生物学的众多科学中掀起了研究复杂网络的热潮，甚至于被称为“网络的新科 学，【2 “。 性能不断提升的计算设备和迅猛发展的i n t e m e t ，使得人们开始能够收集和处理规模巨 大且种类不同的实际网络数据；学科之问的相互交叉使得研究人员可以广泛比较各种不同类 型的网络数据，从而揭示复杂网络的共性；以还原论和整体论相结合为重要特色的复杂性科 学的兴起。也促使人们开始从整体上研究网络的结构与性能之间的关系。这些因素促使着复 杂网络在近几年取得了突破性的进展。过去关于实际网络结构的研究常常着眼于包含几十 个，至多几百个节点的网络，而近年关于复杂网络的研究中则常可以见到包含从几万到几百 东南大学硕士论文第一章绪论 万个节点的网络。网络规模尺度上的变化也促使网络分析方法做出相应的改变，甚至于很多 问题的提法都要有相应的改变。就目前而言，复杂网络理论的主要研究内容可以归纳为： 发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法。 建模：建立合适的网络模型帮助人们理解这些统计性质的意义于产生机理。 分析；基于单个节点的特性和整个网络的结构性质分析与预测网络的行为。 控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据 流通等方面。 1 2 研究现状 随着对现实世界复杂网络研究的不断深入，人们逐渐发现它们中的绝大多数并不是完全 随机的，相反在其内部蕴涵着某种有规律的组织原则。在对这种规律性进行探索的过程中， 大量研究成果不断涌现，其中对复杂网络小世界效应和无标度特性的揭示最为重要。自然界 很多网络都是小世界的，具有两大基本特性”1 。首先，网络的平均最短路径长度随网络节 点数呈对数增长，i nn ，或更慢，类似亍 - e r d 6 s r 6 n y i ( e r ) 随机网络【1 1 其中三表示从 一个节点到达另一个节点所需经过的平均最小边数。其次，网络具有类似于规则网络的较大 的聚类系数。度为t 节点f 的局部聚类系数定义为g = 2 q k , c k , 一1 ) ，其中q 是节点f 的毛 个邻居之间的总边数，t ( t 一1 ) 2 为最大可能的边数。w a t t s 和s 仃a 羽坛证明小世界特性可以 通过一个规则网络重新连接或增加一些长跳连接而得到( w s 模型) 4 1 ，该模型既具有与规 则网络类似的聚类特性又具有与随机网络类似的较小的平均路径长度。但w s 模型顶点的度 分布与随机模型一样服从指数衰减，它们都是同构的，而b a r a b b s i 和a l b e r t 研究表明，独立于 系统及其要素，网络中一个节点与其它k 个节点相互作用的概率p ( 七) 呈幂律衰减，服从 p ( k ) k ，其中度指数2 y 存在一个问题，即如果网络中存在多个簇，那么分属于不同簇的两个的顶点间 的最短距离将无穷大。此时对工的计算将失去意义。解决的方法包括将矿定义为网络中最 大簇顶点的集合，或者改为计算f 1 。 7 东南大学颂士论文 第二章复杂网络概述 f 1 ：上yy 二 n ( n 1 ) 台，氙， d ( f ，) 依据厶网络的小世界效应可以被精确的描述为在顶点平均度不变的条件下， 长度的增长速度小于或等于其顶点增长速度的对数。 2 1 2 聚类系数 网络平均路径 在很多网络中，我们发现如果节点a 与节点b 连接并且节点b 与节点c 连接，那么a 与c 相互连接的可能性比网络中任取两个节点的大很多。在社会网络中，可以通俗地理解 为“你朋友的朋友很可能还是你的朋友”。而聚类系数c 就是表示节点连接的紧密程度。 节点f 的局部聚类系数c 定义为【1 3 i = _ i 二l 一 ( 2 3 ) 毛( t - i ) 2 、。 其中岛是节点i 的岛个邻居之间的边数，并除以最大可能的值岛( 毛- 1 ) 2 。整个网络 的聚类系数c 是所有节点局部聚类系数的平均值。 c ：三y c 月 ( 2 4 ) 表1 1 给出了不同网络的聚类系数c 一般地，聚类系数比相同节点数和边数的随机图 的聚类系数大很多。在很多现实世界网络中，“你朋友的朋友仍然是你的朋友”的可能性随着 网络增大的极限情况不趋向于0 ，因此当栉- - o o 时，c = o ( 1 ) ；相反，在随机图中， c = d ( n - 1 ) 。因此，现实世界网络与随机图的聚类系数值是不同的，这将在2 2 节中进一 步讨论。 2 1 3 度分布 网络中节点的度为连接到这个节点的边数。我们定义尸( 的为度女的节点占整个网络的比 重。也就是说，只为随机选择一个节点其度为七的概率p j 。e r d o s 和r 6 n y i 研究随机图理论， 所有边等概率分布，因此，在图比较大的情况下，度分布服从二项分布或泊松分布。 研究一些大的网络数据库如表1 1 所描述的演员网，万维网，电力网，图2 一l 表示了这 些网络的度分布，表明度分布以随度j i 呈幂律衰减，服从p ( k ) a c 七一，度指数，通常为 2 ， 0 ，网络表现出协调混合，而， 0 表示不协调混合，r = 0 时，网络不具有协调性。 表1 1 给出了不同网络的度相关系数，值，我们有趣地发现，几乎所有社会网络都表现出协 调混合，而工程网络和生物网络却表现出不协调混合。 2 2 复杂网络分类 现实世界复杂网络表现出一些共同的结构特性，包括小世界效应，无标度分布，层次化 模块结构和拓扑自相似特性等。基于这些特性，提出了很多网络生长和演化模型，以更好地 理解复杂网络的内在机制。复杂网络模型的研究主要集中于五类模型，分别为随机图模型， 小世界模型，无标度模型，规则网络模型，分形网模型。本节重点介绍其中的小世界网络模 型，无标度网络模型和分形网络模型。 2 2 1 小世界网络 自然界很多网络是“小世界”的，同时具有短的平均最短路径长度和高聚类系数。w a t t s 和s t r o g a t z 证明小世界网络可以通过由一个规则网络重新连接或增加一些长跳连接得到f 4 ) ， 小世界网络研究引起了很大关注，前面提到，规则的最近邻耦合网络具有高聚类特性，但并 不是小世界网络。另一方面，e r 随机图虽然具有小的平均路径长度但却没有高聚类特性 因此，这两类网络模型都不能再现真实网络的一些重要特征。毕竟大部分实际网络既不是完 全规则的，也不是完全随机的。 作为从完全规则网络向完全随机图的过渡，w a t t s 和s t r o g t z 于1 9 9 8 年引入了一个有趣 的小世界网络模型，称为w s 小世界模型。w s 小世界模型的构造方法如下： 1 1从规则图开始：考虑一个含有个节点的最近邻耦合网络，它们围成一个环，其 中每个节点都于它左右相邻的各k 1 2 节点相连，足是偶数。 2 )随机化重连：以概率p 随机地重新连接网络中的每个边，即将边的一个端点保持不 变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至 多只能有一条边，并且每一个节点都不能有边与自身相连。 在上述模型中，p = 0 对应于完全规则网络，p = 1 则对应于完全随机网络，通过调节p 的值就可以控制从完全规则网络到完全随机网络的过渡，如图2 7 。 1 4 东南丈学硕士论文第二章复杂网络概述 r d * & m * 棚 o 桊 图2 - 7 在规则环状格子和随机网络之间随机重新连接过程，不改变网络中节点和边的数目。 由上述算法得到的网络模型的聚类系数c ( 和平均路径长度工p ) 的特性，都可看作重连 概率p 的函数。图2 - 8 显示了网络的聚类系数和平均路径长度随重连概率p 的变化关系( 图 中对两个值作了归一化处理) 。一个完全规则的最近邻耦合网络( 对应于p = o ) 是高聚类的 ( c ( o ) z 3 4 ) 但平均路径长度很大( l ( o ) 2 k 1 ) 。当p 较小时( 0 ：m 脚, ( 2 1 2 ) 由p ( 聊) = 2 ( m + 2 ) 和p ( _ j ) = p ( | i 一o ( k d ( k + 2 ) 得到 p ( ) ：上唑亨 妥 ( 2 1 3 ) k ( k + 1 ) ( t + 2 ) 、 k 较大的情况下，得到幂律度分布p ( 七) 一k - 3 ，与现实世界网络度分布一致。 2 2 3 分形网络 迄今提出的大多数网络模型都不是分形的，直至最近s o n g 等人，通过逆重正化过程提 出复杂网络自相似动力学演化模型口2 1 。在文献【2 2 】的模型i 中，h u b 节点之间直接相连，是 吸引的或强协调的，如图2 - 9 ( b ) 所示，这个模型产生一个无标度小世界网络但不是分形 的；而模型1 1 中，h u b 节点之间相互排斥或不协调，如图2 - 9 ( c ) 所示，该模型将生成一个 具有分形拓扑结构的无标度网络，但不具有小世界效应。他们提出一个两种模型随机组合的 间接方法生长分形小世界和无标度网络，如图2 - 9 ( a ) 所示。 g o h 等人基于乘性分权树提出一种i ns i l i c o 模型”1 ，同时具有分形尺度和无标度分布。 网络模型按如下方式生成：1 ) 以枝权化概率为k 的乘性分支规则生成一棵树；2 ) 分支化 东南人学硕士论文第二章复杂网络概述 过程后，每个节点的度依概率p 增加，并且连接到局部邻居节点；3 ) 对步骤2 中的每次成 功的捷径，依概率q 重新连接到一个随机选择的节点。这类树状网络是分形网，但同时也注 意到这种分形树也不是小世界的，通过引入一些全局捷径将产生小世界效应。 最近，我们从研究社会行为出发，通过提出去活因子，将老化机制和地理优先连接机制 有机的结合在一起，很自然地得到了能够生成具有分形拓扑结构的网络模型。模型通过调节 去活因子的值来调节网络中节点的老化程度，在网络的度分布呈现出一种混合度分布( 指数 与幂率相结合的分布) 的情况下，模型表现出了拓扑自相似性质1 2 4 1 最近，我们从d l a 模型出发，通过将乘性增长的机制、地理优先连接机制和老化机制有 机的结合在一起得到了具有分形拓扑结构的网络模型，同时模型还表现出层次化的结构。i ，州 2 2 4 其它网络 除了上述小世界模型、无标度网络模型和分形网络模型之外，学者们也提出了一些其它 的网络模型来描述现实世界的网络结构。 ( 1 ) 局域世界演化模型 李翔和陈关荣认为优先连接机制不可能在整个网络上都起作用而只会在某个局域世界 里被遵守，通过将局域世界的概念引入b a 模型对其作了推广，提出了所谓的局域世界演化 网络模型册，其度分布介于指数网络和无标度网络的度分布之间。b a 无标度网络模型中的 全局的优先连接机制并不适应于许多现实网络。由于局域世界连接性的存在，每一个节点都 有各自的局域世界，因而也只占有和使用整个网络的局部连接信息。局域世界演化网络模型 就是用来描述这种情形的。模型的构造算法如下： 1 ) 增长：网络初始时有个节点和条边。每次新加入一个节点和附带的m 条边 2 ) 局域世界优先连接机制：随机地从网络已有的节点中选取肘个节点( m m ) ，作为 新加入节点的局域世界。新加入的节点根据优先连接概率 兀( 咖n ( i l w ) 志5 嚣志 亿m 来选择与局域世界中的个节点相连，其中上由新选的m 个节点组成。该模型表明，随 着局域世界的扩大，网络演化越不均匀，越接近于b a 模型，即局域世界的规模决定了网络 演化的非均匀性。 ( 2 ) 确定性网络模型 上述所有网络模型都引入了某种程度的随机性，那么是否一定要有随机性才能展现出小 世界性和无尺度特性呢? b a r a b 矗s i 等人提出了一种具有层次结构的网络模型”，它在确定性 1 7 东南大学硕士论文第二章复杂网络概述 机制下也能表现出无尺度特性。【8 】网络初始化为5 个紧密相连的节点组成的一个小团体，如 图2 - 9 ( a ) 所示；下一步，复制4 个同样的模块，并将每个模块的外围4 个节点与中心节点 相连，得到一个包含2 5 个节点的模块( 图2 - 9 ( b ) ) ；随后，再复杂4 个包含2 5 个节点的 同样的模块，将外围的1 6 个节点和中心节点相连，得到新的包含1 2 5 个节点的新模块( 图 2 - 9 ( c ) ) 。这些复杂和连接的步骤可以无限地重复，得到相应规模的层次化网络。 越 0 0 a , , o , 嬲 o o a - i 辩啦 树_ 吐m 苎 图2 - 9 迭代构造生成一个层次化网络。 层次化网络度为k 的节点的聚类系数a ，七) 满足如下的尺度关系：c ( 七) k 。这一尺度 关系量化了网络是否具有层次化拓扑结构。 ( 3 ) 权重演化网络模型 上述研究均将网络看作无权网，然而现实网络大多数为有权网，即网络节点之间的连接 强度是有区别的。y o o k 等人提出了一种权重演化模型：假定节点权重正比于节点的度数， 也即度数大的节点拥有更大的权数。结果表明，其度分布也符合幂律特征。 1 8 东南大学硕士论文 第三章分形生长模堑 第三章分形生长模型 自从s o n g 等人发现现实世界的复杂网络中存在自相似特性后，网络分形特性的研究引 起了很大关注。本章结合分形几何中的分形生长模型及其分形维数的测量方法，详细阐述复 杂网络中的分形生长模型及其分形维数的测量方法。 3 1 分形几何 古希腊人创立的经典几何学一直是人们认识自然物体的有力工具。宇宙理论，宏伟的建 筑都是建立在这个基础上的。以致伟大的科学家伽利略曾经断言：大自然的语音是数学，“它 的标志是三角形、圆和其他几何图形”。然而自然界存在着大量无法用经典几何方法准确描 述的复杂图形，如自然界中生长着分岔的树枝、变幻的云彩、高低不平的山脉、弯曲的河流， 生活中股市上的股票价格曲线、水文测量中的水位变化曲线、一个地区的气候变化曲线等等。 从整体上看，它们的几何图形是处处不规则的，但在不同的尺度上图形的规则性又是相同的， 也就是从整体到局部的各个层次上都有自相似的结构，在一个花样的内部还有更小的同样的 花样。p s i 几何对象的一个局部放大后与其整体相似，这种性质就叫做自相似性。其部分以某种形 式与整体相似的形状就叫做分形，其原义是“不规则的、分散的、支离破碎的”物体。从字面 上来讲，分形是指一类极其零碎而复杂但具有自相似性( s e l f - s i m i l a r ) 和仿射性( s e l f - a f f i n e ) 的 体系，自相似性和标度不变性是其重要特征。分形几何作为- f l 新兴学科，其本质是一种新 的世界观和方法论，它承认世界的局部可能在定条件过程中，在某一方面( 形态、结构、 信息、功能、时间、能量等) 表现出与整体的相似性。 曼德勃罗曾经为分形下过两个定义： 定义一：满足条件d i m ( a ) = d i m ( a ) 的集合a ，称为分形集。其中，d i m ( a ) 为集合a 的 分维数，d i m ( a ) 为其拓扑维数。一般说来，d i m ( a ) 不是整数，而是分数。 定义二：部分与整体以某种形式相似的形，称为分形。 然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的内容。实 际上，对于什么是分形，到目前为止还不能给出一个确切的定义，正如生物学中对“生命” 也没有严格明确的定义一样，人们通常是列出生命体的一系列特性来加以说明。分形具有五 个基本特性： 1 ) 分形都具有任意小尺度下的比例细节，或者说它具有精细的结构； 2 ) 分形不能用传统的几何语言来描述，它既不是满足某些条件的点的轨迹，也不是某 9 东南大学硕士论文第三章分形生长模型 些简单方程的解集； 3 ) 分形具有某种白相似形式，可能是近似的自相似或者统计的自相似； 4 ) 一般，分形的“分形维数”，严格大于它相应的拓扑维数； 5 ) 在大多数令人感兴趣的情形下，分形由非常简单的方法定义，可能以变换的迭代产 生。 分形特性中，最重要的一个特征是它具有自相似性。所谓自相似性，是指系统的总体和 部分之间，这部分和那部分之间具有的自相似。分形作为一个数学集，它的内部应具有精细 结构，也就是在所有比例尺度上其组成部分应包含整体，而且是相似的。如一块理想海绵， 它有许多小孔，取下- - + 块，它仍有许多小孔，结构与大块的相似。又如我们在冬天里所见 的雪花，仔细观察它的内在结构，它是由自相似的小块构成，其中的小块又由许多自相似的 更小的块构成。这种具有自相似的几何对象和普通微分几何所研究的光滑曲线、曲面不同， 其“曲线，可以是连续却极不光滑的。当然正如天下没有绝对圆的物体一样，圆形只是数学家 对一类物体所作的抽象概况。完全自相似的分形也是一种数学抽象。随着对分形研究的深入 展开，已经对自相似性作了适当的修正和推广，使分形更接近自然界中的各种现实事物。对 于一些数学模型，如康托集、科契雪花曲线( 如图3 1 ( a ) ) 、谢尔宾斯基垫片等，这类自相 似性是严格的，它们称为规则分形；在物理学或其它自然界中存在的分形，它们的自相似是 近似的或者是统计意义的，则称之为无规则分形。例如我们常见的树木( 如图3 l ( b ) ) ， 它的整体与任意折取的一条树枝，在形态上是很相似的，差别只是在于它们的尺寸不同，这 就是无规则分形的实例。 o 厂 ( a ) 科契雪花曲线( b ) 树叶 图3 1 分形的实例图 分形理论真正发展起来才一、二十年，并且方兴未艾，目前仍处于不断发展之中。分形 为探讨自然界的复杂事物的客观规律及其内在联系提供了新的概念和方法，在其发展过程 中，许多传统的科学难题，由于分形的引入而取得显著进展，分形理论的应用发展远远超过 东南大学硕士论文第三章分形生长模型 了理论的发展。分形作为一种新的概念和方法，正在许多领域开展应用探索。美国著名物理 学家惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。 3 1 1 规则分形 规则分形是一种无限多层次自相似的、支离破碎的、奇异的图形，下面举一维至三维的 几个例子。p 9 】 c a n t o r 集：三等分一直线，挖去中段，再把剩下的二段各三等分挖去中段，如此无限 的进行下去得到由无穷多离散的点组成的c a n t o r 集，如图3 - 2 ( a ) 所示。 k o c h 曲线：挖去直线1 3 中段后，加上等边三角形的二边，形成四段等长线段组成的 折线，如此无限进行下去，形成处处连续、但处处不可微的k o c h 曲线，如图3 - 2 ( b ) 所示。 s i e r p i n s k l 图形：正三角形四等分成四个小三角形，挖去中间的一个，把剩下的三个小 三角形四等分挖去中间的一个，如此无限的进行下去，得到面积趋于零、由无穷多线段组成 的s i e r p i n s k i 三角毯，如图3 - 2 ( c ) 所示。 s i e r p i n s l d - m e n g e r 海绵：立方体2 7 等分( 三个方向均三等分) 成2 7 个小立方体，挖 去1 个体心和6 个面心位置上的小立方体，留下2 0 个小立方体，如此无限进行下去，得到 和s i e r p i n s k i 图形密切有关的s i e r p i n s k i m e n g e r 海绵，如图3 - 2 ( d ) 所示 毛 e i e 马 e ( a ) c a n t o r 集 ( c ) s i e r p i n s k i 地毯 引陂一 。 弱k 钆凡n ( b ) k o c h 曲线 图3 - 2 规则分形图形 ( d ) m e n g e r 海绵 3 1 2 不规则分形 自然界的许多事物所具有的不光滑性和复杂性往往是随机的，如蜿蜒曲折的海岸线；变 换无穷的布朗运动等。这类曲线的自相似性是近似的或统计意义上的，这种自相似性只存在 2 l 东南大学硕士论文 第三章分形生长模型 于标度不变区域，超出标度不变区域，自相似性不复存在。这类曲线被称为不规则分形。它 们既可以是单个粒子随时间而不断聚集形成分形结构，也可以是小的团簇从各个生长中心不 断向外发展或转变，从而形成分形图形的过程。 这里最著名的过程是扩散限制聚集( d i f f u s i o nl i m i t e d a g g r e g a t i o n ，d l a ) 模型和团熊 团簇聚集( c l u s t e r - c l u s t e r a g g r e g a t i o n ，c c a ) 模型。前者受拉普拉斯方程( 自变量是浓度) 的控制，后来发现一系列受拉普拉斯方程控制的其他过程( 自变量是电势、压强等) 也可以 形成分形，因此它们被统称为拉普拉斯分形。这类拉普拉斯分形在自然界和实验中已大量地 存在着，例如液体表面上的电解沉积、不同粘度流体间的流动( 粘滞指凸) 、气体放电、雪 花形成和细菌群落的生长等。随着扫描隧道显微术( s t m ) 的发展，低温下超薄膜生长过程 也被显示出是一种属于d l a 类型的分形生长。 3 9 4 0 1 d l a 模型；在二维正方格子的中心放上一个粒子作为核心，再在远处随机产生一个粒 子并让它作为随机的扩散运动，一旦它进到核心的最近邻位置就停下成为两个粒子组成的核 心。此后在远处不断产生新的粒子重复上述过程，直到成千上万个粒子聚集成图3 - 3 ( a ) 那样 的图形。 ( a ) d l a 生长图形( b ) r l a 生长图形 图3 - 3 不规则分形图形 r l a 模型：在d l a 模型的基础上，假设在粘接概率很小的极端情形，扩散粒子一个一 个产生的假设不再成立，团簇周围会有很多粒子在扩散，团簇的长大主要由粘接过程控制。 控制生长的粘接过程属于反应过程，即粘接的最近邻原子间要建立化学键。这就是说，在粘 接或反应过程进行得很慢时，扩散限制聚集过程将转化为反应限制聚集( r e a c t i o nl i m i t e d a g g r e g a t i o n ，r l a ) 过程。反应限制聚集时粘接粒子的位置不再限制于团簇的生长尖端，而 常是团簇的内凹处，因此团簇的形状是密集的，但表面是粗糙的，生长出的图形如图3 - 3 ( b ) 。 c c a 模型：以大气中尘埃的聚集或胶体粒子的聚集为背景，m e a k i n 和k o l b 等分别提 东南大学硕士论文 第三章分形生长模型 出了c c a 模型。将一定数目的粒子( 单体) 随机地分布在二维( 或三维) 格点位置上，让 这些粒子都处于随机行走( 布朗运动) 状态：当相邻的格点被随机行走的粒子占据后，这些 粒子粘接( 聚集) 形成一个团簇，然后该团簇作为一个单位再以与其本身大小相应的方式随 机运动；随着时间的延长，团簇的数目减少而平均尺寸不断增大，当达到某一尺度时，停止 随机运动：最终得到的聚集体是一种开放的、结构松散的、没有明显中心的分形结构( 如图 3 - 4 所示) 。 3 1 3 分形维数的测定 图3 - 4 c c a 过程示意图 测定分形维数的方法很多，如使用圆规测定粗糙曲线分维，从周长面积关系或表面积 体积关系求分维，盒计数法，s d b o x 法，面积回转半径法，变换法，密度密度相关函数 法等等，这里主要介绍盒计数法。1 3 9 4 0 钐殇钐 钐殇荔 彩 钐彩彩钐 钐钐 图3 - 5 盒计数法 这种方法的示意图如图3 - 5 所示。将尺寸分别为s = “4 和1 8 的网格覆盖在分形图形 上，计数网格中有图形象素( 不管有许多象素还是很少象素) 的方格数目，例如得到 n ( 1 4 ) = 1 6 和n ( 1 8 ) = 6 0 ( 增大不到4 倍) 不断减小网格尺寸s 继续计数含图形象素 东南大学硕士论文第三章分形生长模型 的网格数( s ) ，直至最小的网格尺寸达到象素为止。为了减少误差，应该使不同尺寸的网 格能覆盖相同大小的图形，如5 1 2 x 5 1 2 象素的图形的s 应当是l ，i 2 ，1 4 ，1 1 8 ，1 1 6 ， 直到降到1 1 5 1 2 ，而3 6 0 x 3 6 0 象素的图形的s 应当是l ，1 2 ，i 3 ，1 4 ，1 1 5 ，i 6 ，1 8 ， 直到降到1 3 6 0 。将一系列( 占) 、占数据作i n n ( g ) l n ( 1 占) 图，如能得到一条直线，它 说明( 占) 和g 有如下关系： ( s ) ( 咖) 。 ( 3 1 ) 即直线的斜率d