论文部分内容阅读
复杂网络是近年兴起的一门交叉学科,由于其研究对象的普遍性和多样性,受到国内外学者的广泛关注。任何一个复杂系统都可以抽象成由相互作用的个体构成的网络,因此可以说复杂网络遍及了自然界和社会的各个角落。对复杂网络的研究不仅对人们的生活具有现实意义,而且对了解自然界和社会的发展具有深远的科学和社会意义。 研究复杂网络的最终目标是理解网络结构和网络上的各种动力学过程的相互作用:网络的结构影响发生在其上的动力学过程,同时网络的演化动力学过程决定了网络的结构。我们对网络中耦合同步过程进行了深入的研究,在理解同步实现原理的基础上,对经典的Kuramoto振荡器模型进行了改进,改进后的模型更容易达到同步中的集群现象。针对这一特性我们对改进的模型在不同的应用上进行了研究。本文的主要内容如下: 1.离散相位振荡器模型解决图着色问题。图着色问题是经典的组合优化问题,目前对它的研究主要集中在启发式算法和遗传算法上,启发式算法虽然时间很短,但着色数不是最低的,而遗传算法在着色数上达到最低,但复杂度很高。针对这两种算法的不足,提出了一种基于动力学同步过程的方法。在动力学系统中根据节点之间的连接关系采用不同的耦合强度,并在动力学同步模型的迭代过程中引入了演化策略,即拓扑图和耦合权值根据动力学过程演化,大大提高了效率。最后根据同步中的集群现象对图进行分类并着色,即同一类中节点的相位值趋于一致,而不同类中的相位值彼此远离。 2.离散相位振荡器模型解决聚类问题。目前对聚类问题的研究主要是从基于距离、基于密度和基于连接三个角度出发,前两者普遍使用欧氏距离测量,但欧氏距离只反映数据的局部性质(直线上距离最短),无法反映出数据的全局性质,聚类效率不佳。针对该问题,我们提出了一种新的距离测量,即流形距离测量。流形距离测量能够很好地反映出数据的全局性质。我们并对该流形距离测量在动力学同步模型上进行了仿真实验并与其它聚类算法进行了对比,表明了该流形距离测量和网络动力学同步模型在聚类方面都有很好的发展前景。 3.离散相位振荡器模型解决社区检测问题。针对网络中社区结构的特征,我们提出了一种基于同步过程的动力学模型。该动力学模型加强了有连接关系的节点间的相互作用,同时消弱没有连接关系的节点间的相互影响,在社区检测方面有很好的应用前景。