基于凝聚度和紧密度的网络节点重要性排序

2018-10-23张惠玲

计算机与数字工程 2018年10期

张惠玲

（西安航空学院理学院西安 710077）

1 引言

随着信息技术的迅猛发展，人类进入了网络时代，各种网络在结构、节点等方面具有一定的复杂性，在现实生活中受到各种因素的影响，因此它们也被称为复杂网络。作为复杂网络的一个研究热点，重要节点的排序引起了人们的极大关注。所谓重要节点指的是相对于网络中的其他节点，能够在更大程度上影响网络的结构与功能的一些特殊节点［1］。

人们一般从网络的局部属性、全局属性、网络位置以及随机游走等四个角度出发来分析网络节点的重要性，从而给出了一系列的评价指标［2］。基于局部属性的节点重要性排序指标主要考虑节点的自身信息和其相邻节点的信息，如节点的度。在文献［3］中，王建伟等认为节点的度及其相邻节点的度与节点的重要性呈正相关。在文献［4］，任卓明等考虑了相邻节点的个数以及相邻节点之间的紧密程度，给出了一种新的评价方法。在文献［5］中，定义最重要的节点是该节点在失效的情况下，相应地生成树数目最小的节点记为最重要节点。在文献［6］中，通过最短路径结束的方法确定网络中的重要性节点。文献［7］利用节点收缩的方法，通过删除待分析节点的邻接点来判断节点的重要度，该方法简化了计算的复杂度，但没有考虑节点删除后会导致网络结构变化，从而引起节点重要性的变化。文献［8］提出了基于网络性能梯度的节点重要性评价方法。在文献［9］中，将节点的度平均分配到各个相邻节点后，又结合介数构造了重要度评价矩阵，由此给出了节点重要度评价方法。针对文献［9］中节点度平均分配的不足，文献［10］对其进行了改进，构造了一种新的评价矩阵，优化了评价方法。文献［11］～［13］分别从不同的角度构建了网络节点的重要性评价指标评价，然后使用SIR模型做了验证，并且验证了方法的有效性。

基于全局属性的指标主要考虑全局的信息，这些指标一般准确性较高，如在文献［11］中，在万有引力公式的启发下，考虑节点的度和距离构建了节点重要度评价指标。在文献［12］中，提出一种基于距离的染色方法来判断网络节点的重要性。文献［13］中，考虑边权重，对K-shell指标做了改进，构建了一种新的指标确定节点的重要性。文献［14］中，通过定义限制度效率和等级度效率，构建节点的重要性评价矩阵，从而判断通信网中节点的重要性。文献［15］中，从网络的备选路由数、网络被分割的程度和网络性能三方面考虑了节点的重要性。

紧密度考虑了节点与其它节点之间的最短距离的平均值，发现距离越大，该节点对其他节点的影响力越低，于是将紧密度定义为平均距离的倒数，表明节点的紧密度越大，该节点越重要。在本文中，我们首先定义了网络节点的凝聚度，是一种新的刻画网络局部属性的节点重要性排序指标，而网络节点的紧密度是一种基于网络全局属性的节点重要性排序指标，然后将两个指标结合起来定义了网络节点的重要度指标，给出了相应的算法及其复杂性，最后通过实验分析验证了该方法的有效性。