一种新的复杂网络节点重要度分析方法

张廷萍

（重庆交通大学　信息科学与工程学院，重庆　400074）

一种新的复杂网络节点重要度分析方法

张廷萍

（重庆交通大学信息科学与工程学院，重庆400074）

网络节点重要度分析即识别有影响力的节点，是研究和分析复杂网络的一种非常重要的方法.目前比较常用的是利用中心性方法解决这个问题，然而，使用不同的中心性方法，可以得到不同的结果.本文提出了一种新的折衷中心性方法来分析网络节点重要度.利用计算度中心性、接近中心性和介数中心性的值，再进行欧氏距离计算，得到折衷中心性值.最后通过实例分析证明该方法是一种有效的复杂网络节点重要度分析方法.

复杂网络；重要节点；中心性方法

引言

随着小世界网络和无标度网络的提出，复杂网络受到越来越多的重视.在为人类生产生活带来极大便利的同时，复杂网络也产生了不可忽视的负面冲击，如微博谣言的传播及电力网络瘫痪引起的大面积停电等.因此，对复杂网络进行深入的研究和分析以方便对其负面影响进行预测、避免和控制是刻不容缓的.其中，节点重要度分析是一个非常重要的方向.目前，多种复杂网络节点中心性如度中心性、介数中心性、接近中心性、特征向量中心性以及流介数中心性等被提出来以解决节点重要度分析问题，但是大多数方法只用单一中心性来确定有节点的影响力和重要度，而且使用不同的中心性方法得到了不同的结果.因此，本文提出了一种折衷中心性方法，利用使用不同中心性方法计算的结果，再进行变化计算，得到折衷中心性结果，进行网络节点重要度分析，并进行实例数值计算和模型分型.

1　基本理论

复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构，在数学上可以抽象为一个由点集V和边集E组成的图G=(V,E).如图1所示，是具有9个节点的简单无向无权网络图.为简化问题，本文仅针对无向无权网络进行研究.

图1　有11个节点的简单无向网络图

定义1度中心性（Degreecentralitymeasure）

节点i的度中心性是在网络分析中刻画节点中心性的最直接度量指标，用CD(i)表示，定义为：

其中i为当前所求节点，j表示其他所有的节点，是网络节点总数，表示i与j之间有连接关系.两个节点之间相连，则为1，反之则为0.

定义2接近中心性（Closenesscentralitymeasure）

节点i的接近中心性是刻画节点通过网络到达其它节点难易程度的指标，用CC(i)表示，定义为：

其中dij表示节点i和节点j之间的距离，其定义如下：

定义3介数中心性（Betweennesscentralitymeasure）

节点i的介数中心性，用CB(i)表示，定义为：

2　节点重要度评估新算法

定义4折衷中心性（Compromisecentralitymeasure）

尽管已提出多种中心性方法进行节点重要度评估，但是每一种方法都只从一个中心性角度考虑，导致使用不同的中心性方法得到的评估结果不一致.因此，本文提出了将度中心性、接近中心性和介数中心性的评估结果进行折衷处理的节点重要度评估新算法即折衷中心性.下面给出折衷中心性算法的具体步骤：

1）利用公式（1）、（2）和（4），分别计算复杂网络所有节点的度中心性、接近中心性和介数中心性的值，即得到CD，CC和CB.

2）根据定义5，分别得到复杂网络每个节点的度中心性、接近中心性和介数中心性的归一化值，即得到C~D(i)，C~C(i)和C~B(i).

定义5设CD(i)，CC(i)和CB(i)分别为节点i的度中心性、接近中心性和介数中心性的值，归一化中心计算方法为：

其中C~i表示节点i的归一化中心值，N为复杂网络节点数.

3）根据定义6，整合节点i的归一化中心值，得到CED(i).

定义6设C~D(i),C~C(i)和C~B(i)分别为节点i的度中心性、接近中心性和介数中心性归一化中心值.利用欧拉公式得到的折衷中心性的值定义为：

其中n为网络节点的数目.

4）利用计算所得的值，对复杂网络节点进行排序，值越高，则节点越重要.

3　算例

图1为有11个节点，9条边的无向无权网络.首先利用公式（1）、（2）、（4）和（5），分别计算该复杂网络所有节点的度中心性、接近中心性和介数中心性的值及归一化值，如表1所示.

表1　图1所有节点的度中心性、接近中心性和介数中心性的值及归一化值

根据公式6，计算节点1的折衷中心性值如下：

同理，利用上述方法计算其他节点的折衷中心性值，并按值进行排序，如表2所示：

表2　本文所提算法计算的折衷中心性值

由表2可见，图1的节点重要度依次为7>6>4>5>1>8、9、11>2、3，有效识别了复杂网络节点的重要度.

4　结论

本文提出了一种新的折衷中心性方法来是来分析网络节点重要度.通过计算度中心性、接近中心性和介数中心性的值，再进行欧氏距离计算，得到折衷中心性值.通过实例分析证明该方法是一种有效的复杂网络节点重要度分析方法.

〔1〕张宁，苏树清.个人微博用户网络的节点中心性研究［J］.上海理工大学学报，2015，37（1）：43-48.

〔2〕苑卫国，刘云，程军军，等.微博双向“关注”网络节点中心性及传播影响力的分析［J］.物理学报，2013，62（3）：91-95.

〔3〕D.Wei，X.Deng，X.Zhang，Y.Deng，andS.Mahadevan，Identifyinginfluentialnodesinweightednetworksbasedonevidencetheory，PhysicaA：Statistical MechanicsanditsApplications，vol.392，no.10，pp.2564 –2575，2013.

〔4〕M.Karsai，M.Kivel？，R.K.Pan，K.Kaski，J.Kertész，A.L.Barabási，andJ.Saram？ki，Smallbutslowworld：Hownetworktopologyandburstinessslowdown spreading，PhysicalReviewE，vol.83，no.2，pp.025102，2011.

〔5〕BarthelemyM.Betweennesscentralityinlargecomplex networks［J］.TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems，2004，38（2）：163-168.

〔6〕汪小帆，李翔，陈关荣.网络科学导论［M］.北京：高等教育出版社，2012.

O233

A

1673-260X（2016）08-0001-02

2016-05-05

重庆市教委科学技术研究项目（KJ1500515）