论文摘要
由于计算机、互联网和信息技术的迅猛发展,使得人们比以往任何时候都能够更快捷获取所需的各种信息和资源,促使人类进入了网络信息时代。网络无处不在,如何用定量分析的方法识别超大规模网络中哪些节点最重要,或者评价某个节点相对于其他节点的重要程度。这是复杂网络研究中亟待解决的重要问题之一。本文分别从网络结构和传播动力学的角度,对现有的复杂网络中节点重要性排序方法进行了系统的回顾。首先介绍了基于网络结构的节点重要性排序度量指标,这类指标主要从网络的局部属性、全局属性、网络的位置和随机游走等四个方面展开,同时对这些方法的优缺点及适用范围进行了分析。然后分析了传播动力学与节点重要性度量指标之间的关系,并指出了这一领域中几个有待解决的问题及可能的发展方向。最后本文分别从以下三个角度提出度量节点重要性的新指标。1.复杂网络中最小k-核节点的传播能力分析。采用k-核分解方法将网络划分为不同等级层次的社团,筛选出最小k-核节点集合,这类节点往往在网络总节点数中占很大比例,然而这类节点的传播能力却无法区分,于是利用该类节点邻居集中的最大k-核值,度量其传播能力;通过大量真实网络的SIR传播仿真,分别比较度指标、介数指标和新指标的表现。结果表明该新指标更能够准确度量最小k-核节点的传播能力。2.基于k-核与距离的节点传播影响力排序度量方法。节点在网络中的k-核位置是影响节点重要性的主要因素。然而,k-核指标赋予大量节点以相同的值,从而导致k-核指标无法衡量这些相同节点的重要性,因此有必要对这些相同k-核节点的重要性进行度量。因此认为节点的传播影响力不仅与节点本身的k-核值有关,还和目标节点与最大k-核值节点间的距离相关。基于这个观点,设计了一个新指标对网络中所有节点进行全局排序。为了验证新指标的准确性,采用SIR传播模型对不同的真实网络和改进BA网络模型进行仿真,结果表明该方法比度、紧密度、k-核以及混合度分解法的结果都要好。3.基于度与集聚系数的网络节点重要性度量方法研究。节点的度和集聚系数信息对刻画其重要性都具有十分重要的意义。研究者们普遍运用度或集聚系数来度量节点的重要程度,然而度指标只考虑节点自身邻居个数而忽略了其邻居之间的信息,集聚系数只考虑节点邻居之间的紧密程度而忽略了其邻居的规模。综合考虑节点的邻居个数,及其邻居之间连接的紧密程度,提出了一种基于邻居信息与集聚系数的节点重要性评价方法。对美国航空网络和美国西部电力网进行的选择性攻击实验表明,采用该方法的效果较k-核指标可以分别提高24%和112%。该节点重要性度量方法只需要考虑网络局部信息,因此非常适合于对大规模网络的节点重要性进行有效分析。总之,节点重要性排序指标在涉及网络结构信息时,都是从某一个角度对于网络的某一方面的结构特点进行刻画,如果目标网络的结构在该方面特征显著,即可得到较好的效果。由于网络结构的复杂性,一种节点重要性指标不能同时应用于多种不同类型的网络。同时,复杂网络中节点重要性度量指标的准确性,又与不同的传播模式是密切相关。因此需要同时考虑网络的拓扑特点和传播动力学机制,提出度量节点重要性新指标。这将是我们下一步的研究目标。