英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

---

基于Kshell算法的复杂系统节点中心性衡量

摘要

有影响力的传播者是在复杂网络中最大化影响或控制传播的关键角色。使用kshell分解方法来识别富有影响力的传播者在最近一段时间变得非常流行。在文献中，核心节点即网络中具有最大kshell指数的节点被认为是有影响力的传播者。我们已经使用易感-感染-恢复(SIR)流行病模型研究了kshell方法和节点的传播形态，以根据其在网络中的拓扑位置来理解关键节点的行为。从研究中，我们发现核心区域的每个节点都不一定是最关键节点。即使是战略位置较低的壳节点也可能是最关键的节点。此外，核心区域也可以位于网络的外围。现有的指标方法仅设计用于从核心节点而不是从较低的外壳中识别最关键的节点。在这项工作中，我们提出了一个kshell混合方法，不仅从核心，也从较低的外壳来确定关键的节点。该方法包括kshell指数、节点度、接触距离和多阶邻居潜在影响力等参数。使用九个真实网络数据集对所提出的方法进行了评估。就传播力度而言，实验结果表明，该方法优于现有的其他指标方法，如kshell方法、邻域中心性、混合度分解等。此外，通过考虑三阶邻居节点的潜在影响力，所提出的方法也可以应用于大规模网络。

关键词：复杂网络；最关键节点；传播能力；Kshell混合方法；SIR流行病模型

1.介绍：

在现实世界的许多领域，传播是一种普遍现象，如疾病传播，流行病，连锁故障，博弈论，反应扩散，信息传播等等。在复杂网络中，有影响力的传播者在最大化或控制影响力传播中起着至关重要的作用。这些关键节点在许多应用中具有实践和理论意义，如减缓病毒传播的、在社交网络上宣传新产品、级联失效控制和防御、控制网络谣言传播等。

近年来，关于确定关键节点的研究有很显著的势头。现有一些方法可以在文献中找到关键节点。Bae等将这些方法大致分为两类:“寻找个体影响者”(根据其传播能力对网络中的个体节点进行排序)和“寻找多个影响者”(以最终集体影响最大的方式找到最佳节点集)。“拓扑度量”和“基于动态的度量”是第一类中两种流行的方法。中心性方法如度中心性，k-壳分解方法是拓扑度量的几个例子。另一方面，在基于动态的度量中，存在诸如接近中心性和页面排名的基于传播动力学的特定假设而设计的中心性方法，例如最短路径距离和随机行走。第二类，即寻找多重影响者，主要是根据病毒式营销制定的，在病毒式营销中，通过形成最佳节点集，最终的集体影响被最大化。在这种方法下，最优渗流，独立级联模型和线性阈值模型是寻找最优种子节点集的常用方法。这两类方法，即寻找单个影响者和寻找多个影响者，在不同目的的不同应用中都是很有用的。

第二类，即寻找多个影响者，主要用于寻找信息传播过程的发起者(种子节点)，例如，在社会经济和社会网络中。而第一类，即寻找个体影响者，用于识别有影响的发起者和传播过程的控制者。识别控制者是大有裨益的，因为它有助于我们控制或停止传播过程。例如，在一次流行病爆发中，或者一个谣言在一个地方传播，通常是由第一个被感染的人引起的。通过了解个体的传播能力，我们可以控制疫情或谣言的来源。据观察，中心性方法在发现网络中的个体影响者方面是卓有成效的。由于我们的重点是寻找能够最大化或控制网络传播的关键节点，我们依赖于基于中心性的度量。

如上所述，在文献中存在许多中心性方法。其中一种方法是Kshell分解法(详见第4节)。从kshell方法获得的最大kshell指数被称为网络的最内层外壳或核心。最内层的壳或核心节点比许多研究人员声称的其他较低的壳指数节点更有影响力。为了理解网络中最关键节点在拓扑位置方面的行为，我们使用SIR流行病模型分析了核心和下壳节点的传播行为。分析结果表明，核心区域的每个节点并不总是最有影响力的扩散者。即使是战略位置较低的外壳节点也可能比真实网络中的一些核心节点更有影响力。我们还观察到网络的核心节点可以位于外围。现有的指标方法不能揭示下壳节点具有高度影响的性质。因为那些指标方法基于核心节点是最关键节点的假设。

为了克服现有指标方法在当前工作中的局限性，我们提出了Kshell混合方法及其扩展版该方法不仅关注于核心节点，而且在较低的壳节点中寻找最有影响的扩散者。在传播过程中，许多因素导致节点成为网络中最关键节点。在设计可行的方法之前，需要对这些因素进行详细研究，以使网络中的传播最大化。根据基林等人的观点，核心群体和网络中从发起者到其他个体的距离是传播过程中的重要因素。马和张等认为传播发起者不仅影响最近的邻居，而且影响邻居的邻居。这发生在邻居的许多层次。另一方面，Bae等人已经指出，当网络的完整全局结构不可用时，度也是决定节点的局部影响的重要参数。基于这些分析，我们在我们提出的kshell混合方法中考虑以下参数(1) kshell指数(2)节点的度(3)网络中一个节点和其他节点之间的接触距离(4)多阶邻居的潜在影响力。为了评估我们提出的方法的有效性，我们使用了SIR流行病模型。它衡量网络中每个节点的传播效率。从我们的实验中，我们观察到所提出的kshell混合方法及其扩展版能够识别比其他最先进的指标方法更关键的节点，例如度中心性、介数中心性、接近中心性、kshell方法、邻域中心性、混合度分解(MDD)等等。本文的主要贡献是:

它提出了一个新的理论，发现网络中的每个核心节点并不总是最关键节点，而是一些较低的壳节点也可以更有影响力。它还发现核心可以位于复杂网络的外围。

我们提出了一种新的基于网络结构的无权网络kshell混合方法来衡量节点的中心性。

论文的其余部分组织如下:第二部分提供了对艺术作品现状的回顾。第三部分用一些例子说明了问题，第四部分讨论了建议的方法。第五部分给出了实验和结果。最后，在第六部分中总结了结论。

2.相关著作：

自上个世纪以来，已经提出了各种中心性方法，例如，度中心性、介数中心性、接近中心性以及特别是kshell分解方法来识别复杂网络中有影响的传播者。接下来，我们讨论了这些方法的一些状态，包括kshell方法，在此基础上我们提出了关键节点测量技术，kshell混合方法ks_h及其扩展版ks_h 。

图1 图示是一个有着13个顶点与18条边的小型网络

表1 给出了在beta;_th =0.31与beta; =0.35时SIR排名结果

表2 四个网络Jazz、Odlis、Hamsterster和PowerGrid的网络结构属性

4.Kshell混合方法：

在这里，我们讨论提出的kshell混合方法ks_h及其扩展版ks_h 。所提出的方法是kshell分解方法的扩展。我们在提出的方法中考虑了以下参数：(1) kshell指数(2)节点的度(3)接触距离(4)多阶邻居的影响潜力。在讨论所提出的方法之前，我们提供了一般的图定义，并讨论了如下的kshell分解方法。

图2。a、b、c和d分别显示了以下数据集的传播效率(标为SIR): Jazz、PowerGrid、Odlis和Hamsterster。在图中，核心节点用天空颜色标记，而较低的外壳节点用其他颜色表示。(要解释此图图例中对颜色的引用，读者可以参考本文的网络版本。)

图3 由Gephi工具产生的Netscience网络的可视化。绿色节点是最里面的外壳或核心节点。

4.1.图形定义

我们使用未加权网络G = lang;V，Erang;，其中V是节点或顶点的数量，E是边或关系对的数量。网络可以表示为邻接矩阵A = a_mn isin; R_VXV，其中如果节点m和n连接，则a_mn = 1，否则a_mn = 0。

4.2.Kshell分解方法

kshell分解方法(标记为ks)根据网络的现有度，通过迭代地移除节点来为网络的每个节点分配kshell指数。该方法从移除所有度k为1的节点开始，并将kshell指数ks =1分配给那些被移除的节点。上述过程持续到直到网络中所有剩余节点的度k都大于1。对于度k为2的节点，遵循类似的过程，并分配kshell值ks=2，然后继续该过程，直到网络中不再存在节点。最后，我们根据每个节点的kshell指数对其进行排序。最大的kshell指数被称为网络的最内层外壳或核心。

4.3.提出的kshell混合方法

节点m的kshell混合方法ks_h定义为：

（1）

其中phi;m:节点m的邻居集合。

k(n):节点n的度，

micro;：度势k(n)上的正可调参数

alpha;(mn)：两个节点m和n的kshell指数

d(mn)：节点m和n之间最短路径的距离

alpha;(mn)、d(mn)、k(n)和phi;m的讨论如下：

4.3.1. Kshell指数alpha;(mn)

让我们考虑节点m和n，kshell指数是ks_m和ks_n。我们将这两个kshell指数相加测量综合影响力。在方程中，平方根用于归一化kshell指数对（1）中其他参数的影响因素。

（2）

4.4 k(n)度

受Bae等的启发，当整体结构不可用时，度是决定节点局部影响力的可靠参数。因此，度将作为传播过程中的一个重要参数。在(1)中我们使用了参数可调的k(n)度势。该参数控制网络中度的影响，并且随着网络中传播影响的改善而变化。其范围介于0和1之间。节点n的度(k)由入射到节点上的边数定义。

（3）

其中n是焦点节点，而节点j是节点n的邻居。

4.4.1.接触距离d(mn)

受Keeling等人的启发，接触距离是给定传播过程中的一个重要参数，我们在提出的ks_h方法中使用该参数d(mn)。为了计算接触距离，我们没有使用任何现有的最短路径算法，如Dijkstra或bellman–ford法。这些算法的时间复杂度非常高。为了优化所提出的ks_h方法的计算时间，我们提出一个附加了最短路径距离的算法如下。

从一个节点到其直接邻居的距离是1，到其下一阶邻居的距离是2。这样，我们在计算节点m的邻域集phi;m时，给每个节点分配最短路径距离，前提是给出phi;m的 r = 3的距离范围 (详见第5.1.4节)。

表3 展示出了基于kshell混合方法ks_h、扩展版kshell混合方法ks_h 和SIR流行病模型对于图1的节点排名。

4.4.2. 邻域集(phi;m)

我们知道一个节点可能会受到其邻居的影响，我们将其命名为邻居的潜在影响力。为了衡量这一点，我们考虑了alpha;(mn)、k(n)和d(mn)以及一个附加参数。附加参数是节点m的邻居集phi;m。考虑参数phi;m背后的原因是节点的影响力不仅仅关系到它最近的邻居，而且它还可以流过多阶邻居。其中多阶邻居阶数的距离范围(r)是根据网络直径设置的，并且必须大于0。在邻域集合phi;m中，我们考虑那些到节点m的距离小于或等于r范围的节点。为了优化计算时间复杂度，在我们的实验中，我们设置了邻居等级距离范围r =3。邻域集phi;m的最佳距离范围r在第5.1.4节中讨论。

4.5. 扩展kshell混合方法

扩展的kshell混合方法ks_h 是公式（1）的改进。5.2节的结果显示了ks_h 相对于ks_h的改进，同时检验了所提出的方法在真实数据集上的有效性。ks_h 计算节点的邻居ks_h值。节点m的ks_h 定义为：

（4）

其中psi;m是节点m最靠近的邻居。

一个现有的例子。这里我们提出了一个建议的ks_h和ks_h 方法的推导。我们还将结果与SIR排序进行了比较。在这种情况下，我们使用如图1所示的网络。应用公式（1）计算节点e的ks_h，如下所示:

其中，我们设置micro;= 0.4，邻居级别距离范围r = 3。因此，节点e的邻居集为phi;e= {a,g,f,b,c,d,h,i,j}。

节点e的ks_h 的推导计算如下

其中psi;e = {g，f，a}

表3给出了ks_h、ks_h 和SIR流行病方法的等级。在表中，我们看到ks_h和ks_h 将节点e和f排在第二位，核心节点b、c和d排在第三位。从这个表中，我们观察到ks_h和ks_h 等级相对类似于SIR等级，其中SIR的等级表明较低的壳节点的传播影响要高于一些核心节点。

表4

描述网络结构特性，其中V是顶点数，E是边数，beta;_th是传播临界值，beta;_exp是实验中使用的感染概率，micro;是所提出方法的可调参数ks_h，d是网络直径，lang;krang;是平均度，

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[239251]，资料为PDF文档或Word文档，PDF文档可免费转换为Word