6 小世界与无尺度网络的一体化模型 - read.doc

博 士 学 位 论 文 复杂网络的演化模型研究 Evolving models of complex networks 作 者 姓 名： 章 忠 志 学科、专业 ： 管理科学与工程 学 号 ： 指 导 教 师： 荣 莉 莉 教授 完 成 日 期： 2006年3月 大连理工大学 Dalian University of Technology  独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 日期： 摘 要 复杂网络已成为学术界研究的一个热点，它在工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。例如，在管理领域，复杂网络可应用于系统结构分析、广告营销、产品定价、决策意见形成、知识获取、组织间的信息（知识）传播与交换等许多方面。现实世界中的网络非常普遍，但人们对它们的结构和属性却知之不多。众所周知，随机性符合大多数复杂现实系统形成的主要特性，而确定性可以让人对复杂网络的形成以及不同节点间的相互作用有一个直观而形象的理解。因此，以随机的方式和确定的方式构造符合真实系统性质的小世界网络和无尺度网络的演化模型不仅具有重要的理论意义，而且具有潜在的应用价值；特别地，演化模型可以捕捉网络形成的动态特性，能够准确获得各种微观机制对网络最终结构的影响，对人们掌握网络功能及其动力学有着极其重要的作用。本文分别从确定性和随机性两个方面着手，对小世界网络和无尺度网络的演化模型进行深入研究，通过建立或构造网络模型来模拟真实网络的拓扑和结构性质。 1、建立了两个小世界网络的演化模型。通过边迭代的方式，构造了一个确定性小世界网络（Deterministic Small-World Network，DSWN）模型，并对DSWN模型进行扩展，按照地理位置择优连接机制，建立了一个演化的小世界网络模型（ESWN），DSWN是其一个特例；解析计算和模拟了这两个模型的度分布、簇系数、平均路径长度和直径。它们均为指数网络，具有较大的簇系数，其平均路径长度或直径以网络规模的对数形式增长。这两个模型能为现实世界中存在地理位置约束的网络提供描述上的借鉴。 2、提出了BA网络的一个等价模型及扩展模型。BA网络的择优连接过程使得在计算机上生成大规模网络需要消耗大量的时间，为了解决这一问题，本文提出了BA网络的一个等价模型，等价模型最终演化成的结构特性与BA网络相同；由于在等价模型的生成过程中，以均匀连接代替BA模型的择优连接过程，因此，在计算机上实现本模型时，比按照BA算法生成相同规模的网络所需时间要少得多，为人们研究BA网络的结构和动力学提供了很大的方便。接着，为了更准确地描述BA网络的变体模型——BA指数网络的拓扑性质，对BA指数网络的主要结构特性进行了解析研究。最后，为了描述现实世界中的局部范围内择优连接机制、高集聚现象及广延指数分布，提出了BA网络的一个扩展模型，BA网络模型是扩展模型的一个特例，利用平均场与比率方程的方法给出了扩展模型结构特性的解析计算过程，扩展模型能描述一类具有广延指数分布的现实网络。 3、研究了一类确定性无尺度网络模型。根据著名的阿波罗分形垫，循序渐进地构造和研究了一类确定性无尺度网络模型。首先，提出了确定性阿波罗网络（Deterministic Apollonian Networks，DAN）的一个迭代生成算法；然后，提出了DAN的一个扩展模型（GDAN）、扩展模型的一个变体（V-GDAN）以及扩展模型和变体模型相应的生成算法。根据生成算法，利用组合数学和图论的方法对模型的度分布、簇系数和直径等主要参数进行了求解，并对不同模型的性质进行了比较研究。研究发现，DAN、GDAN与V-GDAN的节点度均服从幂律分布，度指数在较宽的范围内可调，它们的簇系数较大且可以调节大小，它们的直径均以网络规模的对数形式增长。 4、构建了一类随机无尺度网络模型，研究了模型的主要拓扑性质及发生在部分模型上的同步动力学。根据著名的阿波罗分形垫，由浅及深地构造并研究了一类随机的无尺度网络模型。首先，提出了高维随机阿波罗网络（High-dimensional Random Apollonian Networks，HDRAN）模型及其变体V-HDRAN，此后，建立了一个演化的阿波罗网络（Ev