探测和评估复杂网络影响力节点的路径多样性核度中心方法①

杨 雄 黄德才 詹秀秀 张子柯

(*浙江工业大学 计算机科学与技术学院、软件学院 杭州 310023) (**常州工学院 计算机信息工程学院 常州 213002) (***杭州师范大学 阿里巴巴复杂科学研究中心 杭州 311121)



探测和评估复杂网络影响力节点的路径多样性核度中心方法①

杨 雄②***黄德才③*詹秀秀***张子柯***

(*浙江工业大学 计算机科学与技术学院、软件学院 杭州 310023) (**常州工学院 计算机信息工程学院 常州 213002) (***杭州师范大学 阿里巴巴复杂科学研究中心 杭州 311121)

针对当前复杂网络影响力节点探测和评估方法不能精确定位影响力节点、计算复杂等不足，在传统网络K核分解方法的基础上引入了路径多样性概念，从信息传播角度进行了研究，提出了一种基于路径多样性信息熵进行影响力节点探测与评估的新的核度中心方法，即路径多样性核度中心(Cncd)方法。实验结果显示，相对于其他影响力节点探测与评估方法，如度中心法(CD)、介数中心法(CB)、接近中心法(CC)、K核中心法(KC)及核度中心法(Cncd)，Cncd方法能够更精确地对影响力节点进行定位，并且能更细粒度地对节点影响力进行有效排序。

节点影响力， 度中心， 介数中心， 接近中心，K核分解

0 引 言

近年来对以社会网络、计算机网络、生物网络、管理网络为代表的复杂网络科学的研究日益受到重视。挖掘和探测复杂网络系统中的影响力节点已成为研究复杂网络结构和动力学机制的基本方式，如何高效和准确地探测出网络影响力节点已经成为复杂网络研究领域的热点方向之一。网络影响力节点的挖掘和探测技术已经在包括传染病疫情控制[1]、信息传播[2]、市场广告投放[3]、社会网络领袖[4]、学术网络评级[5]等领域产生了重要的理论和实际应用价值。然而当前网络影响力节点的探测和挖掘技术存在明显不足，例如高连接度方法和传统的网络K核分解方法不能很好地精确定位影响力节点，介数中心方法和接近中心方法虽能够较准确定位，但计算复杂，不适用于大规模复杂网络。针对这种情况，本文提出了一种基于路径多样性的网络节点影响力探测和评估方法，该方法既考虑了节点核度，同时也考虑了路径多样性对复杂网络节点的影响力，能够更有效地对关键节点进行定位和更细粒度地对节点影响力进行有效的排序。本文将这种方法叫做路径多样性核度中心(Cncd)方法。

1 相关研究

传统的网络影响力节点探测评估方法通常采用节点的连接度属性来衡量度中心(degree centrality,CD)，方法较为简单，计算工作量较小，但忽视了网络的全局结构，片面地关注于节点的局部属性，因此准确度并不高。Freeman[6]和Sabidussi[7]提出了非常著名且使用广泛的介数中心(betweenness centrality,CB)方法和接近中心(closeness centrality,CC)方法，这两种方法很好地解决了度中心方法不能处理的全局问题，具有较好的探测效果，但是由于网络规模的迅速扩大，这两种全局中心探测方法的计算将会非常耗时，因此并不适用于较大规模网络。2012年Chen[8]提出了一种半局部的节点探测方法，该方法不仅考虑了节点的连接度而且还考虑了邻居的连接度属性，这样做的优势在于一定程度上考虑了网络的全局结构又借鉴了度中心计算简单的特点，解决了全局中心计算复杂性的问题。

最近，Kitsak[9]提出了一种K核分解(K-core decomposition)方法，他发现很多具有高连接度和高介数中心的节点往往并不一定能够对网络中的信息传播起到决定作用，恰恰相反，实验发现能够对信息传播起到重要作用的节点通常位于网络核心位置。K核分解首先删除图G中所有连接度为1的节点及他们所有的边，若剩余节点中仍有度值为1的点继续将他们删除，将这些删除的节点划入核层为1的核中(本文用kc表示节点的核层)；其次对剩余连接度为2的节点重复上面步骤，将它们划入核层为2的核中(kc=2)；最后该过程一直循环下去直到所有节点均被删除且分配了相对应的核层数kc。

然而K核中心(K-core centrality,CKC)法也有一定的局限性，比如这种方法经常会将具有不同传播能力的节点划入同一个核层，或者说同一核层中的不同节点往往对信息的传播具有不同的重要性。针对这个问题，2013年Basaras[10]提出了一种融合介数中心和核层分解的综合方法，该方法较好地弥补了传统K核分解的不足之处。同年，Zeng[11]针对传统K核中心方法只关注于节点核内连接度而不考虑核外连接度属性的缺点，提出了一种混合度分解的节点中心评估算法，Liu[12]根据节点与网络最大核层中核心节点的距离来给出待评测节点的影响力，指出与网络核心距离越近的节点影响力越大的观点，但是该方法由于需要计算距离仍然会导致较大的计算复杂性。

值得注意的是，2014年韩国庆北大学[13]的研究小组首次提出了一种基于节点核度中心(neighborhood core centrality，Cnc)的影响力评估方法，该工作给出的节点核度概念可以理解为该节点所有邻居所处的网络核层数之和，核度概念的提出一方面考虑了节点所处的网络位置，同时也考虑了节点外部邻域的信息。该方法解决了网络边缘连接度大的节点没有获得合理评估的缺陷，由于这种方法将注意力集中在节点的局部属性——连接度，因此具有较好的计算效率。

但是在很多场合中仅用核度的概念并不能很好地解决节点影响力的判断问题。如图1所示，在该网络中节点1、2、3、22均位于网络中心核层3中(kc=3)，而其他节点均位于核层1中(kc=1)。当使用传统的K核分解时并不能判断出这4个节点之间的影响力有何差异，而使用文献[13]中提出的核度方法，因为节点1和2的核度等于12，节点3和22的核度等于9，则可以得知节点1和2的影响力大于节点3和22。从图1中可以非常明确地看出，由于节点1和2外连着核层1中所有的节点，因此这两个节点的影响力将远远大于节点3和22。但是核度方法在判断出节点1和2的影响力大于同核中的节点3和22后并不能对彼此进行更为细致的影响力判断。由于两者核度相同，节点1和2会被认为具有同等重要的地位。然而可以发现，虽然节点1和节点2各自外连着核层1中数量等同的3个邻居节点和6个2级邻居节点(节点1连着4～6和10～15，节点2连着7～9和16～21)，但是由于节点2将信息传往核层为1的2级邻居节点的路径均 重叠于节点7，因此节点7和节点2之间路径的状态对于节点2来说对整个信息的传递具有非常重要的作用，如果该路径崩溃则对于节点2来说能够传递的节点数只有2个(节点8和9)。而对于节点1而言由于路径多样性、同样将信息传给核层为1的节点时，节点4、5、6和节点1之间同等情况任意单条路径的崩溃却仍然能够保证信息可以到达其余6个节点(2个邻居节点、4个2级邻居节点)，即相对于节点2而言同等路径损坏条件下节点1更容易使得信息传播出去，因此具有更重要的传播影响力。

图1 路径多样性的网络核度示意图

从上述讨论中可以看到，单纯依靠K核分解和核度计算并不总能对网络节点影响力进行合理的评估，实际上路径的多样性也将对节点影响力评估产生深刻的影响。本文另辟蹊径，在考虑节点核度的同时引入路径多样性概念来研究复杂网络节点的影响力，相对于介数中心方法和接近中心方法需要全局属性、不适合大规模网络的缺点，本文方法具有聚焦于节点的局部属性、计算简单的优点。实验结果显示，路径多样性核度评估方法相对于其他方法更能够准确地评估节点影响力，同时对网络信息传播的高效性也有着重要的作用。

2 节点影响力评估方法描述

传统的网络节点影响力评估大都利用图论中割点、割边等概念对网络拓扑进行研究，而以社会网络为代表的复杂网络对节点影响力评估大都借助其结构属性和信息传播动力学模型进行度量。G=(V,E)表示一个无权无向网络图，节点数n=|V|，借助已有研究成果对任意节点i的影响力评估指标表示如下：度中心(CD(i))、介数中心(CB(i))[6]、接近中心(CC(i))[7]、K核中心(CKC(i))[9]、核度中心(Cnc(i))[13]。

2.1 路径信息熵的节点影响力计算

目前大多数研究工作都集中于利用局部信息如节点的度进行影响力评估，而本文采用核度中心评估方法并引入路径多样性的概念来提高节点影响力判断的准确性和高效性。

步骤1 任意节点的路径多样性问题均可通过其邻居节点连接度的不均衡性进行有效表达，本文采用信息熵[14]方法对任意节点i的路径多样性进行定量描述。

定义hi为节点i的路径多样性信息熵，N(i)为节点i的邻居集合，j为节点i的邻居(j∈N(i))，kj为节点j的连接度，pj为节点j的度占i所有邻居节点度之和的百分比，公式如下：

(1)

hi值越大表明节点i的邻居节点连接越均衡，也就是节点i的信息传播路径越多样化，在随机传播时感染能力越强。

步骤2 对式(1)进行标准化处理得到公式

(2)

步骤3 在传统度中心评估方法基础上考虑邻居节点的度来提升影响力评估的准确性，文献[8，15]提出了节点i改进后的度中心评估指标如下式所示：

(3)

其中λ为可调参数。鉴于该思想，我们在核度中心评估方法Cnc基础上考虑了节点邻域信息，并且

图2 节点路径多样性信息熵示意图

引入路径多样性参数Hi，提出了节点i的一种路径多样性核度中心评估方法Cncd(i)(neighborhood core diversity centrality)和核度中心评估方法(Cnc)[13]和路径多样性核度中心评估方法公式如下：

(4)

其中CKC(i)表示经过K核分解后节点i所处的核层。

步骤4 遍历网络中各个节点，计算它们的路径多样性核度中心评估值Cncd(i)，并根据该值从大到小排序，即为节点的影响力排序。

下面以图1的小规模样本网络为例，分别利用各种影响力评估方法(CD(i)、CB(i)、CC(i)、CKC(i)、Cnc(i)及Cncd(i))对节点影响力进行评估及排序。表1显示了不同影响力评估方法排序的结果(λ=2)，可以看到有些评估方法同一位次上具有多个节点，因此采用一种优化方法进行细粒度排序划分就显得非常重要；如利用核度中心方法Cnc评估在第一的节点1和2在改进后的路径多样性核度中心方法Cncd中进行了更细粒度的排序；同时利用度中心法CD排在第三位序的节点3、4、5、6和22也在路径多样性核度中心方法中进行了不同顺序的划分。表2显示了节点1-7和节点22这8个重要节点在不同影响力评估方法中的计算值。

表1 不同影响力中心评估方法下的节点排序

表2 不同影响力中心评估方法下的节点数值

2.2 节点传播信息的定义

影响力传播节点对信息传播具有促进作用，这里借鉴经典传染病SI(susceptible infection)模型定义信息传播过程。任意节点的状态只有2个：感染(接收)状态和未感染(未接收)状态。

设t表示信息在网络中传播的轮次，V1(i,t)表示在t时刻被源点Vi感染的节点集合，V1(i,0)={Vi}表示t=0初始时刻感染节点只有Vi，V0(i,0)={V1,V2,V3,…,Vi-1,Vi+1,Vi+2,…,Vn}表示初始时刻未感染节点集合。规定节点一旦感染将从集合V0中删除并被放入集合V1且V1中节点不可重新回到集合V0。当第t轮次(步)传播时，遍历V1(i,t-1)集合中每个节点及它们的未被感染邻居节点，令∀Vp∈V1(i,t-1); Vq={N(Vp)∈V0(i,t-1)}，针对每个Vp随机选择l个Vq中的节点将他们放入V1(i,t)集合，同时从V0(i,t-1)删除这l个节点生成新的V0(i,t)集合。令f(Vi,t)表示节点Vi在t时刻的传播影响力，也就是信源在经过t轮次(步)后能将信息感染传播给网络节点的总数，f(Vi,t)=|V1(i,t)|。

2.3 路径信息熵对节点影响力评估的意义

3 实验结果分析

3.1 实验网络拓扑数据

实验过程中使用2个真实网络进行结果分析，分别为Gleiser[17]的爵士音乐家网络(Jazz)和Duch[18]的细胞代谢网络(C.elegans metabolic network)，两个网络基本拓扑特性如表3所示。

表3 两个实验网络的拓扑数据

从表3中可以看到Jazz网络的节点个数比C.elegans网络少了将近一半但边数反而更多，这个现象说明该网络节点之间的联系较为紧密(簇系数更大)，同配系数相对C.elegans网络更大说明Jazz网络中同类节点易于互连，这个现象也符合社交网络的实际规律。

3.2 实验结果分析

从两个角度对实验结果进行分析：(a)采用2.2节所述传播模型比较评估结果与节点实际传播效果之间的关系，判断不同方法的有效性；(b)使用SI模型和独立级联模型IC[19](independent cascade model)比较不同方法选取差异节点的信息传播效果。实验平台为Intel Core i3-2348M、4G的Win7系统，编程环境为R 3.1-win。

(a)排序结果与实际传播影响力的关系

依次遍历网络中每个节点Vi作为单独的初始传播源，在指定时间(t=5)计算该节点的实际传播能力f(Vi,t=5)。图3显示了不同评估方法在2个网络中与节点实际传播影响力f之间的关系。从图3(a)～(d)，(g)～(j)可以看到度中心方法和接近中心方法的临近节点之间传播影响力差异较大，因此散点图分布发散且不随评估值呈现单调递增趋势；介数中心方法和K核中心方法不能对相同评估值(横坐标值)的节点实际影响力进行有效区分，而 且可以看到随着介数中心值的增加，一些节点的传播影响力也并非呈现递增趋势，可见传统的度中心、接近中心、介数中心、K核中心方法均不能对节点影响力进行细粒度区分。图3(e)和(k)显示了核度中心方法的效果，相对于前述方法，虽然总体呈现单调递增趋势但是仍然有临近节点间传播影响力差异较大的现象，散点图依然较为发散。从图3(f)和(l)可以看到，本文提出的路径多样性核度中心(Cncd)方法呈现单调递增走势，且临近节点间的传播影响力差异较小、散点图较为收拢，因此可以有效对节点影响力进行细粒度排序。

图3 不同影响力评估方法与节点实际传播能力关系图

图4为Jazz和C.elegans网络节点的路径多样性核度中心方法与其他几种方法在传播影响力方面的热度图，横轴分别为节点的度中心、介数中心、K核中心、核度中心；纵轴为节点的路径多样性核度中心；颜色坐标表示节点的实际传播影响力f。从图4(a)、(b)、(d)、(e)可以看到度中心、介数中心、K核中心与本文方法相关性并不强，例如jazz网络度中心和介数中心最大的节点并非实际传播影响力最大的节点，而且两个网络中绝大多数节点都重叠在度中心和介数中心(横坐标)较小的区域，无法有效区分这些节点的影响力；而在C.elegans网络的K核中心方法中大量不同传播影响力的节点被赋予相同核层，同样无法通过K核中心方法进行细粒度区 分；从图4(c)、(f)可以发现本文方法与核度中心方法相关性较强，随着核度中心值的增加、节点路径多样性核度中心值也会相应增加并且传播影响力也越大，但是在核度中心值(横坐标)较小的区域依旧无法对重叠节点的传播影响力进行有效区分。但从图4(a)～(f)可以看到数据点在本文方法表示的纵坐标上分布较为均匀且随着纵坐标值的增加，节点传播影响力也越大(颜色越深)，因此本文方法能够对网络节点传播影响力进行更细粒度地探测。

图4 不同评估方法的传播影响力热度比较图

为了对不同评估方法的有效性进行分析，这里还采用Kendall系数[20](τ)衡量不同评估排序方法与节点实际影响力(f)排序之间的相关性。τ取值最大为1表示两种排序方法完全正相关，取值最小为-1表示两种排序方法完全负相关，τ值越大说明评估方法排序的结果越接近于节点实际影响力排序、该评估方法越准确。表4显示了不同评估方法与实际传播影响力排序之间的Kendall系数，可以看到路径多样性核度中心方法Cncd的性能均优于其他方法，并且随着网络节点规模和感染率β的增加，评估方法的准确性有所下降，这个现象可以解释为随着感染率β的增加，在固定时间有越来越多的节点均达到饱和传播感染状态，从而无法辨别彼此间的实际传播能力，导致排名顺序精确度的下降。

表4 不同评估方法与实际影响力排名之间的Kendall系数

(b)评估方法之间的差异分析

为了分析本文提出的路径多样性核度中心方法(Cncd)与其他方法对节点影响力评估的差异，分别将本文方法与度中心(CD)、介数中心(CB)、核度中心(Cnc)方法进行了比较(由于K核中心(CKC)方法将大量不同影响力节点赋予相同值，准确度较差，因此直接排除)。实验将Cncd方法分别与其他三种方法进行两两比较，选取非同时出现在两种方法排名前20位的节点作为各自的传播源节点(前20位中Cncd与CD有3个不同节点、Cncd与CB有6个不同节点、Cncd与Cnc有1个不同节点)，因为仅仅出现在一种评估方法的节点一定程度反映了该方法对影响力评估的侧重点。为了比较传播效果，实验分别采用独立级联(IC)模型和SI模型进行信息传播，实验中将IC模型的成功激活概率设置为0.2，SI模型传播率β=0.6，λ=2。限于篇幅，这里只给出了规模较大的C.elegans网络的实验结果。

从图5(a)(b)(c)可以看到，相比于其他三种方法，仅被Cncd方法发现的节点在独立级联(IC)模型的传播效果均优于其他方法，而图5(d)(e)(f)中仅被Cncd发现的节点在SI模型的传播速度均快于其他方法，达到同样传播效果所需的时间更少。综上可知，由于(Cncd)方法引入了核度概念，对处于网络边缘但连接度大的节点也给予了正确的定位，同时考虑了传播路径的多样性，因此能够更有效地对节点影响力进行评估。

4 结 论

本文针对当前网络节点影响力评估方法的不足，提出了一种基于路径多样性的节点核度中心评估方法，即路径多样性核度中心(Cncd)方法。该方法不同于已有网络K核分解粗略定位核层最大的节点作为影响力节点，而是同时考虑了节点在网络中的拓扑位置和局部邻域信息，通过引入路径多样性概念来提高影响力节点的定位效果。实验结果证明相对于度中心(CD)、介数中心(CB)、接近中心(CC)、K核中心(CKC)、核度中心(Cnc)等评估方法，本文提出的Cncd方法能够更有效地对关键节点进行定位和更细粒度地对节点影响力进行有效排序。

和当前绝大多数研究工作一样，本文主要针对单个节点的影响力进行评估排序，实验过程中也发现挖掘多个最具传播影响力的节点并非简单地定位一组排名靠前的节点，网络结构和社区特性均会对其产生重要的影响，因此如何挖掘网络(特别是带有社区结构的网络)中可使影响力最大化的一组关键节点值得未来进一步研究。

图5 不同时出现在各评估方法前20名的节点传播效果差异图

[1] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks.PhysicalReviewLetters, 2001,86(14):3200-3203

[2] Lü L Y, Chen D B, Zhou T. The small world yields the most effective information spreading.NewJournalofPhysical,2011,13(12) :123005

[3] Yang J, Yao C, Ma W, et al. A study of the spreading scheme for viral marketing based on a complex network model.PhysicaAStatisticalMechanics&ItsApplication,2010, 389(4): 859-870

[4] Lü L Y, Zhang Y C, Yeung C H, et al. Leaders in social networks, the delicious case.PLoSOne, 2011,6(6): e21202

[5] Zhou Y B, Lü L Y, Li M. Quantifying the influence of scientists and their publications: distinguishing between prestige and popularity.NewJournalofPhysical, 2012,14(3) :033033

[6] Freeman L C. Centrality in social networks conceptual clarification.SocialNetworks, 1979,1(3) :215-239

[7] Sabidussi G. The centrality index of a graph.Psychometrika, 1966, 31(4): 581-603

[8] Chen D B, Lü L Y, Shang M S, et al. Identifying influential nodes in complex networks.JournaloftheAmericanStatisticalAssociation, 2012, 391(4):1777-1787

[9] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks.NaturePhysical, 2010, 6(11): 888-893

[10] Basaras P, Katsaros D, Tassiulas L. Detecting influential spreaders in complex, dynamic networks.IEEEComputer, 2013, 46(4): 24-29

[11] Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks.PhysicalLettersA, 2013, 377(14): 1031-1035

[12] Liu J G, Ren Z M, Guo Q. Ranking the spreading influence in complex networks.PhysicaAStatisticalMechanics&ItsApplication,2013, 392(18): 4154-4159

[13] Joonhyun B, Sangwook K. Identifying and ranking influential spreaders in complex networks by neighborhood coreness.PhysicaAStatisticalMechanics&ItsApplication, 2014, 395(4): 549-559

[14] Shannon C E. A mathematical theory of communication.BellSystemTechnicalJournal, 1948, 27(3): 379-423

[15] Chen D B, Gao H, Lü L Y, et al. Identifying influential nodes in large-scale directed networks: The role of clustering.PLoSOne,2013, 8(10): e77455

[16] Zhang Z K, Zhang C X, Han X P, et al. Emergence of Blind Areas in Information Spreading.PLoSOne, 2014,9(4): e95785

[17] Gleiser P, L Danon. Community structure in Jazz.AdvancesinComplexSystems, 2003, 6(4): 565-573

[18] Duch J, A Arenas.Community identification using extremal optimization.PhysicalReviewE, 2005, 72(2):027104

[19] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington, USA, 2003. 137-146

[20] Knight W R. A computer method for calculating Kendall’s tau with ungrouped data.JournaloftheAmericanStatisticalAssociation,1966, 61(314): 436-439

A method for identifying and ranking influential spreading nodes in complex networks based on neighborhood core diversity centrality

Yang Xiong***, Huang Decai*, Zhan Xiuxiu***, Zhang Zike***

(*School of Computer science and Technology,School of Software,Zhejiang University of Technology, Hangzhou 310023) (**School of Computer & Information Engineering, Changzhou Institute of Technology, Changzhou 213002) (***Alibaba Research Center for Complexity Sciences,Hangzhou Normal University, Hangzhou 311121)

The study aimed to find an improved technique for identifying and ranking influencial nodes in complex networks. In consideration of current techniques’ problems of lower node locating accuracy, higher computing complexity, etc., a method to desect and extimate influential spreading nodes based on the information entropy of path diversity, called the neighborhood core diversity centrality (Cncd) method, was put forward by introducing the conception of path diversity into the traditionalK-core decomposition method to conduct the study from the perspective of information propagation. The experimental results show that, compared with other methods like degree centrality (CD), betweennes centrality (CB), closeness centrality (CC),K-core centrality (CKC) and neighborhood core centrality (Cnc), the proposed Cncdmethod can identify influential nodes more accurately and rank influential nodes more finely.

influence of nodes, degree centrality, betweenness centrality, closeness centrality,K-core decomposition

10.3772/j.issn.1002-0470.2016.02.003

①国家自然科学基金(11305043)，浙江省自然科学基金(LQ13F030015， LY14A050001)，江苏省高校自然科学基金(13KJD520001)和常州市科技计划应用基础研究(CJ20159013)资助项目。

2015-08-18)

②男，1980年生，博士生，讲师；研究方向：复杂网络，数据挖掘；E-mail: popobear801116@qq.com

③通讯作者，E-mail: hdc@zjut.edu.cn