论文部分内容阅读
近年来,图论和复杂网络的相关研究受到了越来越多领域学者的广泛关注,包括物理、化学、计算机科学、数学、生物学、经济学等,而相关研究也逐渐从单学科向多学科交叉转变。与此同时,网络分析作为映射和度量网络实体及其连接关系的关键工具,也得到了充分的研究,为复杂网络提供了一个可视化的和数学抽象上的视角。由于复杂网络自身的复杂性,研究如何根据节点在网络中的拓扑结构和相关信息,确定其在网络中的地位,从而识别出哪些表现突出、处于中心地位的节点,对社会、医药、信息技术、经济管理等领域都具有十分重要的应用价值。由于对节点中心度的理解以及偏重不同,到目前为止还没有一种统一的方法对其进行评估。而且,对现有网络节点中心度的研究成果进行检索的结果显示,目前国内外对复杂网络节点中心度评估的研究中尚没有一种仿生智能的解决方案。根据最近的研究发现,一种名为多头绒泡菌(Physarum polycephalum)的单细胞生物在网络设计、分析与优化方面展现出了惊人的智能特性。在生物实验中,它所设计出的连接各食物源的觅食管道网络在成本、效率和容错性等方面都堪比实际的东京铁路网络。因此,本文提出了基于智能仿生对象——多头绒泡菌的网络优化机理,构造复杂网络节点中心度评估算法的新思路。本文首先研究了多头绒泡菌在其自身觅食网络中所展现的智能行为,重现了已有的路径寻优模型,并在实验验证过程中发现了现有模型的不足,提出了改进方案;然后,结合复杂网络节点中心度评估的应用背景,基于改进的仿生算法提出了三种不同的评估算法。本文的主要工作包括以下几个方面:1.研究快速优化机制基于现有多头绒泡菌路径寻优模型存在冗余计算问题,本文通过观察模型运行过程,总结并抽象出了快速优化的启发式规则,提出了快速多头绒泡菌算法,一定程度上减少了冗余的计算过程,提高了算法运行效率。2.扩展有向网络应用针对原模型在有向网络中不适用的问题,本文考虑到原模型与电路系统在理论基础上的相似性,以及电路系统中二极管处理有向问题的能力,借鉴了模拟电路中二极管控制电流流向的方法,在原模型中加入模拟电路分析模块,提出了有向多头绒泡菌扩展算法,使其能够应用于有向网络中。3.提出完整的多头绒泡菌最短路径算法由于有向多头绒泡菌算法中借助了模拟电路分析模块,使得整体算法流程较为复杂,本文在进一步分析该模块内在机理的基础上,提出了有效的替代机制,并进一步完善算法流程,提出了完整的多头绒泡菌最短路径算法,使其在有向和无向网络中都适用。4.提出基于PASP的初步评估算法在建立复杂网络与多头绒泡菌管道网络对应关系的基础上,结合节点中心度评估的应用背景,提出了初步的多头绒泡菌中心度评估指标CP,该指标不仅考虑了最短路径对节点中心度的影响,同时还包括了次短路径在节点中心度评估中的贡献。5.提出基于PASP的改进评估算法由于初步评估算法的计算复杂度较高,随着问题规模的扩大,该算法将不再适用。为此,本文借鉴了LeaderRank算法中地节点的思想对其进行改进,提出了改进的评估指标CIP,将外层循环的复杂度从O(n2)降低至O(n),大大提高了算法性能。6.提出PhysarumSpreader算法基于针对非加权网络的LeaderRank算法,本文结合了仿生对象多头绒泡菌的网络优化机理,提出了扩展的PhysarumSpreader算法,使其能够有效地应用于加权网络。在此基础上,本文还引入加权传染病传播模型,验证了PhysarumSpreader算法所给出的中心度值较高的节点在信息传播方面具备较好的性能。