0 引言

近些年来, 学者们对复杂网络的研究正处于火热阶段, 其思想已经渗透到各学科研究之中.现实生活中的许多行为都可以抽象成复杂网络, 比如交通网、社交网、蛋白质基因相互作用网等^[1].几乎每一个网络中, 都存在着一个或者多个关键节点并在网络中占有非常重要的位置, 如果删除这些关键节点, 这个网络就有可能在结构和稳定性上受到很大的影响^[2].例如, 在社交网络中, 如果删除了其中重要的节点, 那么消息的传播会受到影响, 但同样也可以通过删除这些节点来抑制谣言的传播.所以, 挖掘网络中的关键节点对于认识网络特征、了解网络传播过程、保持网络结构等有着非常重要的意义.

识别网络中的关键节点存在很多种算法.大多数的算法都是利用网络的结构信息, 为每个节点分配一个值, 然后根据这个值决定节点的排名顺序^[2].最容易想到的就是利用节点的局部特征度数(Degree Centrality, DC)(DC算法, 又称为度中心算法)来判断节点的重要性^[3], 这是判断关键节点最直观简单的方法.但是利用节点局部特征的算法具有一定的缺陷, 比如忽略了节点邻居的作用以及整个网络的拓扑结构, 仅考虑单一因素使得节点重要性评判的依据不够充分.鉴于节点的重要程度和其邻居节点存在一定的联系, 有些学者提出了介数中心性^[4]、特征向量中心性^[5]、接近度中心性^[6]等, 还有人考虑将PageRank算法^[7]、H-index算法^[8]以及累计提名算法^[9]用于节点重要性排序中.介数中心性、特征向量中心性以及接近度中心性均从网络的全局角度出发, 在评估节点重要性方面有了明显的效果, 但这类算法时间复杂度都非常高, 不适用于大规模的网络. PageRank算法最初用于网页排序, 该算法认为节点的重要性由指向它的其他节点的数量及重要性决定, 算法效果较好但是很容易陷入悬挂节点, 并且不适用于节点连接紧密的网络. H-index算法通过统计论文引用数来评价学者的学术能力, 将该算法运用在节点重要性排序中也取得了良好的效果.累计提名算法是利用节点声望的迭代评判节点的重要程度, 但以上两种算法均未从网络的拓扑结构综合地考虑节点的重要性. Chen^[10]等人提出了LocalRank算法, 该算法不仅利用了直接邻居的信息, 还利用了四阶邻居信息, 虽然算法效果较好, 但是忽略了信息传播的过程.随着熵理论在复杂网络复杂性及不确定性研究中的应用, 文献[11]的作者将熵理论应用到关键节点识别中, 并取得了良好的效果.由于网络的结构和信息的传播有关, Kitsak^[12]等人认为节点在网络中的位置对节点的重要性有一定的影响, 于是提出将$K$-shell分解算法($K$s算法)应用到关键节点识别中, 其主要思想是不断地去除网络中度数小于或等于$k$的节点, 直到所有的节点都分配到一个$K$-shell$(K\mathrm s)$值, 根据这个$K$s值判断节点的重要性. $K$-shell分解算法可以很好地显示网络的中心节点, 具有良好的时间复杂度, 但这是一种粗粒化的算法, 所以经常会面临大量节点分配到相同$K$s值的情形.为了克服$K$-shell分解算法带来的这种缺点, 有些学者通过增加节点的额外信息来分解网络, 从而提高算法的分辨率. Zeng等人提出了一种称为MDD(Mixed Degree decomposition)的混合度分解算法, 即删除节点后, 同时考虑网络中剩下的邻居节点以及删除的邻居节点的度数, 然后按照混合$K$s值来递归删除网络中的节点^[13].文献[14]提出了一种基于两端节点的边加权算法, 即w$K$s(weighted $K$-shell)算法, 该算法在划分节点的度中加入了加权边$\omega _{ij} $, 引入加权边从而重新定义节点的混合Ks值.以上两种混合$K$s值方法均有效地增加了分层的层数, 提高了对节点重要性的判别.还有一部分学者通过对节点获得的$K$s值处理来区分每个节点的重要性. Bae等人提出了核心中心性的算法, 认为每个节点的得分应该是邻居的$K\mathrm s$值之和(C$_{\mathrm {nc}^+}$算法)^[15].文献[16]首先定义每个节点的L$K$SS(Local $K$-shell Sum)值等于节点两跳内的邻居的$K$s值总和, 然后基于L$K$SS, 节点最终的EL$K$SS(Extended Local $K$-shell Sum)值为邻居节点的L$K$SS之和(EL$K$SS算法). Ruan等人认为节点的重要性与连接的边有关系, 在计算节点得分时加入了节点的网络连接系数, 每个节点的最终得分为邻居节点的核数与连接系数乘积之和^[17].

大多数算法仅从单方面改进传统的$K$-shell分解算法, 且仅仅考虑了自身的$K$s值, 但这些是远远不够的.所以本文从两个角度来改进$K$-shell分解算法, 提出了E$K$SDN算法.首先, E$K$SDN算法通过增加节点的点权信息克服了传统$K$-shell分解算法的弊端; 其次, 基于有较多邻居节点且位于网络核心的节点影响力更大的思想, E$K$SDN算法加入了节点度指标以及目标节点两跳内节点的$K$s值, 进一步提升了算法识别关键节点的能力.几个真实网络的实验结果表明, 本文提出的E$K$SDN算法在关键节点识别中可取得较好的效果.本文后续的安排:第1节介绍相关工作和算法; 第2节介绍相关的实验; 第3节总结全文并对未来研究方向进行展望.

1 相关工作和算法 1.1 $K$-shell分解算法

对于任一无权网络, 一般用$G=(N, E)$表示, $N$代表网络中的节点数, $E$代表网络中的边数.通常用$e_{i, j} $来表示节点$i$和节点$j$之间是否存在边, 如果存在, 则$e_{i, j} =1$; 否则, $e_{i, j} =0$.

一个节点的度定义为其邻居节点的个数, 即$k_i =\sum\limits_j^N {e_{i, j} } $.一般地, 度数越大的节点意味着其邻居节点的数量越多.度指标仅仅只考虑了节点的邻居节点数量, 然而节点所处的位置对节点重要性也起到一定作用.度数较小但处于网络核心的节点, 其重要性较大.度数大但处于网络边缘的节点, 其重要性也较小. $K$-shell分解算法是一种基于节点位置的粗粒度划分方法, 核心思想是根据节点度数递归地删除网络中的节点.分解过程如下.

(1) 首先计算网络中节点的度数, 删除节点度数为1的节点及其相连的边, 更新网络再重新计算度数, 再删除度为1的节点, 直到网络中不存在度数为1的节点, 记这些删除的节点$K$s=1.

(2) 递归地删除网络中节点度数小于等于2的节点及其相连的边, 之后更新网络并重新计算度, 记$K$s=2.

(3) 对于更新之后的网络, 让度数为$i(3, 4, \cdots, k)$的节点重复上述过程, 直到每个节点都被赋予$K$s值, 记$K$s=$k$.

1.2 改进的算法

加权网络中存在边权的概念, 边权就是一条边两个节点的度数之和, 即边的权重.边权用$\omega _{ij} $表示, 定义为

$ \begin{align} \omega _{ij} =k_i +k_j. \end{align} $

(1)

与边权相对应的是点权, 又叫做点强度(Vertex Strength).点权定义为与它有关联的边权的总和, 为

$ \begin{align} {S}_i =\sum\limits_{j\in {T}_i }^N {\omega _{ij} }, \end{align} $

(2)

其中, ${T}_i $为节点$i$邻居节点的集合, $N$为网络中的节点数.

针对传统$K$-shell分解算法所面临的大量节点分配到相同$K$s值的现象, 本文基于文献[12]提出的加权边$\omega _{ij} $, 将加权网络中点权和边权的概念引入到无权网络, 通过增加点权等信息来分解网络, 从而克服了传统$K$-shell分解算法的弊端, 提升了算法的分辨率.定义每个节点的混合$k_m $值为

$ \begin{align} k_m =k_i +\lambda \times S_i. \end{align} $

(3)

计算每个节点的混合$k_m $值, 然后根据这个$k_m $值按照$K$-shell的分解规则来分解网络. $\lambda $的取值范围为$0\sim 1$, 经过多次实验证明, $\lambda $取值为$0.45\sim 0.55$效果最佳, 且优于$\lambda $的其他取值仅0.01%.由此可见, $\lambda $的取值对实验效果影响较小, 所以本文选取$\lambda =0.5$.由于$k_m $值不是一个整数, 所以采用向下取整的方式来计算节点的$K$s值.经过分解之后, 每个节点都会获得一个$K$s值.

为了进一步提升算法识别关键节点的能力, 基于关键节点与位于网络核心的节点有更多连接的思想, 所以本文在计算目标节点重要性时加入该节点两跳内节点的$K$s值.由于判断节点重要性的因素较为单一, 并且节点的度数在一定程度上反应了节点的影响力, 所以在判断节点重要性时, 又融入了节点的度指标.因此, 定义每个节点的E$K$SDN值为

$ \begin{align} \mathrm{E}K\mathrm{SDN}=K\mathrm s_i \times k_i +\sum\limits_{j\in \Gamma _i }^N {Ks_j \times k_j }, \end{align} $

(4)

其中, $\Gamma _i $为与节点$i$相隔2跳之内节点的集合, $N$是网络中节点的个数.

为了比较各种算法的差异, 对于图 1给出的简单网络模型, 本文分别用几种算法对其分解, 进而获得了节点重要性的排序结果并对结果进行了分析.

表 1所示的是节点重要性排序结果.从表中可以看出前4种算法都存在大量的拥有相同值的节点; 本文的E$K$SDN算法很好地判断了图 1所示网络的节点重要性, 它能够区分节点1、节点2、节点3以及节点4, 也能够区分节点7、节点9、节点23和节点24.因而本文提出的E$K$SDN算法相比于其他算法效果稍好.

2 实验结果 2.1 数据集

每个网络的拓扑结构不同, 本文实验将在4个真实网络中进行: ① Karate Club网络是一个社会网络, 它是经过对美国一个大学空手道俱乐部观测而构建的^[18]; ② NetScience网络是一个从事网络理论和实验科学家合著的关系网络^[19]; ③ Email网络是西班牙一所大学的电子邮件网络, 包含教师、研究生、技术和管理人员^[20]; ④ Blogs网络是联合美国两个政治阵营的博客构建的^[21]. 表 2显示了这4种网络的一些统计特性, 其中, $N$表示网络中节点的数量, $E$代表边数, $ k$为网络的平均度数, $ C$为平均聚类系数, $ d$是平均最短路径, $\beta _{\rm th} =\frac{k}{k^2}$, 该值表示网络理论上的传播阈值.

2.2 评估模型

本文使用文献[15]中的单调性指标(Monotonicity)评估算法效果, 因为该指标量化了排序结果内节点分数的关系, 所以选取单调性指标评估不同算法的分辨率, 且分辨率代表了节点的传播能力.在任一算法中, 网络中的每个节点均会分配到对应的分数, 如果大多数节点的得分不同, 则说明节点重要性划分得更加细腻.得分相同的节点越少, 则单调性指标越大.单调性指标的定义为

$ \begin{align} M(R)=\left[ {1-\frac{\sum\limits_{r\in R} {n_r (n_r -1)} }{n(n-1)}} \right]^2, \end{align} $

(5)

其中, $R$代表将要排序的数据向量, $n$为$R$中元素的个数, $n_r $表示的是$R$中相同得分的节点的数目.如果每个节点的得分都不同, 意味着排序结果完全单调, 则$M\left( R \right)$为1;如果每个节点的得分相同, 即排序的结果全部相同, 则$M\left( R \right)$为0.

在关键节点识别研究中, 通常会选择3种模型来模拟信息传播: SI(Susceptible-Infectious)模型、SIS(Susceptible-Infectious-Susceptible)模型以及SIR(Susceptible-Infectious-Recovered)模型.这3种模型均是度量节点传播影响力时广泛使用的工具.由于SIR模型广泛运用在描述人群中的信息和谣言传播过程中, 所以本文使用该模型来评估节点的传播能力, 从而衡量网络中节点的重要性^[22-23].在SIR模型中, 主要存在3种个体:易感染个体$S$、感染个体$I$以及免疫个体$R$.

初始的时候, 在网络中随机选择一个或者多个节点作为感染个体$I$, 其他的节点为易感染个体$S$.每一个时间步内, 如果一个易感染个体$S$与一个或者多个感染个体$I$相连, 则它会按照某个概率变成感染个体$I$.除此之外, 感染个体$I$也会依照某个事先预定的治愈率变成免疫个体$R$.每个时间步, 这些演化规则在网络中并行执行, 直到网络中不存在感染个体$I$, 然后按照最终感染的节点个数来衡量节点的传播效率.

为了进一步验证算法的性能, 将SIR仿真模拟的实验结果和算法的结果进行比较.本文采用肯德尔相关系数(通常用希腊字母$\tau $来表示)判断两者之间的相似性.将SIR模型仿真的结果视为随机变量$X$, 算法的结果当成随机变量$Y$, 它们的元素个数相同, 均为$N$, 随机变量的第$i$个值用$x_i $和$y_i $分别表示.从排序结果中构造序列对$\left( {x_i , y_i } \right)(i=1, 2, \cdots, N)$, 如果同时满足$x_i >x_j $且$y_i >y_j $, 或者满足$x_j >x_i $且$y_j >y_i $, 则$\left( {x_i , y_i } \right)$和$\left( {x_j , y_j } \right)$是一致的; 如果$x_i >x_j $且$y_i <y_j $, 或者$x_j >x_i $且$y_j <y_i $, 则这两个序列是不一致的.除此之外, 如果满足$x_i =x_j $或者$y_j =y_i $, 那么就可以认为$\left( {x_i , y_i } \right)$和$\left( {x_j , y_j } \right)$既不是一致的, 也不是不一致的^[24].两个随机变量的肯德尔相关系数$\tau $定义为

$ \begin{align} \tau \left( {X, Y} \right)=\frac{c-d}{\frac{1}{2}n(n-1)}, \end{align} $

(6)

其中, $c$和$d$分别表示$N$对$\left( {x_i , y_i } \right)$序列中一致的数量以及不一致的数量, $n$是排序向量中的元素个数, 肯德尔相关系数$\tau $可以用来判断不同排序结果的相似性, $\tau $值越大, 则相似性越高, 反之相似性越低.

2.3 算法性能分析

本文的实验均是在Windows10操作系统下进行, 开发语言为python.一共进行了3项实验, 实验结果与分析如下.

实验一:为了进一步了解排名结果的分布情况, 本文画出了4种网络中各种算法的累积分布函数(Cumulative Distribution Function, CDF)图像, 如图 2所示. CDF图像中横坐标表示节点得分, 纵坐标表示对应横坐标值所出现的概率.从图 2中可以看出:在前两种网络(Karate Club和NetScience)中, E$K$SDN算法的排名分布最广, $K$s算法的排名分布最窄.在Email网络和Blogs网络中, E$K$SDN算法和w$K$s算法的排名分布相近.综上, 通过排名结果的CDF图像可知, E$K$SDN算法相对其他几种算法在区分关键节点上较有优势, 所得的结果分布也更广.

实验二:实验一的结果仅仅展示了各种算法的排名分布情况, 但是不能直观地反映出排名的内部情况.由于单调性指标能够很好地考虑排序结果的内部情况, 因此, 表 3给出了各种算法对应不同网络的单调性指标.从表 3中可以看出, 原始$K$s算法的效果最差, 原因在于很多节点被分配到相同的$K$s值, 这正是此算法的弊端; DC算法仅仅考虑了节点的度数, 虽然分辨率较高, 但是判断节点重要性的依据过于简单, 可信度较小; MDD算法在小型网络(Karate Club)中的性能高于w$K$s算法, w$K$s算法在NetScience网络和Blogs网络中分辨率值均高于MDD算法; C$_{\mathrm {nc}^+}$算法在4种网络中的分辨率指标都较高.本文提出的E$K$SDN算法相较于其他5种算法有了一定的提升, 特别是在Email网络中具有很好的分辨率.

实验三:从图 3中得到以下信息. Karate Club网络中, 各个算法的波动都比较大, MDD算法与w$K$s算法走势相似, $K$s算法的效果稍逊于其他算法.在NetScience网络中, 初始时DC算法和$K$s算法效果较好; 但是当感染概率大于理论传播阈值$\beta _{\rm th} $之后, 这两种算法的效果较差, 而E$K$SDN算法和C$_{\mathrm {nc}^+}$的算法效果较好. Email网络中, 各种算法走势都比较相近, 效果相差不大. 图 3(d)中, E$K$SDN算法和C$_{\rm nc^+}$算法均呈先上升后下降的走势, 其余算法均呈下降趋势.总而言之, 本文提出的E$K$SDN算法表现更加稳定, 特别是当感染概率大于理论传播阈值$\beta _{\rm th} $时效果都优于其他算法.

3 总结

关键节点识别在复杂网络的研究中具有重要的理论和实践意义.本文提出了E$K$SDN算法, 首先通过加入网络节点的边权来细分节点的核数(混合$k_m $值), 然后基于节点和邻居的关系, 用节点及两跳之内节点的核数和度数来计算每个节点的最终得分.值得一提的是, 这种算法不仅考虑了网络的全局指标核数, 也考虑到了网络的局部指数度, 从而更加全面地评判节点重要性.在实验部分, 本文通过CDF图像和单调性指标分别比较了各算法的实验效果, 同时还运用了SIR模型模拟网络信息的传播, 并将得到的节点的传播能力与算法得出的排序结果进行了比较, 各项实验结果证明本文提出的E$K$SDN算法较优于其他算法.接下来的研究中会将该算法应用到SI模型和SIS模型等传播模型中.考虑到本文提出的E$K$SDN算法仅适用于无权网络, 所以下一步的研究方向将会扩展到加权网络中, 同时会把网络规模对重要节点识别的影响纳入到研究中.