第一节 网络节点重要性指标国内外研究进展

网络节点重要性的度量，是社会网络分析和系统科学研究领域一个引人关注的问题，许多学者从不同角度对此问题进行了研究，提出了各种指标对此进行了度量。文献中常见的无尺度网络（Baratasi, A. L., 1999）、“小世界”理论（Watts, D. J., 1998）、社交网络（Dodds, P. S., et al., 2003）、生物网络（Girvan, M., 2002）、交通网络（Holms, P., 2003;Crucitti, P., et al., 2005; Porta, S., et al., 2005）、恐怖分子组织网络（Drˇazen, P., 2005）等研究领域，都从不同角度讨论了节点对网络的影响。

社会网络分析对这一问题的研究始于20世纪40年代末，其主流方法均基于这样一个假设，即节点的重要性等价于该节点与其他节点的连接而使其具有的显著性（Knoke, D., et al., 1983）。这些方法的基本思路是从网络中寻找某种有用的属性信息（如度、最短路、路径中包含的信息量等）来凸显网络节点间的差异，也就是说，充分地反映出节点在网络中的位置特性，放大网络节点的显著性以定义节点的重要性。

已提出的指标分为节点中心度（Centrality）和声望（Prestige）两大类，度量方法主要包括节点的度（Degree）、接近度（Closeness）、介数（Betweenness）、信息中心度（Information Centrality）、特征向量（Eigen-vector）和累计提名（Cumulated Nomination）等。

最简单的节点中心度指标是节点的度，直接利用与节点相邻接的边数来度量节点的重要性，这显然存在很多不足之处；节点的接近度被定义为该节点到其他所有节点距离之和的倒数，反映了节点在网络中的居中程度（Wasserman, S., 1994）; Freeman, L. C.（1979）提出的介数指标反映了节点对其他节点的控制作用；Stephenson, K．和Zelen, M.（1989）提出的信息中心度指标类似于节点的接近度，但在计算时充分考虑了所有路径中传递的信息流；Bonacich, P.（1972, 1987）提出的特征向量指标则是从网络成员的地位或名望角度考虑，将单个成员的名望看成所有其他成员名望的线性组合从而得到一个线性方程组，该方程组的最大特征值所对应的特征向量就是各个节点的重要性指标；Poulin, R．等（2000）在对Bonacichi, P．求解特征向量的映射迭代方法改进的基础上，提出了收敛速度更快、更稳定而且适用于大网络和多分支网络的累计提名指标。

以上指标中，特别值得关注的是介数指标，由于其在复杂网络、社会网络分析等领域的重要作用，与其相关的指标已经发展成了一个介数指标族。最早的介数指标被定义为网络中通过节点的最短路数目占所有最短路的百分比。在信息完全按照最短路径传播的网络中，介数指标刻画了信息流经给定节点的可能性，可以用来度量节点对网络中信息传播的控制和影响；Newman, M. E. J.（2001）和Brandes, U.（2001）分别提出了计算介数的有效算法，对于具有m条边和n个节点的网络，所有节点的介数都可以在O（mn）的时间内求得，这也大大拓宽了介数的应用范围。但在大多数现实世界的网络中，信息并不是沿最短路径传播的（Stephenson, K. A., 1989），由于无法获得网络的所有结构信息，信息往往只是根据传递节点周围的部分结构信息选择路径，因此路径的选择具有一定的随机性（Milgram, S., 1967; Travers, J., 1969）。针对此问题，Freeman, L. C.等（1991）又提出了流介数指标（flow betweenness），利用最大流的概念来度量所有传播路径的贡献；Newman, M. E. J.（2005）提出了随机行走介数指标（random-walk betweenness），利用统计方法来研究部分结构信息下网络节点重要性的度量；Noh, J. D．和Rieger, H.（2002）提出了随机行走中心度（random-walk centrality），通过度量消息在网络中传播的速度来反映网络节点的重要性。

近年的研究又有了新突破。Kitsak, M．等人（2010）提出同时考虑节点度数和位置的“k-壳分解法”（k-shell decomposition）, Hu, Q．等人（2013）将“k -壳分解法”与社区结构相结合，对其进行了改良；Chen, D. B．等人（2012, 2013）提出了一种基于半局部信息的半局部中心性节点重要性排序方法，其计算复杂度随网络规模线性增长，只需非常少的计算时间，就能够得到远好于度中心性和介数中心性的排序结果；Gao, C．等人（2013）用“D-S证据理论”将此方法推广到了含权网络；秦李等（2015）结合改进的主成分分析法和TOPSIS法提出了一种新复杂网络中的节点重要性的综合评价方法，并对ARPA网络和美国航空网络进行了实验分析；任卓明等（2012）提出了基于度与集聚系数的网络节点重要性度量方法，并分析了复杂网络中最小K-核节点的传播能力。

社会网络分析方法是在保证网络整体性的前提下进行指标研究的，而系统科学的研究方法则是用网络的连通性来反映系统某种功能的完整性，通过度量节点删除对网络连通的破坏程度来反映网络节点的重要性。

这种节点删除的思想最早体现在图论中反映图的连通程度的指标连通度上（Bondy, J. A., 1981；吴望名、李念祖，1984），但具有相同连通度的两个图的连通程度实际上仍可能有相当的差异。为此，Chvatal, V.（1973）引入了图的坚韧度（toughness）概念；欧阳克智等（1993）提出了图的相对断裂度；许进等（1993）提出的系统的核与核度理论是这方面主要的研究成果。该理论将系统抽象成网络，定义系统的“核”为那些对系统功能来讲具有重要的或支配性作用的，且一旦遭到破坏会使整个系统瘫痪或受到重大损失的节点或节点的集合，而“核度”的计算则通过点断集和连通分支数来实现。其后，寿纪麟、李飞（1996）提出了针对节点加权连通网络系统的点权核与点权核度；谢政、汤泽莹（1997）提出了模糊连通度与模糊核度，对核与核度理论进行了扩展。这些参数较连通度而言更进了一步，但还存在不足，有些图的这些参数相同，但连通程度不同。为了解决这个矛盾，许进等（1994）又提出了核冠与核能量的概念；Cozzens等（1995）提出了韧性度的概念；王志平、赵连昌等（1999, 2001）提出了离散度的概念；另外考虑到连通分支在大小和形状上的差异，席酉民和唐方成（2002）提出了立体多核网络的定义，将核度定义为立体多核网络中核的拓扑势的测度，但没有给出核度的数学表达式或拓扑势测度的具体方法；李鹏翔、任玉晴、席酉民（2004）用节点被删除后形成的所有不连通节点对之间的距离（最短路）的倒数之和来计算指标的大小，对这一思想进行了量化。

综上所述，研究节点重要性的方法主要有两类。一类是社会网络分析方法，将节点的“重要性等价为显著性”，对指标的研究不破坏网络的整体性且通常不考虑节点集的重要性；另一类是节点删除的研究方法，将节点的“重要性等价为该节点被删除后对网络的破坏性”，指标的研究实际上考虑的是节点删除前后图的连通状况发生的变化。

但以上这些方法考虑的都是节点对于整个网络的重要性，没有考虑节点对于某个目标节点集的重要性。因此所求解的问题只能是静态的，这两类方法关注的始终是整个网络，而没有考虑问题的动态特性，即在解决问题的过程中，在不同的阶段或不同的子问题中关注的中心往往具有目标性和局域性。应急物流配送是这方面最典型的例子：在一次出救行车任务中，配送车辆不需要关注整个区域路网海量的道路细节，其关心的只是对于此次行车目标节点集重要的那部分道路地图（即“出救点—应急物资储备中心—灾区需求点”及其沿线的道路网络），而且突发事件中道路网络节点常因次生衍生灾害损毁无法通行，因此救援人员在应急物流配送的不同阶段所关心的目标集也是动态变化的。为此，必须寻找度量节点对于目标节点集重要性的新指标，从而将节点对于目标节点的连通关系从节点对于整个网络的连通关系中分离出来。