融合邻域鲁棒性及度均衡性的集体影响中心性

宋甲秀，杨晓翠，张曦煌

(江南大学物联网工程学院，江苏 无锡 214122)

0 引言

受益于评估节点影响力标准的多样性，节点影响力度量方法的研究也是各有侧重。本文，主要关注复杂网络中基于网络结构中心性指标的一类影响力度量方法。这类方法又可分为基于网络全局结构、基于网络局部结构、基于特征向量中心性的影响力度量方法等。一般地，局部度量指标效率较高，但是度量效果不尽理想，如度数中心性、局部中心性等。而以接近度中心性、介数中心性为代表的全局度量指标虽然更为有效，但计算复杂度普遍很高。相比之下，k-核中心性在时间复杂度上有极大改善，但由于粗粒度特性的存在，使得其无法区分部分节点的影响力大小。特征向量中心性指标及其变体方法更适用于有向网络，在无向网络上效果不佳。近来，Flaviano Morone和Makse[1]在Nature上提出了一种复杂度较低的基于渗流理论的集体影响(Collective Influence，简称CI)中心性指标。关于其有效性，在文献[1]～[3]中均有所证明。直观地来看，该指标考虑了节点的度数和l层所有邻居的度数(l可取1,2,3…)，但忽略了节点邻域可能存在的不平衡结构以及邻域间连接紧密程度的差异，导致其在异质性明显的实际复杂网络适用中，表现出很大的局限性。对此，本章创新性地提出了基于邻域平衡性及鲁棒性的节点影响力度量方法NewCI(New Collective Influence)中心性，并通过实验结果证明了该方法能够在保留原CI中心性较低计算复杂度优势的同时突破其局限性，有效性得到进一步地增强。

1 相关工作

在信息传播过程中，位于网络特殊位置的某些节点往往能够引发大规模的信息扩散[4-5]。较之于其他节点，此类节点在影响力方面具有明显优势，以产品的病毒营销、流行病传播等场景中最为常见。这些影响力节点的识别对于理解和分析网络中的各类信息流动过程有着重要的作用，与如今形式多样的生活应用更是密切相关。近年来，学术界对于节点影响力度量方面的研究也是在不断突破，取得了相对丰富的成果。其中，给定复杂网络中节点位置的结构信息，衡量单个节点影响力最简单的方式是基于中心性的启发式度量，如度中心性、k-核、介数和PageRank等。这些指标主要是根据网络中单个节点在扩散过程中的作用大小进行排序，并以此作为对节点影响力的衡量，为后续实现加速或限制信息扩散的目标提供理论支持。

直观地，拥有大量连接的节点应该具有更大的影响力，这也是度中心性指标的核心思想。关于此理论的合理性，于无标度网络脆弱性的早期研究中[6]有所揭示。该研究认为节点的连接数对动态过程的影响是非线性相关的，针对网络极少数的高度节点进行攻击，会使得服从重尾分布网络中的巨大连通图迅速崩溃。此外，与其他较复杂的中心性指标相比，度数的计算复杂性可以忽略不计，所以度中心性被视为识别影响力节点最简易有效的方法之一。

然而，度中心性存在一明显不足，表现为该指标只考虑了节点的一阶邻居数量，忽略了节点所处位置的网络信息。大量实证表明多数的传播现象是以层叠的方式进行的。因此，单个节点影响力的最终评估也应该受到全局网络结构的作用。此外，在实际的复杂网络中，高度节点在网络的核心位置以及边缘部分均有出现的可能。这也就意味着以度作为影响力节点识别指标，在真实世界中并不可靠。据此，Kitsak等人通过对各种实际社交网络上的数据在SIS和SIR模型上进行了广泛的模拟证实了这一推测[7]。取决于节点在全网络中位置的差异，两个度数相等的节点在SIR模型的传播过程中可能会感染完全不同的人群。相较而言，k-核指标可以区分网络的核心位置和边缘部分，且能在O(m)(m为网络边数)的运算时间内完成分解过程，故被广泛应用于大规模复杂网络分析。一般认为，具有低k-核指标值的节点被大量的低度邻居包围，会限制影响的传播，而位于核心区域的节点(高k-核指标值者)可以通过其高度邻居促进大规模扩散。但在SIS模型下，由于I群体被治愈后仍然可能被再次感染，所以高k-核区域一直会存在I群体。对此，文献[8][9][10]考虑到网络中高k-核区域的局部结构信息，提出了几种更为一般化的强化k-核方法。

除了k-核指标之外，特征向量中心性也可作为基于全局网络结构的指标。该指标认为节点的影响力取决于其邻居的传播能力。首先给网络中的所有节点分配统一的声望分数，声望分数一般初始化为向量(1,1,…,1)T∈Rn(n为网络节点数)，该分数会沿着边进行传播直到达到稳定状态为止。在计算过程中，声望分数传播的每一个迭代对应于当前得分向量左乘网络的邻接矩阵。该过程实际上是通过幂迭代来计算邻接矩阵的主特征向量及其对应的特征值，声望分数向量最终会收敛到最大特征值的右特征向量。PageRank和LeaderRank算法都为基于特征向量中心性的著名变体。

无独有偶，Flaviano Morone等人[1]为解决影响最大化问题，把寻找一组最小化的种子节点对网络中信息扩散进行控制使其达到免疫状态这一问题，精确地映射到最优渗流模型中，并提出CI中心性来对量化个体节点的影响力。该中心性度量方法考虑了节点间的拓扑相互作用，却对节点邻域分布以及网络结构的健壮程度未予关注。基于此，本文在CI中心性的基础上，对其所忽略的重要影响因素分别进行了分析、定义及量化，继而创新性地提出了在一般化网络下仍然普遍适用的影响力度量方法—NewCI中心性。通过在真实复杂网络数据集上进行的节点免疫网络抗毁性实验，证明了该中心性影响力度量方法在性能上具有很高的稳定性，且对影响力大小度量的准确性优于CI中心性。

2 算法描述

2.1 定义描述

渗流理论：是复杂网络理论研究中的一个重要发现，主要包括键渗流和点渗流。给定无向网络G(V,E)，在键渗流的模型下，G中的每条边以一定的概率q被保留，同时以1-q的概率被删除。当q=0时，所有的边都会被删除；随着q的增大，G中将会保留了较多的边并形成一些网络簇；仅当q大于临界阈值qc时，G中会出现规模为O(|V|)(V为网络节点集)的巨型连通分量。点渗流模型与键渗流模型类似，不同之处在于保留概率q被分配给节点而不是边。

(1)

(2)

其中，向量v=(v1,v2,…,vn)表示节点是否属于巨型连通分量，vi取值为1(或0)，表示节点vi属于(或不属于)该巨型连通分量。在删除节点等量的情况下，G(q)的值越小，说明网络分裂越严重，反映出所删除节点在网络中承担的角色越重要，即个体影响力较大。

连通分量的数量：给定初始网络G(V,E)，C(q)为基于某种特定的中心性度量方法删除nq数目的节点之后的网络中连通图的数量，连通分量的数量分数Rc则定义为C(q)与初始网络G的规模的比值，即

(3)

式中Rc的值越大，网络的分段就越多。Rc(q)=1时，网络将完全分散，所有的节点之间几乎相互孤立，网络的性质也就不复存在；Rc(q)=0时，则表示网络为一个连通网络，具有较强的抗毁性。在以删除相同数量节点为前提条件下，C(q)和Rc(q)都可通过网络被破坏的碎片化程度来衡量这些节点的实际影响力。

2.2 基本方法介绍

本文主要就五种最为常用的节点影响力度量方法进行简要介绍，包括介数中心性[4,13-14]、接近度中心性[4,15]，k-核[16]、特征向量中心性[17]以及CI中心性[7]。它们也将作为后续实验研究中的基准方法。

(4)

接近度中心性(Closeness Centrality，简称CC)[4]，定义连通网络G中节点vi的接近度中心性为从该节点到所有其他节点的最短距离平均值的倒数，即

(5)

其中，dij为节点vi与节点vj间的最短距离。显然，CC值越大，节点越处于网络中心，影响力就越大。

k-核(简称k-core)方法[13]的主要思想基于核心度，即认为位于网络核心部分的节点的影响力要高于边缘节点。实现流程如下：设网络的孤立节点的核心度为0，并将其从网络中去除，而后进行k-核分解。首先，把所有核心度为1的节点从网络中移除，之后继续移除剩余度小于等于1的节点，直到网络中所有剩余节点的剩余度都大于1为止。该步中所有移除的节点即为1-核节点，其核心度都等于1。接着遵循以上步骤，对网络中核心度为2的节点进行处理。以此类推，直到网络中所有的节点都被移除。在该方法下，较大核心度的节点意味着位于网络更中心的位置，有更大的影响力。

特征向量中心性(Eigenvector Centrality，简称EC)[17]认为节点的影响力取决于邻居的数量以及其影响力，定义节点vi的特征向量中心性如公式(6)，可通过幂迭代方法计算得出。

(6)

Α={aij}

(7)

其中，c为比例常数，一般取1/λ，λ为邻接矩阵A的最大特征向量。

集体影响(Collective Influence，简称CI)[7]是一种中心性优化方法，旨在寻找在最优渗透模型下使网络结构碎片化的最小影响力节点集，该指标从选择节点并将其删除给网络中巨型连通分量所带来的破环程度来衡量节点的影响力大小。定义Ball(i,l)为围绕节点vi，且属于半径(最短路径)为l的球内的节点集合，∂Ball(i,l)为该球的边界，那么节点vi的CI中心性值为

(8)

其中，ki是节点vi的度，l是预定义的不超过有限网络的网络直径的非负整数，在大中型网络一般取3，小网络中取2。

2.3 融合邻域鲁棒性及度均衡性的集体影响中心性度量方法

真实的复杂网络中普遍存在着异质性，如微博、Twitter等社交网络，考虑该因素对提出合理的节点影响力度量方法有着重要意义。而CI中心性只考虑到了节点的度数和以该节点为中心，半径在l(节点间的最短路径)的球面边界上所有节点的度数，忽略了由于优先连接造成的度分布不平衡问题所带来的影响。

如图1所示，首先，本文针对多个节点的CI中心性度量值相等的情况，对各节点所对应的局部拓扑结构进行详细分析。简单起见，1)令l=1，后续的分析将推广至l阶邻居，2)以局部树状网络为研究起点，逐步扩展到节点及其l阶邻居的局部聚类系数不为0的一般网络。根据CI中心性的定义可知，CI中心性度量值相等的节点无外乎是两种情况：一是其一阶邻居节点的数量相同，且一阶邻居节点的度之和也相等，如图1a和c中的节点1。如此一来，一阶邻居的度分布平衡与否便成为了区分两节点影响力的关键，本文称此问题为目标节点的1阶邻域的度均衡性。第二种则是其一阶邻居的数量不相等，如图1a和b中的节点1。

除了目标节点的一阶邻居节点度分布及其一阶邻居数量这两个因素之外，目标节点的一阶邻居的邻居之间的相互连接关系也会对该节点的影响力评估产生影响，本文称此因素为1阶邻域簇间连接强度。鉴于在CI中心性度量方法中，半径l考虑的是最短路径，所以该因素并不会对CI的计算结果产生影响。以图1e为例，节点一阶邻居的邻居之间的连接关系对应于最外层球面节点的连接情况。显然，节点6和节点7、节点12与节点13之间的连接在目标节点1从网络中去除后，不会对碎片化网络的连通分量的数量以及巨型连通分量的规模产生影响。然而节点7与节点9、节点10和节点12之间连接的存在与否，将导致在对目标节点进行相同的操作后，网络结构会产生截然不同的变化。

此外，还有一个不容忽视的影响因素：目标节点一阶邻居间的连接关系，本文称之为邻域鲁棒性，以局部聚类系数这一基本网络特征来衡量。假设突破CI中心性度量方法对于局部树状网络的限制，推广到一般化网络，节点局部的网络拓扑结构将会发生巨大变化。如图1d，若目标节点1在树状网络中的一阶邻居全部没有互相连接(即虚线链接不存在)，即该节点的局部聚类系数为0，其与一阶邻居的局部拓扑结构是树状网络；随着一阶邻居互连强度的增大，该节点的局部区域的结构趋于稳定，当该节点的聚类系数增加到1时，其与一阶邻居节点在拓扑上则构成了全连接网络图(图1d中虚线链接全都存在的情况)。不难发现，目标节点在树状网络中被删除后，该网络因抗毁性差，迅速分段瓦解成多个碎片网络。而在全连接网络中，网络结构具有较强的健壮性，删除目标节点后，网络仍然连通。因此，网络中目标节点的一阶邻居间连接关系的复杂性对于准确有效地衡量节点的影响力至关重要。

图1 NewCI中心性分析示意图Fig.1 Analysis diagram of NewCI centrality

综上所述，CI方法忽视了研究目标节点的度数及其1阶邻域度均衡性、1阶邻域簇间连接强度、邻域鲁棒性等四个与影响力节点的度量相关的因素。本文对其进行改进，将1阶邻域度均衡性、1阶邻域簇间连接强度推广到l阶邻域，对目标节点的l阶邻域度均衡性、l阶邻域簇间连接强度、邻域鲁棒性给出了相应的定义与分析，并以真实复杂网络为应用背景，提出更具合理性的影响力度量方法。同时，针对目标节点的度数这一影响因素，制定出相应的排序局部调整策略。以下，将就这些概念逐一介绍。

2.3.1l阶邻域度均衡性

节点的l阶邻域度分布的异质程度是评估节点影响力的重要因素。为了量化l阶邻域节点度分布的均衡程度，本文定义l阶邻域度均衡性如式(9)。其中，Nl(i)表示节点vi的l阶邻域的节点集合，kj代表节点vj的度。分母中的第一项理解为l阶邻域度的振幅与l阶邻域度的理论中间值的比值，加1为防止分母为0的平滑操作。

(9)

目标节点的l阶邻域各节点的度越均衡，去除该节点后分裂成的网络碎片，规模会相对更均衡，网络中巨型连通分量会骤减，即该节点在网络中的影响力更强。反之，则越弱。基于此，本文将CI中心性方法修正为NewCIB中心性(New Collective Influence centrality based on Neighborhood Balance)方法，如式(10)。当Bl(i)为1(目标节点的l阶邻域各节点的度绝对均衡)时，该方法退化为CI方法。

NewCIB(i)=Bl(i)CI(i)

(10)

为验证NewCIB中心性方法的合理性，本文以图1a,c举例说明。令l=1，节点1为研究对象，根据式(8)两图中节点1的CI中心性值都为24。NewCIB(1)考虑了邻域度分布均衡性，节点1对应的邻域节点的度均衡程度越高，则NewCIB值越大。对于a，c两图中的目标节点1，根据式(10)计算出的NewCIB方法值分别为24、16.8，表明节点1的删除对a网络的破坏性更大，与图中所反映的实际情况一致。由此可知，与CI中心性方法相比，NewCIB方法对节点影响力大小的评估更为准确。

2.3.2l阶邻域簇间连接强度

如上所述，在目标节点l阶邻域的节点度分布均衡性一定的情况下，l阶邻域节点间的连接情况则成为评估节点影响力的主要干扰因素。其中，目标节点的l阶邻域簇内节点间的连接(图1e中的连边(6,7)和(12,13))与该节点的删除对网络的破坏性相互独立。而其l阶邻域簇间节点间的连接(图1e,1f中的虚线)则影响了删除该节点后的网络连通性，增强了网络的健壮性。更直接的表述是，虚线连接之后的网络，目标节点的影响力减弱。本文中以目标节点的所有邻居节点为簇头的网络簇中l阶邻域连通簇的数量来定义l阶邻域簇间连接强度这一影响因素。

对于目标节点vt，Nl(t)表示其l阶邻居的集合，l阶邻域连通簇对(Connected cluster pairs)的集合记为Ccp(初始化为Ø)，N(x)为vx的邻居集合。当|Nl(t)|=1时，l阶邻域连通簇的数量为1。当|Nl(t)|>1时，对于任意vi，vj∈Nl(t)，且j>i，利用Ψij来判断vt所有邻居节点为簇头的网络簇之间在l阶邻域上是否连通，即

Ψij=(N(Nl(i))-N(Nl(i))INl(i))INl(j)

(11)

此时，若Ψij=Ø，表明以vi和vj为簇头的网络簇之间不连通；Ψij≠Ø，则连通，连通簇的簇头对集合记为{(vi,vj)}。所以有

(12)

记Ccp中簇对所形成的连通簇团个数(Number of connected clusters)为Ncc，目标节点的邻居中未和其他簇头连通的节点数，即独立簇头个数(Number of independent cluster)为Nic，则最终目标节点的l阶邻域连通簇的数量为

Tc=Ncc+Nic

(13)

l阶邻域簇间连接强度定义为

(14)

同样，CI中心性方法不能实现根据l阶邻域簇内节点间的连接存在与否以及连接强度对节点影响力的大小进行区分。为克服这一不足，在目标节点l阶邻域的节点度分布均衡性一定的情况下，本文将CI方法重写为NewCIS中心性(New Collective Influence Centrality based on Neighborhood Strength Coefficient)方法：

NewCIs(i)=Sl(i)CI(i)

(15)

以图1a和e、c和f为对比，来分析验证NewCIS中心性方法的合理性。首先，当e和f中虚线不连接时，根据式(8)得到目标节点1在4个图中的CI均为24。其次，虚线连接后，e和f中目标节点1的NewCIS分别为12和6。显然，簇间连接的加入，会使得e(或f)中目标节点1的影响力弱于a(或c)，与实际情况相符。

2.3.3 邻域鲁棒性

为了量化节点的局部邻域结构拓扑的健壮性差异对节点影响力大小的影响，本文引入“邻域鲁棒性”概念来衡量目标节点的邻域节点间连接的密集程度，认为邻域节点间的连接越密集，网络结构的鲁棒性则越强，反之亦然。这里采用目标节点的局部聚类系数这一网络统计量来计算其邻域鲁棒性，形式化表示为

(16)

考虑到目标节点的邻域鲁棒性与其在网络结构上发挥的影响力成反比，且该节点邻域节点间的连接程度会直接影响邻域节点的度分布均衡性，本文修正CI中心性方法为NewCIB/R中心性(New Collective Influence centrality based on Neighborhood Balance and Robustness)方法，定义如下：

(17)

接下来结合图1a、d来验证NewCIB/R中心性方法的合理性。在图1a、d中，节点1为研究对象，即目标节点。a中节点1的CI中心性值为24；d中节点1的CI值会随着其聚类系数的增加而增加，当节点2与节点5之间有连接时，目标节点的CI值为30。显然，节点1在a网络中被删除之后，该网络会分解成4个碎片网络，而图d中，由于节点2与节点5的相互连接，删除节点1后，该网络只分段为3个碎片网络，且巨型连通分量更大，说明了节点1在a网络中有更大的影响力，这与两图中由CI中心性方法所度量的影响力结果相悖。然而，基于本文的NewCIB/R中心性方法，节点1在a网络中的NewCIB/R中心性值同样为24，但在d图中该节点的NewCIB/R中心性值为21.4，与CI中心性方法相比，NewCIB/R中心性方法对目标节点的影响力度量更为合理。

同上思路，基于节点的NewCIS中心性度量方法，其邻域鲁棒性也能加强度量方法的有效性，故在CI中心性指标的基础上融合节点的l阶邻域簇间连接强度与邻域鲁棒性，定义NewCIS/R中心性(New Collective Influence Centrality based on Neighborhood Robustness and Strength Coefficient)方法为：

(18)

综上所述，结合l阶邻域度均衡性、l阶邻域簇间连接强度、邻域鲁棒性等CI方法忽略的影响力度量影响因素，本文定义NewCI中心性方法为：

(19)

其中，参数α一般取0.5。

需要补充的一点是，NewCI中心性方法是针对目标节点的邻居数目一定，CI值相同的情况(图1a、c、d、e、f)而设计，并不能适用于邻居数目不等，CI值相等的情况。如图1a、b所示，两图中目标节点1的邻居数分别为3和4，CI值均为24，且l阶邻域度均衡性、l阶邻域簇间连接强度以及邻域鲁棒性都相等，故二者的NewCI值相等。但b中节点1的影响力显然比a中的要弱。也就是说，在这种情况下，目标节点本身的度是具有最高优先级的考虑因素。因此，本文制定排序局部调整策略如下：在对网络各节点的影响力进行度量时，若出现多个节点NewCI相等的情况，将根据邻居数目对这部分节点进行降序排列，以强化结果的整体合理性。注意，该策略只为实验中确定影响力节点的相对排名而用，并不作为节点影响力度量方法。

2.4 时间复杂度分析

给定复杂网络G=(V,E)，这里V和E={(u,v)|u,v∈V}分别表示网络中的节点集和边集，n和m依次代表V和E的规模。NewCI中心性影响力度量方法的计算复杂度主要由节点的CI中心性度量、l阶邻域度均衡性、l阶邻域簇间连接强度以及邻域鲁棒性等4部分计算复杂度组成。其中，节点CI的计算复杂度与该节点l阶邻域节点的数量有关。由于网络中节点的平均度为〈k〉，则任意节点的l阶邻域的平均节点数量为〈k〉*〈k〉l-1，则计算网络所有节点CI的复杂度为O(n*〈k〉*〈k〉l-1)。对于目标节点l阶邻域度均衡性和l阶邻域簇间连接强度的计算，复杂度均为O(〈k〉*〈k〉l-1)，节点的邻域鲁棒性的计算复杂度为O(1/2*〈k〉*(〈k〉-1))。所以，NewCI中心性影响力度量方法的最终时间复杂度为O(n*(3*〈k〉*〈k〉l-1+1/2*〈k〉*(〈k〉-1)))。又由于真实世界的复杂网络通常是稀疏的，节点的数量n和边数量m存在着m=O(n)的相关关系，所以〈k〉=2m/n可以记为一个常数，故算法的时间复杂度可近似为O(n*(3*〈k〉l+1/2*〈k〉2))，而l的取值一般较小。因此，NewCI中心性影响力度量方法具有较低的时间复杂度，符合基于网络局部的中心性方法所具有的优势。

3 实验结果与分析

节点的影响力大小主要通过免疫该节点给网络带来的破坏程度来体现，本节即从该角度对NewCI中心性的性能进行实验验证。实验中l的取值一般为2，与CC、BC、EC、k-core以及CI等5个代表性方法进行对比。

3.1 实验环境与数据集介绍

实验的硬件环境为Intel(R) Core(TM) i5-3210 CPU @ 2.50GHz，8 GB的内存。操作系统为window7。开发环境Visual Studio Code 1.15.1，开发语言为python 2.7。网络分析工具包括snap-4.0.1版本、networkx-1.11版本、Gephi 0.8.1beta等。

为充分评估NewCI中心性的性能，本文选取了6个领域不同的真实复杂网络数据集，包括：1)Celegans[18]：秀丽隐杆线虫神经元网络；2)Power[18]：美国西部电力网络，以发电站或中转站为节点，高压传输线路为边；3)Citeseer[19]：由科学出版物和引用链接组成的引文网络；4)Literature_1976[20][21]：荷兰文学评论数据集，节点为文学作者或评论家，边表示评论家对文学作者工作的评价；5)Sawmill[21][22]：某企业内部员工的通信关系网络；6)ModMath[21]：现代数学方法在美国宾夕法尼亚州Allegheny县的小学和中学课程中的传播网络。网络中的节点表示学校的主管领导，边则表示管理者之间的友谊关系。

各数据集的基本网络拓扑特征如表1，依次为节点数量(n)、网络边数(m)、平均度(〈k〉)、最大度(kmax)、网络中节点的平均聚类系数(C)、节点间的平均最短路径(〈d〉)、同配系数(r)、节点度分布的异质性(H)[23-24]以及传播阈值[6,25](λc)。其中，H=〈d2〉/〈d〉2，λc=〈k〉/(〈k2〉-〈k〉)。

表1 实验数据集的基本拓扑特征Tab.1 Basic topological features of the experimental datasets

3.2 节点免疫的网络破坏性实验

本节对最终的NewCI中心性方法在6个真实复杂网络数据集上进行实验和结果分析。其中，各真实网络中G(q)、C(q)随着q值变化的情况描述如图2，各方法在6个实验数据集中的执行效率记录如表2。

图2 不同中心性方法在节点免疫的网络破坏性实验中的表现Fig.2 Performance of different centralities in network destructive experiments of node immunity

表2 各中心性方法在真实数据集中的执行效率Tab.2 Execution efficiency of each centrality in real datasets

显然，NewCI中心性度量方法的表现稳定优于CI中心性方法。如在图2a Celegans网络中，NewCI中心性在q约等于0.576时，网络中G(q)的规模从43直接减小为22。而CI中心性方法完成这一变化，即达到相同的网络破坏程度，网络中删除节点的比例q须达到0.623，可见NewCI方法较CI提高了约7.5%的性能。在图2b power网络中，q为0.10时，NewCI中心性使该网络中G(q)的规模从1 088个节点急剧减小为629。而CI中心性的最优分裂点在q=0.151处，此时网络中G(q)的规模仅从856个节点减少到515个节点。同样是使目标网络中的G(q)的规模达到网络规模的10%，NewCI的性能相比CI大约提升了34%。在其他的实验数据集中的结论与此类似。

整体而言，在节点删除的最初阶段，G(q)随着节点的删除会剧烈减小，当超过一个最优的比例q之后，删除节点对网络的破坏作用减弱。而NewCI相比其他方法，曲线的下降趋势更为快速。其中，该方法在Celegans、Power、Literature_1976以及Sawmill 4个网络集中均为最佳；在Citeseer和ModMath中的表现也仅以微弱差距次于BC中心性方法；在所有数据集上都领先于CI，充分证明了其对节点影响力大小评估的有效性和准确性。与G(q)相对应，C(q)在最初阶段随着q的增加急剧增加，达到极值之后，呈现减小趋势。在该指标之下，本文的NewCI中心性在Power、Literature_1976、Sawmill以及ModMath 4个网络数据集上的表现同样明显优于CI中心性，在其他两个数据集中，也能取得和CI相当的效果。

从表2各方法的执行效率来看，NewCI中心性的执行时间比与经典的BC、CC方法更短，与其他方法的执行时间同处一个数量级。

综上所析，在所有中心性方法的对比中，以NewCI中心性方法与BC中心性方法的表现最好。NewCI中心性于各个类型的网络中的表现均能稳定地优于CI中心性，肯定了该方法对CI中心性方法性能的提升，同时也验证了其在度量节点影响力问题上的有效性，以及在应用网络方面的普适性。较短的执行时间，使得其在较大规模的网络中依然可行。

4 总结与展望

从节点免疫的网络破坏性角度来看，NewCI中心性较CI中心性表现出更高的有效性和普适性，打破了CI中心性方法仅适用于树状网络的局限。与各中心性方法相比，该方法与BC中心性方法展示出最佳的性能。综合有效性、时间复杂度及执行效率三者考虑，NewCI中心性则优于其他中心性方法。

近年来，网络表示学习技术兴起，逐步成为解决大规模网络数据网络数据的有效手段。基于网络表示学习技术实现对网络中节点影响力更为准确和快速的评估，以适用于多关系网络等新型网络，将是本文下一步的研究任务。