（系统理论专业论文）分形理论在复杂网络研究中的应用.pdf

摘要 复杂网络理论被广泛研究，归结于它与现实中许多真实系统之间密切的关系。 现实世界中，这些复杂系统，都可以用复杂网络来表示，如因特网、社会网、新陈 代谢网、演员合作网等等，即用复杂网络中的节点来代表这些系统的个体，用边来 表示个体之间的相互联系。许多研究表明，尽管拓扑结构各不相同，大量的真实网 络，却表示出相同的三大特征：无标度特征、小世界特征和分形特征。这些特征引 起了研究者们极大的兴趣和广泛的注意。 本文运用m a t l a b 仿真方法，在经典b a 无标度网络模型基础上，建立了一类具有 老化机制和分形特征的无标度复杂网络演化模型； 运用分形理论中的盒计数法和重正化群方法，探讨对复杂网络三大特征的产生 机理和它们之间相互关系的内在机制，刻画出复杂网络整体的特征； 运用迭代法，在阿波罗网络和谢尔宾斯基垫片的基础上，生成了一类具有分形 特征和小世界特征的拓扑复杂网络结构，并用数学解析的方法，计算了拓扑复杂网 络结构的集聚系数，平均最短路径和网络图的直径，证明了该结构的小世界特性， 用分形理论中的盒维数和豪斯道夫维数来证明了该结构的分形特征。 最后，本文运用盒计数方法和s p s s 软件的回归方法，计算了某地区断层裂缝的 分维数和度分布指数，揭示了现实世界的断层裂缝分布可以认为是复杂网络，具有 分形特征和无标度特征。 关键词：分形；小世界；无标度；重正化群；盒计数 a b s t r a c t 1 i h et h e o r yo fc o m p l e xn e t w o r k sh a sb e e ns t u d i e de x t e n s i v e l yo w i n gt ot h e i rc l o s e r e l e v a n c et om a n yr e a ln e t w o r k s i nt h er e a lw o r l d ，t h e s es y s t e m sc a nb er e p r e s e n t e db y c o m p l e xn e t w o r k s ，s u c ha si n t e r n e t ，s o c i a ln e t w o r k s ，m o v i ea c t o rc o i l a b o r a t i o nn e t w o r k ， m e t a b o l i cn e t w o r k s ，a n ds oo n i nt h e s ec o m p l e xn e t w o r k s ，t h en o d e sc a nr e p r e s e n t i n d i v i d u a l so ro r g a n i z a t i o n sa n de d g e sm i m i ct h ei n t e r a c t i o n sa m o n gt h e m a n dm a n y e m p i r i c a ls t u d i e si n d i c a t et h a tt h e s ev a r i o u sk i n d so fn e t w o r k sh a v et h r e ec o m m o n c h a r a c t e r i s t i c s ：s c a l e f r e e ，f r a c t a la n ds m a l l w o r l d t h e s ec h a r a c t e r i s t i c sr e c e i v et h e r e s e a r c h e r s g r e a ti n t e r e s ta n dc o n s i d e r a b l ea t t e n t i o n t h i st h e s i st a k e sm a t l a bs i m u l a t i v em e t h o dt op r o p o s eam o d e lo fs c a l e f r e e c o m p l e xn e t w o r kw i t ha g i n gm e c h a n i s ma n df r a c t a lb a s e do nt h em o d e lo fb a s c a l e f r e e n e t w o r k t h et h e s i su s e sr e n o r m a l i z a t i o na n db o x c o v e r i n gm e t h o do ff r a c t a lt h e o r yt op r o b e i n t oo r i g i n so ft h r e ef e a t u r e s o fc o m p l e xn e t w o r k sa n du n d e r l y i n gm e c h a n i s mo ft h e i r r e l a t i o na n dd e p i c te n t i r ef e a t u r e so fc o m p l e xn e t w o r k s t h et h e s i st a k e si t e r a t i v em e t h o dt ob u i l dac l a s so fn e t w o r kg r a p h sw i t hf r a c t a l i t y a n ds m a l l w o r l de f f e c tb a s e do na p o l l o n i a nn e t w o r k sa n ds i e r p i n s k i g a s k e t b y c a l c u l a t i n ga n a l y t i c a l l yt h ec l u s t e r i n gc o e f f i c i e n t ，t h ea v e r a g el e n g t ho ft h eg r a p h s ，a n d t h ed i a m e t e ra n dc a l c u l a t i n gt h eb o x c o u n t i n gd i m e n s i o na n dh a u s d o f fd i m e n s i o na sa m e a s u r eo ft h e i rf r a c t a l i t y ，w ep r o v et h a tt h eg r a p h sh a v es m a l l - w o r l da n df r a c t a l f i n a l l y ，t h et h e s i st a k e sb o x c o v e r i n gm e t h o da n dr e g r e s s i v em e t h o do fs p s st o c a l c u l a t et h ev a l u eo ft h ef r a c t a ld i m e n s i o na n de x p o n e n to fd e g r e ed i s t r i b u t i o no f f a u l t a g ec r a n n yo ns o m ea r e a ，d e p i c tt h ec r a n n yi nr e a lw o r l dh a ss c a l e f r e ea n df r a c t a l c h a r a c t e r i s t i c s k e y w o r d s ：f r a c t a l ；s m a l l - w o r l d ；s c a l e - - f r e e ；r e n o r m a l i z a t i o n ；b o x - c o v e r i n g 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人己用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：次日| 习危 日期：洳西年阴日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保瓤彩 ( 请在以上方框内打“4 ) 论文作者签名：弓艮酮虎 导师签名： 矿 卞气 、一 日期：加争年月6 日 日期：伽扩年占月e 日 5 5 第一章绪论 1 1 论文的研究背景 第一章绪论 当前，随着以i n t e r n e t 为代表的信息技术的迅猛发展，人们进入了网络时代。 同时，基于网络的理论方法，越来越多的复杂事物的规律和性质被挖掘和呈现。从 i n t e r n e t 到w w w ，从大型电力网络到全球交通网络，从生物体的神经系统到蛋白质 网络，从科研合作网到引文网，人们逐渐发现它们具有相似的特征，这些网络被统 称为复杂网络。而复杂网络理论所要研究的就是看上去互不相同的复杂网络之间的 共性和处理它们的普适方法n 1 。从2 0 世纪末开始，复杂网络研究正渗透到数理学科， 生命学科和工程学科等众多不同的领域，对复杂网络的定量和定性特征的科学理解， 己成为网络时代科学研究中一个极其重要的挑战性课题。得益于分形理论自身丰富 的理论内涵，复杂网络里自相似分形特征的涌现，使得分形理论成为复杂网络研究 中举足轻重的分支。 复杂网络研究的前身，可以追溯到1 8 世纪法国科学家欧拉对“k o n i g s b e r g 七 桥问题”的研究心1 。k o n i g s b e r g 是东普鲁士的一个城镇，城中有一条贯穿城区的河 流，河中有两个岛，岸与岛之间共有七座桥，由此提出了一个问题：能否一次性不 重复的走过七座桥，这就是历史上著名的“七桥问题”。欧拉将七座桥的图形，画 在了纸上( 将陆地抽象为节点，而桥则成为了点与点之间的连线) ，并通过推理得出 “不可能一次性不重复地走完这七座桥 的结论，从而由此开创了数学的一个分支一 图论。在欧拉解决七桥问题之后的相当长的一段时间里，图论并没有得到足够的发 展。直到2 0 世纪6 0 年代，由两位匈牙利数学家e r d o s 和r e n y i 建立了随机图理论， 并被公认为是在数学上开创了复杂网络理论的系统性研究口1 。他们认为两个节点是 否相连不再是确定的事情，而是用由一个概率p 决定，这种网络又称随机网络，网 络中的节点的连接数目大致相同，其分布遵循泊松分布。在2 0 世纪的后4 0 年中， 随机图理论一直是研究复杂网络的基本理论，被认为是描述真实最适宜的网络。2 0 世纪末，美国c o r n e l l 大学的w a t t s 和s t r o g a t z 在n a t u r e 上发表的c o l l e c t i r e d y n a m i c so f s m a l l 一y o r l d n et w o r k s t 钔和美国n o t r ed a m e 大学的b a r a b d si 和 a l b e r t 在s c i e n c e 杂志上发表的e m e r g e n c eo f 兜a j 啦i nr a n d o mn e t w o r k s t 引。 这两篇文章开创了复杂网络的研究新纪元，它们分别揭示了复杂网络的小世界特性 和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。这两种网络的出 现和大量真实网络的实证研究成果，促使人们去探索现实网络的内在演化机制，从 此掀起了研究复杂网络的热潮。s o n g 等人将分形理论中的盒计数法引入到复杂网络 的研究中来，揭示了复杂网络具有自相似的分形特征哺1 。他们又通过重正化过程， 青岛大学硕士学位论文 揭示出复杂网络中无标度特征与分形特征之间的关系。基于分形理论的复杂网络研 究，正曰益成为人们研究的热点。 1 2 论文的研究意义 复杂网络的研究大多采用数学和统计物理学的方法，而这为研究者提供了一种 复杂性研究的新视角、新方法。而采用分形理论研究复杂网络的方法，也逐渐兴起。 通过复杂网络的研究可以对各种复杂系统网络进行比较、研究和综合概括。正因为 如此，复杂网络刚提出，就在各个领域都呈现出广泛的应用前景。 而现实的复杂网络系统，如果发现一种能够提出它们共性的观点和方法，则能 够对这类网络的形成深入的认识。而复杂网络的实证研究发现这些不同的复杂系统 之间，却有着共同的特征：( 1 ) 无标度特征，即节点的连接度呈幂律分布；( 2 ) 小 世界特征，即较高的集聚系数、以及较短的平均路径；( 3 ) 分形特征，即复杂网络 的自相似性。 网络的节点的连接度呈幂律分布，呈现无标度特征，决定了网络由少数几个h u b 节点所支配，这一性质决定了网络的鲁棒性和脆弱性。“鲁棒而又脆弱已被许多 学者认为是复杂网络最基本的特性之一。鲁棒性，是指对复杂网络随机删除一部分 节点，网络中的绝大部分节点仍是连通的，而脆弱性则表示如果去掉少数几个h u b 节点，网络将会瘫痪。无标度性决定了现实网络的这双重特性，对随机节点故障具 有极高的鲁棒性，而对蓄意攻击却具有高度的脆弱性。这给现实系统带来很大的启 发意义。例如，在网络预防黑客攻击方面，为了更有效地保护网络，可以主要针对 保护那些大的门户网站口1 。在疫苗注射上，可以采取措施直接或间接地针对那些与 很多人具有连结关系的人接种疫苗，这样可以达到很好的效果。网络的较高的集聚 系数反映了事物在小世界的情况下自发走向有序的态势，较短的平均路径特征反映 了演化速度快的特征。在疾病传播方面，科学研究者通过建立复杂网络模型阴1 发现， 对于从规则网络到随机网络的所有传染概率p ( o ，1 ) 网络，其传染病的扩散时间刚 好与最短路径一致。这使得我们明白在控制疾病传播时，不仅仅是要提高治疗的医 学问题，而且考虑如何切断网络。 将复杂网络三大特征综合起来考虑，对现实也有很强的指导意义。在因特网中， 我们即希望不管网络的规模如何以倍数增长，针对于目标网络的搜索路径依然很短， 在不同网络节点之间存在“捷径 ，网络具有小世界特征，这样，资源分享将会更 加便捷，网络利用将会更加充分。我们又希望避免由于集群程度高，在接受目标攻 击时，网络极其脆弱的情况。结合分形特征的生成根源，集群节点的强度不相配性， 适当在现实的网络中，使集群节点与连通度更小的节点相连，避免集群节点之间直 2 第一章绪论 接相连，在实际世界的复杂网络中产生模块性，一个模块的瘫痪或者崩溃不至于极 大的影响另外的模块，从而去增强网络的鲁棒性，保护和屏蔽部分集群节点不受损 坏和攻击，使得网络不至于迅速瘫痪。 1 3 基于分形特征的复杂网络国内外研究现状 当前对复杂网络的研究已经扩展到不同的领域，研究方法，也由最开始的图论， 扩展到概率论、随机过程、统计物理学以及分形理论。借助这些方法，以及强大的 计算机编程运算能力，人们对复杂网络的认识也越来越深刻。 早在2 0 世纪初，德国著名物理学家普朗克就认为：“科学是内在的整体，它被 分解为单独的整体不是取决于事物本身，而是取决于人类认识能力的局限性。实际 上存在从物理学到化学、通过生物学和人类学到社会学的连续的链条，这是任何一 处都不能被打断的链条。许多研究者从系统整体出发，研究复杂网络。我们知道， 复杂网络的特征作为复杂网络的重要研究方向，经历了一个从简单到复杂的过程， 经历了从最初的随机特征到之后无标度特征、小世界特征、分形特征逐渐深化的过 程。由于现实复杂网络之间所表现的共性，使得人们对复杂系统的研究也越来越深 入。基于三大特征的越来越多的复杂网络模型正在被提出来，并一步一步地接近现 实网络。研究复杂网络的模型，再现现实系统的主要拓扑特性是复杂网络研究方向 之一，网络结构的复杂性研究在很大程度上决定了其功能特征，对发生在其上的动 力学特性至关重要。复杂网络上的博弈、合作、同步、搜索、随机游走、疾病传播 等动力学行为，都在很大程度上受到拓扑结构的影响，不同结构的网络，其动力学 行为表现出明显的、本质上的差异。 l 规则网络 早期，人们认为真实系统各因素之间的关系可以用一些规则网络表示，如一维 链、二维平面上的欧几里得格网等。用的最多的规则网络是由个节点组成的全局 耦合网络。在一个全局耦合网络中，任意两个节点之间都有边直接相连( 图1 1 ( a ) ) 。 因此，在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径长度和 最大的聚类系数。 稀疏的规则网络是最近邻耦合网络得到大量研究，网络的每一个节点只和它周 围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含个围成一个环的 点，其中每个节点都与它左右各k 膨个邻居节点相连，这里k 是一个偶数( 图1 1 ( b )。 3 青岛大学硕士学位论文 另外一个常见的规则网络是星形耦合网络，它有一个中心点，其余的一1 个点 都与这个中心点相连接，而它们彼此之间不连接( 图1 1 ( c ) ) 。 一o ? 一 ( 8 )( b ) 图1 1 几种不同形式的规则网络 ( c ) 2 随机图模型 与完全规则网络相反的是完全随机图，其中一个典型的模型是e r d o s 和r e n y i 于1 9 6 0 年提出了e r 随机图模型。 e r 模型中，顶点数固定为，顶点间由无向边随机相连，由此构成一个网络， 三( 一1 、 网络中有2 、 。条可能边，每条边出现的概率为p 且相互独立。 p 目 ( a p 目- 么露翕 蝴嗵 o ( b ) 图1 3 小世界网络模型的构造过程 w s 模型提出后，很多学者在此基础作了进一步改进，其中应用最多的是n e w m a n 和w a t t s 提出的所谓n w 小世界模型汨3 。n w 模型不同于w s 模型之处在于它不切断规 则最近邻耦合网络中的原始边，而是以概率p 重新连接一对节点。n w 模型的优点在 于其简化了理论分析，因为w s 模型可能存在孤立节点，但n w 不会。事实上，当p 很 小而很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小 世界模型。 4 无标度网络 b a r a b 6 s i 和a l b e r t 在对许多真实世界的网络进行研究时发现许多网络的度的 5 青岛大学硕士学位论文 分布函数呈现出幂律分布的特点。他们分析万维网的产生机理，提出了无标度网络 产生的两个基本机制：增长和择优连接。增长是指网络不是静态不变的，而是不断 演化不断增长的过程，是区别于小世界网络和随机网络的固定节点个数的；而择优 连接意味着网络中节点之间的连接不是均等的，而是有偏好的。他们认为网络是在 这两种规则下不断地生长演化的，并建立了著名的无标度网络演化模型，简称b a 模 型n 们。 小世界网络模型和b a 无标度网络模型的提出，掀起了复杂网络的研究浪潮。在 这两个模型的基础上，许多研究者又提出了许多扩展模型和新的演化机制。 k r a p i v s k y 等人研究了非线性的择优连接机制，并证明线性择优连接时的幂律分 ，一 、 布指数y 1 2 ，0 。j 。d o r o g o v t s e v 和m e n d e s n 2 1 考虑了老节点之间的连接或断开的情况， 用节点的连通的平均度的变化率来建立模型，并计算出该模型的网络幂指数。他们 还将节点的老化机制加入网络的演化当中，让新节点与老节点连接的概率和老节点 的年龄相关n 引。k l e m mk ，e g u f l u zv m 也考虑了节点的老化情况n4 1 ，提出了基于节 点有限记忆量的网络增长模型，证明了现实网络中的节点的年龄和它被连接的概率 成负相关关系。 随着对复杂网络研究的深入，复杂网络的自相似分形特征也被逐渐挖掘出来， 值得一提的就是阿波罗网络。而阿波罗网络同时具备了无标度特征、小世界特征和 分形特征。 由阿波罗填充问题得到和建立的阿波罗网络率先由a n d r a d e 提出n5 1 ，该网络由 于同时具有小世界和无标度的特性，并且具有一定的分形特征，引起了研究者的广 泛关注n 6 啦3 。周涛等提出了一个产生随机阿波罗网络的简单规则，并研究了随机阿 波罗网络的拓扑性质n 7 _ 1 郇。章忠志等则将该阿波罗网络扩展成高维，并建立了高维 的阿波罗网络n6 1 ，高维的随机阿波罗网络心引，以及阿波罗网络的一般模型等一系列 相关模型乜。捌。黄子刚等用随机行走的方式对确定性阿波罗网络和随机性阿波罗网 络进行了比较研究1 。正因为阿波罗这种完美而又符合现实网络的特点，值得进一 步更深刻的研究。 分形特征作为大多数复杂网络的共性真正被认识，是2 0 0 5 年的n a t u r e 上一篇 名为“s e l f s i m i l a r i t yo fc o m p l e xn e t w o r k s ”文章，给人提供了研究复杂网络的 新角度。文章作者s o n g 等创造性地用分形理论中的分维来描述网络中的自相似性， 采用盒维数的方法来计算网络的维数证明其自相似性，并进一步通过重正化过程， 证明自相似性和无标度的分布在网络的所有粗粒化过程阶段都成立。其实从0 2 年 d o r o g o v t s e v 等人提出的伪分形网络模型m3 开始，研究者开始建立各种具有分形特 征的网络模型。阿波罗网络模型就是具有明显的自相似特征的模型。古志鸣用单纯 6 第一章绪论 形剖分生成了一个类似阿波罗网络的模型心5 1 。在s o n g 这篇文章之后，研究者逐步开 始建立具有分形特征的网络演化模型，并用这种盒维数方法来证明其分形性协3 2 1 。 g i m 和g o h 等人则从一种称为骨架( s k e l e t o n ) 的树结构出发来建立网络模型，并 分析研究分形网络的成因，认为最初的分形网络可以看作是这种分形骨架和一些点 与点之间的捷径组成曙6 矧。h e r n a n 等人则从伪分形模型进行扩展，提出迭代的无标 度网络，并证明其分形性b 引。d i d i e rs o r n e t t e 等人则提出了用边覆盖来计算复杂 网络分维数日。d j b s o a r e s 建立了一个空间填充的复杂网络模型噼1 ，并用盒维数 的方法证明其分形性。s o n g 在随后的研究中，又将复杂网络出现的这种分形性归因 于连接度高的节点之间的互斥性口割，并提出了计算盒维数的算法利。可以认为复杂 网络的分形特征正在成为一个重要的研究方向。 1 4 本文的研究内容 现在，随着分形特征的被挖掘，复杂网络的研究进入了一个新的阶段。人们建 立了越来越多的复杂网络模型，也越来越接近现实的复杂网络特征。根据复杂网络 研究的国内外现状，本文主要做了以下有创新性的工作： l - 对经典的b a 无标度复杂网络模型作了改进，利用m a t l a b 进行仿真，建立了 新的基于距离择优连接的无标度复杂网络演化模型，其节点度分布的指数r = 2 6 ， 区别于b a 无标度复杂网络的度分布指数r 2 3 ，具有分维特征。 2 将复杂网络的三大特征：无标度特征、小世界特征、分形特征作了相互比较， 找出它们之间对复杂网路的关系以及复杂网络具有这些特征的根源所在，揭示了复 杂网络演化和形成的机制。 3 阿波罗网络同时具有无标度特征、小世界特征和自相似分形特征，运用分形 理论，对阿波罗网络进行解析研究，同时给出网络的统计属性和参数，以证明阿波 罗网络的三大基本特征。 4 给出了一个具有分形和小世界特性的网络图，从分形理论的视角去研究复杂 网络演化模型，用数学解析的方法给出了该网络的统计特征：小世界特征和分形特 征。 5 运用分形理论中的盒计数法，对现实中某地区的断层裂缝进行分析研究，得 到断层裂缝具有无标度特征，并在无标度区间内，具有分形的特征，这一结果，对 发现断层裂缝并对断层裂缝的资源勘探开发具有重要的现实意义。 7 青岛大学硕士学位论文 1 5 本文的结构 第一章为概述部分，对复杂网络的研究历程、基于分形理论的复杂网络研究的 国内外研究现状、研究方法进行了介绍，指出了当前研究的不足之处。 第二章介绍分形的发展脉络，分形目前的几种定义，以及分形理论中可以用到 复杂网络研究中去的分形维数、盒计数法、重正化群等方法。 第三章着重介绍了复杂系统和复杂网络的基本概念，描述了复杂网络的一些基 本属性，对复杂网络的重要特征参数给出介绍，最后利用m a t l a b 仿真的方法，建立 了改进的无标度复杂网络演化模型，并对得到的图形性质进行分析研究。 第四章对复杂网络的三大特征：无标度特征、小世界特征、分形特征进行比较 研究，得出它们在复杂网络中存在的相关关系，指出分形特征正日益成为许多现实 的复杂网络的共性，揭示了三大特征形成的根源，以及对复杂网络性质和功能产生 的影响。 第五章介绍了同时具有无标度特征、小世界特征和分形特征的阿波罗网络，并 对其的统计属性进行解析。又从谢尔宾斯基垫片出发，给出了一个同时具有小世界 特征和分形特征的复杂网络图。对可以认为是复杂网络的断层裂缝，运用分形理论 的方法，对其分布特征进行了定量研究，指出现实世界中复杂系统的分形特征普遍 存在的性质。 最后，对研究结果进行了总结，指出研究中的不足之处，对下一步的研究工作 做出了展望。 8 第二章分形理论的基本概念 2 1 分形的定义 第二章分形理论的基本概念 古希腊人创立的经典几何学一直是人们认识自然物体的有力工具。宇宙理论， 宏伟的建筑都是建立在这个基础上的。以致伟大的科学家伽利略曾经断言：大自然 的语言是数学，“它的标志是三角形、圆和其他几何图形 。然而自然界存在着大 量无法用经典几何方法准确描述的复杂图形，如自然界中长着分岔的树枝、变幻的 云彩、高低不平的山脉、弯曲的河流，生活中股市上的股票价格曲线、水文测量中 的水位变化曲线、一个地区的气候变化曲线等等。从整体上看，它们的几何图形是 处处不规则的，但在不同的尺度上图形的规则性又是相同的，也就是从整体到局部 的各个层次上都有自相似的结构，在一个花样的内部还有更小的同样的花样。 这种特殊的不规则的图形称为分形口副。分形( f r a c t a l ) 一词，是曼德尔布罗特创 造出来的，其原意具有不规则、支离破碎等意义，分形几何学是一门以非规则几何 形态为研究对象的几何学。由于不规则现象在自然界的普遍性，分形几何又称为描 述大自然的几何学。目前分形理论已经是现代数学的一个新分支，其本质又是一种 新的世界观和方法论，它承认世界的局部可能在一定条件过程中，在某一方面( 形态、 结构、信息、功能、时间、能量等) 表现出与整体的相似性。 。 曼德尔布罗特曾经为分形下过两个定义： 1 ) 满足条件d i m ( a ) = d i m ( a ) 的集合a ，称为分形集。其中，d i m ( a ) 为集合a 的分维数，d i m ( a ) 为其拓扑维数。一般说来，d i m ( a ) 不是整数，而是分数。 2 ) 部分与整体以某种形式相似的形，称为分形。 然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的 内容。实际上，对于什么是分形，到目前为止还不能给出一个确切的定义，正如生 物学中对“生命”也没有严格明确的定义一样，人们通常是列出生命体的一系列特 性来加以说明。分形具有五个基本特性： 1 ) 分形都具有任意小尺度下的比例细节，或者说它具有精细的结构； 2 ) 分形不能用传统的几何语言来描述，它既不是满足某些条件的点的轨迹，也 不是某些简单方程的解集； 3 ) 分形具有某种自相似形式，可能是近似的自相似或者统计的自相似； 4 ) 一般，分形的“分形维数”，严格大于它相应的拓扑维数； 5 ) 在大多数令人感兴趣的情形下，分形由非常简单的方法定义，可能以变换的 迭代产生。 。 9 青岛大学硕士学位论文 2 2 分形的缘起 作为现代数学的一个新分支，分形( f r a c t a l ) 理论被誉为大自然的几何学，是 当今世界非常活跃，应用广泛的新理论、新学科。 分形的概念是美籍法国数学家曼德尔布罗特1 9 7 5 年首先提出的，但分形最早的 缘起可追溯i 0 0 年前，德国数学家魏尔斯特拉斯构造了处处连续但处处不可微的函 数，集合论创始人康托( g c a n t o r ，德国数学家) 构造了有许多奇异性质的三分康 托集，1 9 1 5 年，波兰数学家谢尔宾斯基( w s i e r p i n s k i ) 设计了象地毯和海绵一 样的几何图形。这些都是为解决分析与拓扑学中的问题而提出的反例，但它们正是 分形几何思想的源泉。1 9 1 0 年，德国数学家豪斯道夫开始了奇异集合性质与量的研 究，提出分数维概念。1 9 3 2 年庞特里亚金等引入盒维数。1 9 3 4 年，贝塞考维奇更深 刻地提示了豪斯道夫测度的性质和奇异集的分数维，他在豪斯道夫测度及其几何的 研究领域中作出了主要贡献，从而产生了豪斯道夫一贝塞考维奇维数概念。 1 9 7 5 年，曼德尔布罗特用法文出版了分形几何第一部著作分形：形状、机遇 和维数。它集中了1 9 7 5 年以前曼德尔布罗特关于分形几何的主要思想，它将分形 定义为豪斯道夫维数严格大于其拓扑维数的集合，总结了根据自相似性计算实验维 数的方法，由于相似维数只对严格自相似这一小类集有意义，豪斯道夫维数虽然广 泛，但在很多情形下难以用计算方法求得，因此分形几何的应用受到局限。 1 9 8 2 年，曼德尔布罗特出版自然界的分形几何，将分形定义为局部以某种 方式与整体相似的集，重新讨论盒维数，它比豪斯道夫维数容易计算，但是稠密可 列集盒维数与集所在空间维数相等。为避免这一缺陷，1 9 8 2 年特里科特引入填充维 数。 1 9 8 5 年，迈克多纳和格雷波基等得到分形吸附界的三种类型： 1 ) 局部不连通的分形集； 2 ) 局部连通的分形拟圆周； 3 )既不局部连能又不是拟圆周。前两者具有拟自相似性。 1 9 8 5 年，曼德尔布罗特提出并研究自然界中广泛存在的自仿射集，它包括自相 似集并可通过仿射映射严格定义。1 9 8 2 年德金研究递归集，这类分形集由迭代过程 和嵌入方法生成，范围更广泛，但维数研究非常困难。德金获得维数上界。1 9 8 9 年， 钟红柳等人解决了德金猜想，确定了一大类递归集的维数。 随着分形理论的发展和维数计算方法的逐步提出与改进，1 9 8 2 年以后，分形理 论逐渐在很多领域得到应用并越来越广泛。建立简便盛行的维数计算方法，以满足 应用发展的需要，还是一项艰巨的任务。 分形理论与动力系统的混沌理论交叉结合，相辅相成，认为复杂系统的局部可 1 0 第二章分形理论的基本概念 能在一定条件和过程中，在某一方面( 形态、结构、信息、功能、时间、能量等) 表现出与整体的相似性，而这也催生了分形理论在复杂系统与复杂网络中的应用日 益兴起。 2 3 分形维数 维数是几何对象的一个重要特征量，其概念源于经典的欧氏空间。在欧氏空间 里，如果要确定一个点的位置，需要引入一个确定的坐标系。例如，在一个点的位 置在普通欧氏空间里要用3 个独立坐标来表示，即用三个实数( x ，y ，z ) 代表空间中的 一个点，而在平面上只需要两个独立坐标( x ，y ) ，在直线上则仅需要一个坐标x 就够 了。由于独立坐标的数目要与欧氏空间的维数相一致，所以说直线所构成的空间是 一维的，平面是二维的，普通( 立体) 空间是三维的。将这一概念推广：要确定物 体或几何图形中任意一点的位置，所需要的独立坐标的数目，就是该物体或几何图 形的维数。人们称这种维数为经典维数或欧氏维数。然而这种维数只能是整数，存 在较大的局限。自然界中如雪花、云彩、山脉等复杂的物体的维数则不能通过这种 整数维来表达，分维则是用对这些复杂事物进行定量分析的工具。 首先从整数维开始对维数这一概念进行扩展。设用“半径”为r 的线段( 即长 度为2 r 的线段) 作单位去测量一个长度为l 的线段，得到所需的个数为n ( r ) ，所 以得到： ( r ) 2 寺 2 一( 1 ) 这表明在长度为l 的一维线段中包含有n ( r ) 个“半径”为r 的单位线段。所以公式 2 一( 1 ) 可以写成： ( ，) = ( 争r = c r 一，( d = 1 ，c = 兰l ) 2 - ( 2 ) 同样，可以设有一个二维的圆，若用半径为r 的小圆面积作单位去测量其面积 为s ，测量的个数为n ( r ) ，则有 n ( r ) = 之 2 一( 3 ) 这表明在面积为s 的二维圆中有n ( r ) 个“半径”为r 的单位圆： ( ，) ：( 鸟，4 ：c ，一，( d ：2 ，c ：马 2 一( 4 ) 再将二维拓展成三维，用半径为r 的小球体积作单位测量其体积v ，测量的个 数为n ( r ) ，则有 帅) = 丢 2 - ( 5 ) 3 青岛大学硕士学位论文 表明在体积为v 的三维球中有n ( r ) 个半径为r 的单位球 ( 厂) ：( 当厂一：c 厂，( d ：3 c = 当 2 一( 6 ) q 死q 冗 根据上面的情况，可以将维数推广到一般情况，对于一个客体，如果测量其“容 积”的单位的半径为r ，用单位测量客体的个数n ( r ) 满足如下关系： n ( r ) ：c 1 一d ，o ct - d ， 2 一( 7 ) 则客体的维数为d i ，这一维数就是经典的分形维数豪斯道夫维数。 我们都知道，将正方形的边长放大倍，面积即会扩大r 倍，如果正方体的边 长扩大倍，则体积会扩大p 倍。则同样可以推理：对于某客体，如沿其每个独立 方向皆放大倍，若新客体为原客体的厅倍，那么必有 k ：p 2 一( 8 ) 所以客体的维数d ，为 d i ：婪 2 一( 9 ) h ll 作为分维的定义计算起来比较方便，并且和公式2 一( 7 ) 是一致的。 分数维是描述分性特征的定量参数。经典的分形维数一豪斯道夫维数，定量地描 述一个点集规则或不规则的几何尺度，同时其整数部分反映图形的空间规模，这揭 示了分形维的意义。 2 4 盒计数法 上一节，我们介绍了经典的分形维数一豪斯道夫维数，它是用不一样大小的“小 球”来覆盖集合a 的，由定义求解是比较困难的。而由曼德尔布罗特定义的分形集 的维数是：豪斯道夫维数大于拓扑维数。故由曼德尔布罗特定义的分形集维数也是 很难直接求出分形维的大小。因此，用一样大小的正方形盒子来代替“小球”来求 解分形维则很容易求出，即所谓的盒维数方法，又称为盒计数法b 6 1 。 1 设( x ，d ) 是距离空间，设acr ”，这里欧氏距离被引用。用边长为当的闭的 z ” 1 正方形盒子来覆盖，令m ( a ) 表示边长为砉的盒子和分形集a 相交的个数，如 z 果 1 2 第二章分形理论的基本概念 l i i n 垫! 型! ! 垒丝：d2 一( 1 0 ) f $ - - l * 。 i n2 4 则称分形集a 的维数为d ，即我们所谓的盒维数。 1 按照盒维数定义，盒计数法中，不同尺度砉下的。( a ) 为覆盖分形的最少盒子 数，表明的含义是：( 1 ) 。( a ) 个盒子完全覆盖分形。( 2 ) n 。( a ) 在数量上最少。 ( 3 ) 所有的盒子都非空。 随着s o n g 等人利用盒计数法和重正化群方法研究复杂网络的自相似性质，深入 探索了复杂网络演化的内在机制。由此，盒计数法日益成为复杂网络研究的有力工 具。 2 5 重正化群过程 美国物理学家威尔逊( w i l s o n ) 把量子场论中的重正化群方法创造性地运用到 相变理论研究中，取得重大成就，为此获得1 9 8 2 年诺贝尔物理学奖。重正化群方法 ( 简称r g 方法) 实质是在观测中改变粗视化( c o a r s e n i n g ) 程度，借此定量地分析 物理量的变化以揭示某种规律，不仅是研究临界现象的有力工具，而且可以广泛地 应用于材料科学研究等领域。特别是作为一种“由大量随机个性提取必然共性”的 科学方法而与电子计算机相结合，己开始用于复杂网络理论的应用研究。 渗流( p e r c o l a t i o n ) 与复杂系统结构的形成以及复杂网络的弹性问题密切相关。 以渗流问题为例，介绍重正化群引。 设在某种尺度下有一物理量为p ，当用此尺度的2 倍粗视化时，此物理量为 p7 ，此关系可记为：p7 = 厂2 ( p ) ，如果再继续2 倍粗视化，将有如下关系式成立： p = a ( p7 ) = 矗- ( p ) = 兀( p ) 2 一( 1 1 ) 这里，是变换，一般它有如下性质： 正兀= 兀b ， = 1 2 一( 1 2 ) 后者为恒等变换，此外不存在逆变换九。 满足这种性质的变换称半群，故倒称重正化( 半) 群。 考虑渗流问题：参看图2 1 暗7 1 ，将若干尺寸相同的绝缘球和金属球装在一个绝缘 的箱体内，置于两电极之间。设金属球占总球个数的百分比为尸，每摇动箱体一次， 可得一种掺合状态即概率分布。摇动若干次可得一个概率分布的集合，称总状态数。 设其中使电路导通的状态数占总状态数的百分比为称为连通概率。显然，当尸= 0 1 3 青岛大学硕士学位论文 时，p = o ，即完全不会出现导通：当p = 1 时，p 7 = l ，恒处于导通状态：当p 由0 增加到1 的过程中，每个p 都对应一定的连通概率。这个实验可以用计算机模拟来完 成，得到尸一尸7 图线。从而可知当p 很小时，连通概率p 7 等于o ，当p 达到临界值 pc 时，尸，迅速上升接近和达到l 。 现在分析箱体的导电问题，随着金属球在箱体中所占格子的比率p 的逐渐增大， 到某一临界值p ，时，箱体将成为导体。此临界点也就是发生相变的相变点。 今用粗视化或重正化方法寻求此临界点，再参看图2 2 7 1 ，最低一行表示箱体 中的4 个格子，圆圈表示被金属球占有，第二行的箭头表示重正化，最上一行表示 重正化为一个格子。 如果在4 个格子中，纵横方向均被导体占有，如最低一行左端的两个，则这4 个格子纵横均导电，故重正化后的格子中也有导体点，如果被占格子只有2 个或少 于2 个，则纵横方向不能同时导电，重正化后的格子中将没有金属球。 金属。n 5 6 0 矗 霎一 疏 盒$ i i , - o 6 5 9 b l o o n m 金属矿0 7 0 7 c 1 0 0 n m l o o n m 金鳓f 0 7 5 2 垒p = 0 8 3 6 d 尊 图2 1 箱体上金属簇的分布，p 为金属的比率 将重正化后的格子称为超格子，设重正化前金属球占有一个格子的概率为p ， 重正化后金属占有一个格子的概率为p7 ，则4 个格子同时被金属占有( 如图2 2 下行最左端的4 个格子) 的概率为p 4 。 1 4 第二章分形理论的基本概念 百# 百面 # # # # # 图2 2 重正化过程 金属占有3 个格子将有4 种情况：一个格子不被占，概率为以一，其他3 个 格子被占，概率为p 3 ，这两种事件同时发生，概率为p 3 ( 1 一p ) ，共有4 种可能，只 要其中之一发生，就发生了3 个格子被占，故应为4 种可能情况概率之和为 4 p 3 ( 1 一p ) 。 4 个格子或3 个格子被占，超格子也将被占，故有 p = p 4 + 4 p 3 ( 1 一p ) ，2 一( 1 3 ) 临界情况：根据不动点原理，不论进行多少次重正化，格子被金属占有的概率 都是一样的( 不变的) ，否则，如果重正化后p 增大，继续重正化下去，将导致p = - ，即薄膜全部为金属。如果减少，将导致p = 仍即整个薄膜没有金属。 因此，设临界情况的p 为p 。，将有 p 。= p ? + 4 p ：( 1 一p 。) 2 一( 1 4 ) 解此方程将得到4 个不同的根p 。：0 ，1 ，望掣堡籍- o 4 3 6 ，o 7 6 8 。取其中合理值： o p 。= 0 7 6 8 2 一( 1 5 ) 实验值为p 。= o 7 5 2 ，比较相近，参看图2 1 d 。 不仅仅是渗流问题，临界现象在自然界和社会领域中是普遍存在的。重正化群 方法是研究转变点附近临界现象的新的有力工具。特别是近几年来，b r e z i n 等人把 青岛大学硕士学位论文 重正化群方法与场论对应起来，使人们对临界现象的理解更加深入了一步。重正化 群理论将对其他科学产生深远的影响。我们可以用电子计算机建立相关模型，运用 重正化群的理论方法，设计围棋对弈最佳方案，果树防病虫害优化植距，大范围民 意倾向调查，宏观决策的微观支持，选举区域规划以及石油探测中渗流现象模拟研 究等。 重正化群也与复杂网络密切相关。金属占有格子与网络中点的占有可对应起来， 如果网络中某些点被破坏( 不再占有) ，网络能否保持工作，这就是复杂网络的鲁棒 性问题口8 1 。所以分形理论中的重正化群方法是研究复杂网络结构和功能的重要工具。 1 6 第三章复杂系统与复杂网络概述 第三章复杂系统与复杂网络概述 3 1 复杂系统与复杂性科学 复杂网络的研究，是从人们对复杂系统的认识开始的。研究复杂系统的科学， 就是复杂性科学。 3 1 1 复杂性科学的研究背景 2 0 世纪的科学研究，如物理学，其研究方法是“还原论( r e d u c t i o n ) ”，即研究 单一个体。随着现代科学技术的发展，研究问题的复杂性提高，“还原论”的方法 步履维艰。2 0 世纪8 0 年代，有几位物理学和经济学等领域的诺贝尔奖金的获得者，盖 尔曼( m u r r a yg e l l - m a n n ) ，安德森( p h i l i pa n d e r s o n ) 、阿诺( k e n n e t ha r r o w ) ， 认识到从整体性研究问题的重要意义，并聚集了一批物理、经济、生物、计算机等方 面的研究人员，在s a n t af e 成立了一个研