论文部分内容阅读
复杂网络将宏观上各类复杂多样的实际系统抽象为“图和网络”,是理解和认识世界进而解决现实问题的重要工具。在复杂网络中能够在更大程度上影响网络结构和功能的节点被称为“关键节点”,识别网络中的关键节点并对其进行有效利用能够以最小代价实现对网络的有效控制,因此精确挖掘网络中的关键节点成为网络科学研究中的一个重要问题。现如今,用于挖掘关键节点的算法大多基于链路关系单一化的单层网络模型。然而,现实世界的各类复杂系统往往都存在着千丝万缕的联系,如一种传染病的流行就足以对交通、餐饮、金融等诸多领域造成影响。上述实例表明现实世界的大多数网络需要结合起来整体研究,因此构建贴合现实数据的多层网络模型具有一定的理论和现实意义。由于多层网络结构更加多样化,且存在复杂的层间影响,传统单层网络中的关键节点识别算法已不再适用于多层网络。基于上述分析,本文主要从多层网络模型的构建和关键节点识别两个方面展开研究,具体内容如下:(1)针对现有多层网络模型无法对层间节点数量不同的多层系统做出精确描述和分析,构建了一种超互联多层网络模型。该模型充分考虑了不同网络间拓扑结构的异质性,并根据网络间的交互建立了层间链路。基于所构建的模型,提出一种基于有偏游走的关键节点识别算法(Multilayer Biased Walk Rank,MBW-Rank),该算法基于网络的拓扑特性及连通性定义各层的重要性,并将其与节点的层内拓扑属性相结合作为随机游走跳转偏差。MBW-Rank能有效地综合各层网络的信息,同时获取节点在各层以及整个网络中的重要度排名。实验比较验证了本文所提方法的准确性和有效性,表明超互联多层网络模型是对由多个具有不同连接关系、不同节点数量的子网络相互作用构成的系统的精确描述,且MBW-Rank能有效挖掘出该网络中起关键作用的“桥接节点”,为多层网络中的研究工作提供策略上的指导和帮助。(2)针对现有研究对时序网络建模时存在忽略时间信息、未考虑时间切片间的交互关系进而影响关键节点识别的准确性的问题,构建了一种多层时序网络模型。该模型结合多层网络分析法,完整揭示了时序网络基于时间的结构演变及其动力学过程。基于所构建的网络模型,提出了一种基于节点相似性有偏游走的关键节点识别算法(Multilayer Temporal Biased Page Rank,MTB-PR)。该算法根据时间相继性提出了相邻层间节点的单向影响作用,并将其与层内节点相似性指标相结合来区分节点的不同影响力。MTB-PR可以获得节点在不同时刻的重要性排名并得到节点的重要性随时间变化的轨迹,能够有效挖掘不同时刻中的关键节点。此外,本文将模型和算法应用于真实网络中,实验数据结果表明了该方法的有效性和可行性。