物理学

复杂网络中节点重要性排序的研究进展

刘建国，任卓明，郭强，等

摘要：目的：如何用定量分析的方法识别超大规模网络中哪些节点最重要，或者评价某个节点相对于其他一个或多个节点的重要程度，这是复杂网络研究中亟待解决的重要问题之一。方法：本文首先介绍了基于网络结构的节点重要性排序度量指标，这类指标主要从网络的局部属性、全局属性、网络的位置和随机游走等4个方面展开，同时对这些方法的优缺点及适用范围进行了分析；然后介绍了传播动力学与节点重要性度量指标的关系；最后在总结和展望部分指出了当前面临的问题和可能的发展方向。结果：复杂网络中节点重要性可以是节点的影响力、地位或者其他因素的综合。从网络拓扑结构入手是研究这一问题常用的方法之一。基于网络局部属性的节点重要性排序指标主要考虑节点自身信息和其邻居信息，这些指标计算简单，时间复杂度低，可以用于大型网络。如：节点的度（degree），简单直观，但只反映了节点的局部特征。考虑节点多级邻居信息的指标（local centrality）比度更准确，但是没有考虑邻居之间的紧密程度。基于网络全局属性的节点重要性排序指标主要考虑网络全局信息，如：特征向量（eigenvector）考虑了节点邻居的重要性，但它的缺点是简单的将各节点的拓扑特性进行了线性叠加；Katz指标根据路径长短给邻居赋予不同的权重，区分了不同邻居对节点的不同影响力，但是此方法不易获得权重衰减因子的最优值；紧密度（closeness centrality）指标通过网络对部分节点产生全局影响；Kernel函数法则是通过网络对所有节点产生全局影响；介数（betweenness）指标在识别重要节点时考虑了节点的信息负载能力；可达性（accessibility）指标通过计算节点到达目标节点的可能性来说明节点的重要程度。这些指标一般准确性比较高，但时间复杂度高，且不适用于大型网络。此外，节点重要性还依赖于其在整个网络中的位置，k-核分解考虑了节点在网络中位置的全局特性，该指标时间复杂度低，适用于大型网络，且比度、介数更能准确识别出有影响力的节点，但是不适用于树状网络和 BA网络。混合度分解法（MDD）解决了树状网络和BA网络不适用的问题，但是不容易确定最佳权重因子。基于随机游走的节点重要性排序方法主要是基于网页之间的链接关系的网页排序技术，如PageRank考虑了网络的全局拓扑特性，但当网络中存在孤立节点或社团时会导致排序不唯一。LeaderRank算法解决了这一缺陷，并对网络噪音有更好的容忍性，但不适用于无向网络。HITS算法时间复杂度低，在学术界得到广泛运用，然而它不能识别非正常目的的网页引用，会导致计算结果与实际结果有偏差。除了上述4类方法外，有些方法分别从网络的连通性、节点删除法、边权值、节点效率等视角度量节点重要性。通过分析传播动力学与节点重要性度量指标之间的关系，发现节点重要性排序不仅仅由网络结构决定，还受网络行为传播机制以及节点自身特性的影响。结论：节点重要性排序的指标在涉及网络的结构信息时，都是从某一个角度对于网络的某一方面的结构特点进行刻画，如果目标网络的结构在该方面特征显著，即可得到较好的效果；或在复杂网络环境下，通过节点的网络传播行为的影响力与网络结构关系判断节点的重要性。复杂网络节点重要性的研究还有非常多的问题没有解决，如，（1）节点重要性的定义。节点的重要性含义不同，评价节点重要性排名的结果也不同。（2）各种指标间的内在联系。各种节点重要性排序的方法层出不穷，这些指标从不同视角评价节点重要性。（3）网络结构和网络行为是如何影响节点重要性评价，特别是对研究社会影响力非常有帮助。（4）时变网络中，网络结构是变化的，节点的各种指标具有动态性，如何在这种具有大数据特征的时变网络中对节点重要性排名，这将是一个极具有挑战性的课题。

来源出版物：物理学报, 2013, 62(17): 178901

入选年份：2016