浅议几种复杂网络节点重要度分析的中心性方法5页

1、龙源期刊网 浅议几种复杂网络节点重要度分析的中心性方法作者：张廷萍来源：价值工程2016年第14期摘要：网络节点重要度分析是研究和分析复杂网络的一种非常重要的方法。识别有影响力的节点比较常用的是利用中心性方法解决这个问题。本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。Abstract： To study and analyze complex networks， identifying influential nodes is a very important methodology. Many c

2、entrality measures have been proposed to address this issue. In this paper， centrality measures to identify influential nodes in complex networks are described. Numerical examples show the analysis and comparison of several methods to identify influential nodes.关键词：复杂网络；重要节点；中心性方法Key words： complex

3、networks；identify influential nodes；centrality measures中图分类号：TN711 文献标识码：A 文章编号：1006-4311（2016）14-0209-020 引言当前，从疾病传播网络到全球医疗诊断网络，从电力网到交通网络，从交际网络到社会关系网络，复杂网络已经渗透到人类社会生活，给我们带来了极大的便利，但是，同时也产生了诸如交通瘫痪、谣言快速传播等不容忽视的负面冲击。因此，对复杂网络进行深入的研究和分析以方便对其负面影响进行预测、避免和控制是刻不容缓的。由于网络中的节点存在着许多的全局信息和局部信息，因此对有影响力节点的识别即节点重要度分

4、析是一个非常重要的方向，在许多领域也得到了广泛的应用，如攻击防御、谣言传播控制、搜索排名等。目前，已提出多种复杂网络节点中心性方法解决节点重要度分析问题。本文介绍了几种常见的进行网络节点重要度分析的中心性，并通过算例对几种方法进行了分析比较。1 基本理论复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构，在数学上可以抽象为一个由点集V和边集E组成的图G=（V，E）。如图1所示，是具有11个节点12条边的简单无向无权网络图。为简化问题，本文仅针对无向无权网络进行研究。2 节点重要度分析方法所谓的重要节点是指与网络其他节点相比，能在更大程度上影响网络的结构与功能的一些比较特殊的节

5、点。一般而言，一个网络中的重要节点的数量都是比较少的，但其影响却可以快速地波及到网络中的大部分节点1。为了解决识别网络节点重要度问题，已有多种不同的网络节点中心性方法。各种方法利用计算出的中心性值进行排序，确定节点重要程度。2.1 度中心性（Degree centrality measure）节点i的度中心性2，用CD（i）表示，定义为：其中i为当前所求节点，j表示其他所有的节点，N是网络节点总数，xij表示i与j之间有连接关系。两个节点之间相连，则为1，反之则为0。2.2 介数中心性（Betweenness centrality measure）节点i的介数中心性3，用CB（i）表示，定义为

6、：其中gst表示从节点s到节点t的最短路径的数目，gst（i）表示从节点s到节点t所有最短路径中经过节点i的最短路径的数目，是用来对介数中心性值进行归一化，n为网络节点的数目。其中表示节点i和节点j之间的最短距离dij，其定义如下：d（i，j）=min（xih+xhj）（3）2.3 接近中心性（Closeness centrality measure）节点i的接近中心性3，用CC （i）表示，定义为：2.4 融合中心性（Compromise centrality measure）节点i的融合中心性8，用CED（i）表示。其来源于对度中心性、接近中心性和介数中心性的值的融合计算，具体计算方法步骤

7、如下：设CD（i），CC （i）和CB （i）分别为节点i的度中心性、接近中心性和介数中心性的值，分别进行归一化，计算方法为：其中i表示节点i的归一化中心值，N为复杂网络节点数。然后整合节点i的归一化中心值，得到CED（i）。设分别为别为节点i的度中心性、接近中心性和介数中心性归一化中心值。利用欧拉公式得到的融合中心性的值定义为：其中n为网络节点的数目。2.5 TOPSIS中心性（TOPSIS centrality measure）节点i的TOPSIS中心性7，用CTC（i），是利用度中心性、接近中心性和介数中心性的值结合逼近最优解的偏好顺序法（TOPSIS）的方法，具体计算方法如下：计算出各

8、节点度中心性、接近中心性和介数中心性的值，并利用公式（5）进行归一化，再进行加权计算，得到加权归一化值；计算理想最优解A+和最劣解A-，具体说就是步骤二中的最大值和最小值；根据公式（7）计算节点与理想最优解和最劣解之间的相似紧密度即节点i的TOPSIS中心性值。CTC（i）=， i=1，m（7）其中S和S分别表示节点i与理想最优解和最劣解之间的距离。3 算例如图1为有11个节点，12条边的无向无权网络。利用前述各中心性定义，分别计算复杂网络所有节点的度中心性、接近中心性和介数中心性、融合中心性和TOPSIS中心性的值，其中计算TOPSIS中心性时假定权重都相等，即都为，计算结果如表1所示。从表

9、1可知，根据度中心性，各节点的重要度排序结果为：4、75、61、102、3、8、9、11；根据接近中心性，各节点的重要度排序结果为：657104111、9、83、2；根据介数中心性，各节点的重要度排序结果为：67541012、3、8、9、11；根据融合中心性，各节点的重要度排序结果为：76451018、9、112、3；根据TOPSIS中心性，各节点的重要度排序结果为：76451018、9、112、3。4 结论本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。使用不同的中心性方法，可以得到不同的节点重要度结果。度中心性是在网络分析中刻画节点中心性的

10、最直接度量指标，一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。接近中心性是刻画节点通过网络到达其它节点难易程度的指标，相比节点度指标更能反映网络的全局结构。节点的接近度越高，那么离其它节点越近，传播难度越低，所需借助的节点越少，反之亦然。网络上传输时负载最重的节点是处于网络中心位置的节点，也就是经过此点的最短路径条数最多的节点。一个节点的介数越高，该节点在网络中就越重要。融合中心性和TOPSIS中心性是考虑前三种中心性进行综合处理所得，能更有效地识别复杂网络节点重要度。参考文献：1StefnaniaVtali，James B Glattfelder， and St

11、efano Battiston. The networkof global corporate control. PloS One， 6（10）：e25995.2011.2Phillip Bonacich. Factoring and weighting approaches to status scores and clique identificationJ. Journal of Mathematical Socioogy. 1972，2（1）：113-120.3Liton C Freeman. Centrality in social networks conceptual clari

12、ficationJ. Social networks， 1979，1（3）：215-239.4Zhang， Tingping， Liang， Xinyu， A Novel Method of Identifying Influential Nodes in Complex Networks Based on Random Walks Journal of Information and Computational Science， v 11， n 18， p 6735-6740， December 10， 2014.5Tingping Zhang， Bin Fang， and XinyuLiang ，A novel measure to identify influ