论文部分内容阅读
复杂网络是复杂系统的抽象,人类社会和自然界中的诸多系统都以网络的形式存在,这些网络错综复杂,变化多样。比如生物网络、神经网络、人事关系网络、计算机网络等。其中,复杂系统中的个体对应于网络中的节点,系统中个体之间的关系对应于网络中节点之间的边。复杂网络的进一步研究不仅对人们的工作和生活具有十分重要的现实意义,而且对整个人类社会和自然界的发展具有深远的科学意义。 研究复杂网络的最终目的包括:一方面理解网络的拓扑结构如何影响发生在网络上的各种动力学过程,另一方面理解网络的演化动力学过程如何决定网络的拓扑结构。本文中,我们首先深入研究了网络中的耦合同步过程,并在基于对同步实现原理的理解的基础上,引入了相位聚类模型,该模型很容易达到同步中的集群现象。然后将该相位聚类模型与局部搜索算法相结合用于解决图着色问题。接着我们对动力学过程中的网络博弈,特别是囚徒困境博弈进行了深入的研究,并对博弈数据进行详细的分析。最后将博弈动力学结合进化算法、提出的移动算子用于网络重构。具体工作如下: 1.基于相位聚类模型的图着色混合算法。本文利用相位聚类模型中相位同步的原理和图论中补图的理论,使补图中相邻的节点相位越来越接近,不相邻的节点的相位越来越远离,从而达到初始分组的目的。同时引入了局部搜索算法—桶排序法,将初始分类结果中分类错误的节点重新分类正确,从而提高该算法的正确率。实验表明,只要网络演化的参数设置合理,该算法具有很好的集群效果,而且可以得到正确的着色结果和最优的着色数。 2.博弈动力学和博弈数据分析。本文在理解博弈动力学的基础上,将经典的囚徒困境博弈和网络重构问题联系起来。然后从理论出发,对具体的博弈数据进行分析,说明了什么情况下博弈数据足够重构整个网络,什么情况下博弈数据只能重构网络中的部分边。 3.基于博弈动力学的网络重构。在系统生物学和复杂网络领域中,专家和学者们提出了许多基于观察到的数据进行网络重构的启发式算法。本文是将囚徒困境博弈理论与进化算法相结合来重构网络的拓扑结构,重构时对网络中的节点按照度从小到大的顺序一个接着一个重构。算法首先通过进化迭代产生问题的近似解,然后在此基础上引入了移动算子,用移动算子对近似解进行扩充,使之包含问题的正解,最后用博弈数据对扩充的数据集进行否定,得到问题的唯一解,即网络的真实拓扑结构。实验表明,在重构网络方面,该算法具有很好的效果。