论文摘要
复杂网络广泛存在于自然界和人类社会，是复杂性科学中复杂系统的抽象。继小世界网络和无标度网络模型被提出以来，复杂网络的研究逐渐成为当今科学界研究的前沿和热点，从数学、物理到生命科学，从社会科学到工程技术等众多不同领域的学者开始开展复杂网络的研究，并且在复杂网络的拓扑结构和性质、网络模型、网络的同步、搜索等动力学行为以及网络应用等各个方面都取得了重要成果，这些成果加深了人们对复杂网络的认识，揭示了隐藏在现实世界中的一些普遍规律。然而，相比于网络的复杂性本身而言，这些认识仍是非常局限的，大量的复杂网络的奥秘有待于揭示和研究，更多的实证分析和理论研究工作亟待完成，实际领域的应用也亟待挖掘和探索。本文的主要工作是运用Cayley图和代数图论方法对复杂网络的性质、演化模型展开理论研究，并进行了一些应用方面的探索，主要的工作成果和创新点如下：1. Cayley图是运用有限群构造高对称网络的图论模型，在互连网络设计中有重要应用，肖文俊和Parhami曾于2006年首次提出Cayley图可作为确定性的小世界网络模型，本文在此基础上进行了形式化描述和扩展,将极小Cayley图作为构造小世界网络的基础，分析了Cayley图的极小性与小世界特性的关联，提出了基于极小Cayley图的扩展构造确定性小世界网络的方法。该模型通过增加极小Cayley图的生成集，构造出一类对称性强且结构规则的小世界网络。和现有模型不同，该模型可根据需求构造常数度或非常数度网络，且生成网络不仅具有较高的聚集系数和低的网络直径，而且是节点对称的，在通信网络、P2P覆盖网络等实际领域的拓扑结构设计中具有重要应用。2.目前现实世界中很多网络的幂指数在2和3之间，很多研究直接假设是大于2的，但是这种假设与事实并非完全符合，因为也有很多网络幂指数不大于2，这些网络是否属于一类完全特殊的网络，换句话说，幂指数的不同是否会导致网络呈现不同的性质，这个问题并没有得到应有的重视。本文对无标度网络的幂指数的取值与网络拓扑性质的关联进行了深入探讨，以2为临界点，比较了γ <2与γ≥2的无标度网络的关于最小度节点数、平均度的拓扑性质，得到了一些新的有意义的结论，当γ≥2时，网络中最小度的节点相当多，其数量与节点规模N是同阶，而且网络平均度较小，其大小是阶的；当1<γ <2时，这些性质消失，网络的平均度是发散的，最小度的节点数量占总节点的比例明显减少，网络中具有较多的Hub节点。3.尽管很多研究关注无标度网络的性质，但是缺少对度序列长度的分析与讨论。本文讨论了无标度网络的一般特性，指出当γ>1时，最小度的节点数n k1能够被k1γ， k2γ... klγ的最小公倍数整除，而且网络中度序列长度是log N阶的,这里网络大小为N，网络节点的度序列为k1<k2<...kl。我们通过计算大量的现实网络的度序列长度验证了该结论，该性质可进一步应用于无标度网络的搜索，改进最大度的搜索算法。4.本文根据无标度网络的度分布规律，利用度序列长度的性质，提出了一种基于度序列增长的无标度网络模型。与现有BA动态演化模型不同，网络的增长不是简单基于节点和边的增长，而是按照预先设定的度分布完成。本文详细介绍了两个按度序列增长的网络模型示例，度分布为素数的无标度网络和度分布为等比数列的无标度网络，包括模型定义，模型的性质分析以及相关的网络实例。本文的方法为网络建模的研究提供了一个新的思路，通过对一些初始参数的设置，可以生成一类幂指数可调的符合特定度分布的无标度网络。5.本文最后给出了对称性小世界模型的应用，通过恰当地扩展极小Cayley图-蝶图，提出了一种新的P2P覆盖网络GBFnet （Generalized ButterFly Network），该网络兼具对称性和小世界特性，网络的节点和数据项映射到基于扩展的蝶图的标识符空间，节点的逻辑连接由确定性的算法进行控制和维护，并且在一定程度上模拟人类的社交网络，提供了结构化的分组方式，理论分析和实验结果表明，该网络可以基于较小的路由表获得较好的查询性能，同时具有优良的路由容错性和健壮性。