【毕业学位论文】（Word原稿）博士论文－复杂网络演化模型的研究-管理科学与工程

博 士 学 位 论 文 复杂网络的演化模型研究 of 者 姓 名： 学科、专业 ： 管理科学与工程 学 号 ： 指 导 教 师： 荣 莉 莉 教授 完 成 日 期： 20 年 3 月 大连理工大学 独创性说明 作者 郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 日期： 摘 要 复杂网络已成为学术界研究的一个热点，它在 工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。例如，在管理领域 ，复杂网络可应用于系统结构分析、广告营销、产品定价、决策意见形成、知识获取、组织间的信息（知识）传播与交换等许多方面 。现实世界中的网络非常普遍，但人们对它们的结构和属性却知之不多。众所周知，随机性符合大多数复杂现实系统形成的主要特性，而确定性可以让人对复杂网络的形成以及不同节点间的相互作用有一个直观而形象的理解。因此，以随机的方式和确定的方式构造符合真实系统性质的小世界网络和无尺度网络的演化模型不仅具有重要的理论意义，而且具有潜在的应用价值；特别地，演化模型可以捕捉网络形成的动态特性，能够准确获得各种微观机 制对网络最终结构的影响，对人们掌握网络功能及其动力学有着极其重要的作用。本文分别从确定性和随机性两个方面着手，对小世界网络和无尺度网络的演化模型进行深入研究， 通过建立或构造网络模型来模拟真实网络的拓扑和结构性质 。 1、建立了两个小世界网络的演化模型。 通过边 迭代的方式， 构造了一个确定性小世界网络 （ 模型，并对 型进行扩展，按照地理位置择优连接机制，建立了一个演化的小世界网络模型（ 析计算和模拟 了这两个模型的度分布、簇系数、平均路径长度和直径。它们均为指数网络，具有较大的簇系数，其平均路径长度或直径以网络规模的对数形式增长。 这两个模型 能为现实世界中存在地理位置约束的网络提供描述上的借鉴。 2、提出了 络的一个 等价模型及扩展模型 。 络的择优连接过程使得在计算机上生成大规模网络需要消耗大量的时间，为了解决这一问题 ，本文 提出了 络的一个等价模型，等价 模型 最终演化成的结构特性与 络相同；由于在 等价模型的生成过程中，以均匀连接代替 型的择优连接过程，因此， 在计算机上实现本模型时，比按照 法生成相同规模的网络所需时间要少得多，为人们研究 络的结构和动力学提供了很大的方便。接着，为了更准确地描述 络的变体模型 数网络的主要结构特性进行了解析研究。最后，为了描述现实世界中的局部范围内择优连接机制、高集聚现象及广延指数分布，提出了 络的一个扩展模型 ， 络模型是 扩展模型的 一个特例，利用平均场与比率方程的方法给出了扩展 模型 结构特性的解析计算过程，扩展模型能描述一类具有广延指数分布的现实网络。 3、研究了一类确定性无尺度网络模型。 根据著名的阿波罗分形 垫，循序渐进地构造和研究了一类确定性无尺度网络模型。首先，提出了 确定性阿波罗网络 （ 一个迭代生成算法；然后，提出了 扩展模型的一个变体（ 及扩展模型和变体模型相应的生成算法。根据生成算法，利用 组合数学和图论的方法对 模型的度分布、簇系数和直径等主要参数进行了求解，并对不同模型的性质进行了比较研究。研究发现， 节点度均服从幂律分布，度指数在较宽的范围内可调，它们 的簇系数较大且可以调节大小，它们的直径均以网络规模的对数形式增长。 4、构建了一类随机无尺度网络模型，研究了模型的主要拓扑性质及发生在部分模型上的同步动力学。 根据著名的阿波罗分形垫， 由浅及深地 构造并研究了一类随机的无尺度网络模型。 首先，提出了高维随机阿波罗网络 （ 模型及其变体 后，建立了一个演化的阿波罗网络（ 模型，将 析与模拟结果相吻合。它们的平均路径长度最多按照网络规模的对数形式增长，度指数和簇系数均可调节大小，其中演化阿波罗网络的度指数在区间 2,3 连续可调。这些模型可以很好地描述现实系统。最后，研究了演化阿波罗网络的同步能力，结果表明在空间维数相同的情况下，确定性阿波罗网络比随机阿波罗网络容易同步。 5、为了将小世界网络与无尺度网络纳入到一个框架之下，建立了小 世界网络和无尺度网络的确定性统一模型。 首先 ， 提出了一 个确定性 一体化模型（ 将 入到一个模型中； 给出了一种节点标号方法， 对一体化模型中的所有 节点进行标号，使得任意一对节点之间的最短路径都可以根据标号很容易得到。然后， 通过引入一个 取值为整数的参数， 扩展了 型， 提出了小世界网络和无尺度网络的一个确定性交叉模型 （ ，通过调节参数值，可以得到 一类通过边迭代生成的确定性无尺度网络。最后，通过边递归的方式，构造了交叉模型的一个变体（ 。利用图论和组合数学的方法， 解析计算了交叉模型 变体模型度分布、 二阶平均度、度相关、 簇系数和直径等主要拓扑特性 。 关键词：复杂网络；小世界网络；无尺度网络；复杂系统；演化模型 in a of in to as in or of of It is to us is in of it to a of do to it be of of to to in we to In as 1. a is by is to an by a is a In a is to it is to to of of an a or a of by 2. An to A an A of A it it to To an A is of to A In of of of So A be of A is is et of A an A is by a A a of is by of a of to 3. A of is a of is a as of in of on of of in as a of 4. A of is in of is a of is AN as is an of a on of AN be . of is at of in to AN is 5. In to a is a A of of is a is to in is on by a a a of by a is a We of of of by 录 摘 要 . I . 绪 论 . 1 杂网络的发展、应用及研究意义 . 1 杂网络的发展历 程 . 1 杂网络的应用及研究意义 . 2 络的定义及表示方式 . 5 杂网络的特征度量 . 5 杂 网络的分类 . 9 杂网络演化模型的研究概况 . 9 则网络 . 10 机图模型 . 10 世界网络 . 11 A 无尺度网络 模型 . 12 化 网络 模型 . 12 定性网络模型 . 14 杂网络演化模型研究存在的问题 . 15 文的主要工作 . 17 2 迭代方式生成的小世界网络模型 . 21 迭代生成的确定性小世界网络 . 21 络生成的迭代算法 . 21 络的 主要特性 . 23 化的小世界网络模型 . 26 化 网络的迭代算法 . 26 化 网络的拓扑性质 . 27 结 . 32 3 络的等价模型与扩展模型 . 33 A 网络的等价演化模型 . 34 价模型的生成 . 34 价模型的解析计算与数值模拟 . 35 A 网络的变体模型 . 40 A 随机指数网络 . 40 A 确定性 指数网络 . 44 种网络结构特性的比 较 . 46 A 网络的扩展模型 . 46 型的描述 . 46 型性质的解析 . 48 结 . 54 4 确定性增长的 无尺度网络模型 . 55 定性 阿波罗 网络模型 . 55 络构造 . 55 络的迭代算法 . 59 络的结构特性 . 60 定性 阿波罗 网络的扩展模型 . 63 型生成的迭代算法 . 64 型的结构特性 . 64 定性 阿波罗 网络扩展模型的变体 . 68 体 模型生成的递归算法 . 68 体 模型的结构特性 . 69 结 . 72 5 随机增长的无尺度网络模型 . 73 机 阿波罗 网络模型 . 73 络构造与迭代生成算法 . 73 络的统计特性 . 74 机 阿波罗 网络的变体模型 . 80 型的描述 . 80 型的统计特性 . 80 化的 阿波罗 网络模型 . 84 络构造及生成算法 . 85 络 的拓扑性质 . 86 络的同步性 . 90 结 . 92 6 小世界与无尺度网络的一体化模型 . 93 统一模型 . 93 型的建立 . 93 找网络 的最短路径 . 94 迭代生成的一体化模型 . 100 型生成的迭 代算法 . 100 型的拓扑性质 . 101 展的 伪分形无尺度网络模型 . 103 体 模型的递归构造 . 103 型的拓扑性质 . 104 结 . 108 7 结论与展望 . 109 论 . 109 望 . 110 文未来的工作 . 110 络建模的新方向 . 111 参 考 文 献 . 113 论文的主要创新点 . 123 附录 攻读博士学位期间参加的项目及个人获奖情况 . 125 攻读博士学位期间发表学术论文情况 . 126 致 谢 . 128 大连理工大学学位论文版权使用授权书 . 130 1 绪 论 著名的物理学家霍金认为：二十一世纪是复杂性的世纪。 复杂网络的研究是复杂性理论研究的一部分，