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

龙源期刊网浅议几种复杂网络节点重要度分析的中心性方法作者：张廷萍来源：《价值工程》2016年第14期摘要：网络节点重要度分析是研究和分析复杂网络的一种非常重要的方法。识别有影响力的节点比较常用的是利用中心性方法解决这个问题。本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。Abstract：Tostudyandanalyzecomplexnetworks，identifyinginfluentialnodesisaveryimportantmethodology.Manycentralitymeasureshavebeenproposedtoaddressthisissue.Inthispaper，centralitymeasurestoidentifyinfluentialnodesincomplexnetworksaredescribed.Numericalexamplesshowtheanalysisandcomparisonofseveralmethodstoidentifyinfluentialnodes.关键词：复杂网络；重要节点；中心性方法Keywords：complexnetworks；identifyinfluentialnodes；centralitymeasures中图分类号：TN711文献标识码：A文章编号：1006-4311（2016）14-0209-020引言当前，从疾病传播网络到全球医疗诊断网络，从电力网到交通网络，从交际网络到社会关系网络，复杂网络已经渗透到人类社会生活，给我们带来了极大的便利，但是，同时也产生了诸如交通瘫痪、谣言快速传播等不容忽视的负面冲击。因此，对复杂网络进行深入的研究和分析以方便对其负面影响进行预测、避免和控制是刻不容缓的。由于网络中的节点存在着许多的全局信息和局部信息，因此对有影响力节点的识别即节点重要度分析是一个非常重要的方向，在许多领域也得到了广泛的应用，如攻击防御、谣言传播控制、搜索排名等。目前，已提出多种复杂网络节点中心性方法解决节点重要度分析问题。本文介绍了几种常见的进行网络节点重要度分析的中心性，并通过算例对几种方法进行了分析比较。1基本理论复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构，在数学上可以抽象为一个由点集V和边集E组成的图G=（V，E）。如图1所示，是具有11个节点12条边的简单无向无权网络图。为简化问题，本文仅针对无向无权网络进行研究。2节点重要度分析方法龙源期刊网所谓的重要节点是指与网络其他节点相比，能在更大程度上影响网络的结构与功能的一些比较特殊的节点。一般而言，一个网络中的重要节点的数量都是比较少的，但其影响却可以快速地波及到网络中的大部分节点[1]。为了解决识别网络节点重要度问题，已有多种不同的网络节点中心性方法。各种方法利用计算出的中心性值进行排序，确定节点重要程度。2.1度中心性（Degreecentralitymeasure）节点i的度中心性[2]，用CD（i）表示，定义为：其中i为当前所求节点，j表示其他所有的节点，N是网络节点总数，xij表示i与j之间有连接关系。两个节点之间相连，则为1，反之则为0。2.2介数中心性（Betweennesscentralitymeasure）节点i的介数中心性[3]，用CB（i）表示，定义为：其中gst表示从节点s到节点t的最短路径的数目，gst（i）表示从节点s到节点t所有最短路径中经过节点i的最短路径的数目，是用来对介数中心性值进行归一化，n为网络节点的数目。其中表示节点i和节点j之间的最短距离dij，其定义如下：d（i，j）=min（xih+…+xhj）（3）2.3接近中心性（Closenesscentralitymeasure）节点i的接近中心性[3]，用CC（i）表示，定义为：2.4融合中心性（Compromisecentralitymeasure）节点i的融合中心性[8]，用CED（i）表示。其来源于对度中心性、接近中心性和介数中心性的值的融合计算，具体计算方法步骤如下：①设CD（i），CC（i）和CB（i）分别为节点i的度中心性、接近中心性和介数中心性的值，分别进行归一化，计算方法为：其中i表示节点i的归一化中心值，N为复杂网络节点数。②然后整合节点i的归一化中心值，得到CED（i）。设分别为别为节点i的度中心性、接近中心性和介数中心性归一化中心值。利用欧拉公式得到的融合中心性的值定义为：其中n为网络节点的数目。龙源期刊网中心性（TOPSIScentralitymeasure）节点i的TOPSIS中心性[7]，用CTC（i），是利用度中心性、接近中心性和介数中心性的值结合逼近最优解的偏好顺序法（TOPSIS）的方法，具体计算方法如下：①计算出各节点度中心性、接近中心性和介数中心性的值，并利用公式（5）进行归一化，再进行加权计算，得到加权归一化值；②计算理想最优解A+和最劣解A-，具体说就是步骤二中的最大值和最小值；③根据公式（7）计算节点与理想最优解和最劣解之间的相似紧密度即节点i的TOPSIS中心性值。CTC（i）=，i=1，…，m（7）其中S和S分别表示节点i与理想最优解和最劣解之间的距离。3算例如图1为有11个节点，12条边的无向无权网络。利用前述各中心性定义，分别计算复杂网络所有节点的度中心性、接近中心性和介数中心性、融合中心性和TOPSIS中心性的值，其中计算TOPSIS中心性时假定权重都相等，即都为，计算结果如表1所示。从表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结论本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。使用不同的中心性方法，可以得到不同的节点重要度结果。度中心性是在网络分析中刻画节点中心性的最直接度量指标，一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。接近中心性是刻画节点通过网络到达其它节点难易程度的指标，相比节点度指标更能反映网络的全局结构。节点的接近度越高，那么离其它节点越近，传播难度越低，所需借助的节点越少，反之亦然。网络上传输时负载最重的节点是处于网络中心位置的节点，也就是经过此点的最短路径条数最多的节点。一个节点的介数越高，该节点在网络中就越重要。融合中心性和TOPSIS中心性是考虑前三种中心性进行综合处理所得，能更有效地识别复杂网络节点重要度。龙源期刊网参考文献：[1]StefnaniaVtali，JamesBGlattfelder，andStefanoBattiston.Thenetworkofglobalcorporatecontrol.PloSOne，6（10）：e25995.2011.[2]PhillipBonacich.Factoringandweightingapproachestostatusscoresandcliqueidentification[J].JournalofMathematicalSocioogy.1972，2（1）：113-120.[3]LitonCFreeman.Centralityinsocialnetworksconceptualclarification[J].Socialnetworks，1979，1（3）：215-239.[4]Zhang，Tingping，Liang，Xinyu，ANovelMethodofIdentifyingInfluentialNodesinComplexNetworksBasedonRandomWalksJournalofInformationandComputationalScience，v11，n18，p6735-6740，December10，2014.[5]TingpingZhang，BinFang，andXinyuLiang，Anovelmeasuretoidentifyinfluentialnodesincomplexnetworksbasedonnetworkglobalefficiency[J].ModernPhysicsLettersB，2015，29（28）.[6]杜雨弦.复杂网络中节点重要度评估算法的研究[D].重庆：西南大学，2015.[7]张廷萍.一种新的复杂网络节点重要度分析方法[J].赤峰学院学报（自然科学版），2016（8）.龙源期刊网