改进的吸收中心性方法衡量节点重要性

宁阳 天津职业技术师范大学 信息技术工程学院 宁晴 北京联合大学/北京市信息服务工程重点实验室

关键字:复杂网络 关键节点 吸收节点 最短路径

近年来，节点重要性识别研究受到越来越广泛的关注，在医学、社会学、网络安全、电力交通、政治与经济学领域有重要研究意义。例如社会网络中找到最有影响力的人控制流言的传播，疾病传播中找到易感人群，进行预防和控制，城市交通系统、电力系统中找到关键枢纽进行重点维护，降低经济损失风险等。目前关于复杂网络重要节点识别主要是在常用指标度值、介数、接近数、k-壳值基础上进行改进和将多个指标融合综合考虑节点重要性。基于多属性融合决策关键节点的研究包括基于证据理论和TOPSIS多属性决策，确定各指标的权重识别关键节点。基于网络拓扑结构，Wang等提出节点删除方法计算网络效率识别关键节点，存在破坏网络连通性的问题；Lv等提出的改进算法，将不连通节点之间距离通过网络直径解决；谭等提出的节点收缩方法将节点与邻居节点凝聚为一个节点，通过网络凝聚度衡量节点重要性。本文基于网络平均最短距离、改进节点移除方法提出改进的吸收中心性方法，解决移除节点造成的网络不连通问题，更有效的进行关键节点识别。

1 相关算法

将网络抽象为图G=(V,E)，顶点数记为N=|V|，边数记为M=|E|。图G的邻接矩阵A=（aij）N×N是一个N阶方阵，节点i和j有边，aij=1，否则为0。无向网络中节点度表示节点i的邻居节点的个数，表示为度中心性（DC）考虑局部信息，认为节点的度越大，节点越重要。如公式(1)所示：

介数中心性（BC）考虑全局信息，认为信息是通过最短路径进行传播，以经过每个节点的最短路径数目刻画节点的重要性。如公式(2)所示：

式中：njk(i)为经过节点i的节点j和节点k之间的最短路径数目，njk为节点j和节点k之间的最短路径总数目。

接近中心性（CC）是基于最短路径衡量节点重要性的指标，反映节点通过网络对其他节点施加影响的能力，反映网络的全局结构，只能应用于连通的网络中。如公式(3)所示：成的网络不连通。在新形成的网络中计算网络平均最短路径长度，通过计算网络前后平均最短路径长度变化率作为节点j对网络的影响力。网络平均最短路径长度变化越大，节点j对网络的影响力越大。例如节点8的连边吸收到节点1，如图1案例网络(a)-(b)所示。

图1 案例网络

网络平均最短路径：

网络平均最短路径变化率：

深化繁简分流，优化资源配置，着力解决案多人少矛盾；加大调解力度，法院检察院的司法调解、公安部门的行政调解、司法行政机关的人民调解，加强衔接联动，拧成一股绳，让当事人既有面子又有里子。

2.2 定义衡量节点重要性指标

本文考虑节点的邻居节点，节点i为节点j的一个邻居节点，通过2.1节计算了将节点j吸收到节点i时节点j对于整个网络信息传递的影响力，考虑节点j的所有邻居信息，综合考虑节点j的影响能力。直观反映在转移概率矩阵中即为累加转移概率矩阵中每行的值，节点j的吸收中心定义为ASC(j)：

如图1所示的案例网络，根据公式(4-6)计算如下：

图G的平均最短路径：

将节点8吸收到节点1的网络平均最短路径变化率：

转移概率矩阵如下所示：

式中：dij为节点i到节点j的最短距离。

2 吸收节点衡量节点重要性方法

2.1 构建转移概率矩阵

网络中节点i和节点j之间存在直接连边，表示两节点之间有互相转移的倾向性，无向网络可以看成是具有双向信息转移的有向网络，当信息从节点i传递到j，将以节点j为起点在网络中传播。信息的传播通常是在最短路径上进行传播，故本文结合最短路径衡量节点重要性。当信息从节点i传递到j，将节点j吸收到节点i，即将节点j的邻居节点作为接节点i的邻居节点。相比移除节点的同时移除节点的所有连边，该方法移除了节点，没有移除节点的边，避免移除节点造

3 衡量指标

3.1 传播模型

使用SIR传播模型计算标准排序结果，在典型的传染病模型中，N个节点的状态可分为3类：

S：易染状态，初始条件下所有节点的状态，该节点以β的概率被邻居节点感染；

I：感染状态，感染某种病毒作为传染源的节点，以β概率感染其邻居节点；

R：移除状态，感染状态节点以β概率感染邻居易感节点后，以γ概率变为R。

采用单源感染模型，初始时刻，假设网络中只有一个节点处于感染状态，其余个体均处于易感状态，一个单位时间内，所有处于感染状态的节点以β=0.25的概率感染其邻居节点，以γ=1的概率变为移除状态，统计达到稳定状态时，即不存在易感节点，统计处于移除状态节点和感染节点的个数衡量节点的传播能力，记为F(tc)，tc为达到稳定状态的时间。为减少β、γ参数带来的随机性，独立运行100次。

3.2 Kendall tau距离

Kendall tau距离计算两个排序列表之间成对分歧数量，K(σ,τ)表示σ、τ的差异性：

K∈[0,1]，K值越大，相似性越小。Kendall距离归一化处理，得将其用于比较一个序列与另一个类似标准答案的排序序列的相似性，得出排序序列有效性, 值越大，相似性越大。

4 实验结果与分析

为了验证本文提出的改进的吸收中心性方法识别关键点的有效性，对Physicians网络进行仿真实验。Physicians—一个节点代表一个医生，两个节点之间存在边说明两个医生对同一个话题感兴趣或者二者是朋友的关系。取网络的极大连通子图，包含117个节点，465条边。设计对比实验，验证本文提出方法的有效性和准确性。

通过各中心性算法与SIR模型Kendall tau距离相似性比较，ASC排序结果与标准排序之间相似性为0.86，次于DC相似性0.89，高于BC相似性0.84、CC相似性0.85，证明了该方法的有效性，排序精度较高。

基于SIR传播模型，对于网络中的每个节点作为初始感染节点，在t=10时刻计算F(t)与各中心性方法值的相关性。在t=10时刻基本达到稳定状态。理论上中心性值越大的节点传播感染能力F(t)越大，说明具有很强的相关性。如图2所示，BC方法与F(t)的相关性最差，ASC和CC方法与F(t)的相关性最好，而DC方法的相关性也很好，但是对于网络中度数相同的节点不能做区分，相关性略次与ASC和CC方法，在一定程度上证明了本文提出方法的有效性，且优于BC、DC方法。

图2 相关性分析图

基于SIR传播模型，依次分析本文提出方法ASC与其他方法识别出的Top10节点作为SIR传播模型的初始感染节点，在t∈[0,40]各时刻的平均感染能力。在该过程中，取两种方法各自Top10节点的差异节点作为初始感染节点进行分析，减小计算量。从图3(a-c)可以看出在t=10时刻，基本达到稳定状态。ASC识别出的Top10节点明显优于BC、DC方法识别结果，和CC识别出的Top10节点的传播能力无明显差异。说明了ASC方法的有效性，且优于DC和BC方法。

图3 TOP10节点在不同时刻感染节点数

5 结语

针对复杂网络中关键节点识别的问题，通过移除节点及其连边的效率中心性会破坏网络的拓扑结构使得移除节点后的网络不连通，在此基础上提出了改进的吸收节点中心性，吸收节点的连边，使网络保持连通性。结合网络的平均最短距离及邻居节点信息，将网络的局部信息和全局信息综合考虑。通过实验分析证明，提出的改进吸收中心性方法可以有效的识别网络中的关键节点。下一步与点权相结合，将其向有向加权网络进行扩展，进行更深入的研究。