文件标题：网络韧性的改善与度量

6090测量和改善网络的核心韧性0RickyLaishram雪城大学雪城，纽约州rlaishra@syr.edu0Ahmet ErdemSarıyüce布法罗大学布法罗，纽约州erdem@buffalo.edu0TinaEliassi-Rad东北大学波士顿，马萨诸塞州eliassi@ccs.neu.edu0Ali PinarSandia国家实验室阿尔布克雷克，新墨西哥州apinar@sandia.gov0SuchetaSoundarajan雪城大学雪城，纽约州susounda@syr.edu0摘要0k-cores的概念对于理解网络的全局结构以及识别网络中的中心节点非常重要。了解网络的k-cores的韧性对于攻击和删除边缘（即损坏的通信链路）非常有价值。我们提供了网络核心韧性的正式定义，并研究了如何通过网络的结构特征来描述核心韧性的问题：特别是哪些结构特性导致网络具有高或低的核心韧性？为了衡量这一点，我们引入了两个新的节点属性：核心强度和核心影响力，它们分别衡量了个体节点的核心数的韧性以及它们对其他节点核心数的影响。基于这些属性，我们提出了最大化k-core韧性（MRKC）算法，通过添加边缘来改善网络的核心韧性。我们考虑了两种攻击场景-随机删除边缘和随机删除节点。通过对各种技术和基础设施网络数据集进行实验，我们验证了我们基于节点的韧性度量在预测网络韧性方面的有效性，并评估了MRKC在改善网络核心韧性方面的任务。我们发现，对于边缘删除攻击，MRKC相比于最佳基准方法，将网络的韧性提高了11.1％，而最佳基准方法只能将网络的韧性提高2％。对于节点删除攻击，MRKC将原始网络的核心韧性平均提高了19.7％，而最佳基准方法只能将其提高3％。0CCS概念0• 计算数学 → 图论；图算法；近似算法；路径和连通性问题；0关键词0图；韧性；k-core；0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861270ACM参考格式：Ricky Laishram，Ahmet Erdem Sarıyüce，TinaEliassi-Rad，Ali Pinar和SuchetaSoundarajan。2018年。测量和改善网络的核心韧性。在WWW2018：2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318612701 引言0k-cores已成为理解网络的全局结构以及识别网络中的“中心”节点的重要概念。网络的k-core[21]是最大的子图，使得每个节点至少有k个邻居。顶点的核心数定义为存在包含该顶点的k-core的最大k值，而较高核心中的节点被认为在网络中更为中心。k-cores代表着节点的凝聚子群，并且已在广泛的重要应用中使用，例如研究互联网网络的结构[8]，预测蛋白质的功能[2]或理解网络的演化。有许多应用程序依赖于网络的核心结构（第3.1节）。因此，了解网络的核心结构对节点和边缘被删除（即损坏的路由器或通信链路）的攻击的韧性非常有价值。我们定义网络G的（r，p）-core韧性，表示在随机删除p％的边缘或节点之前和之后，前r％的节点的核心数排名之间的相关性。R∙（p）r（G）为我们提供了关于网络的丰富信息：直观地说，它衡量了即使网络受到攻击，网络中前r％核心数节点的核心排序是否保持大致相同。由于核心数是中心性的度量，（r，p）-core韧性决定了最中心的节点是否继续是最中心的节点。我们还提出了一个聚合的（r，pl，pu）-core韧性度量（R∙（pl，pu）r（G）），定义为当我们从pl变化到pu时的平均R∙（p）n（G）。我们研究了如何通过网络的结构特征来描述核心韧性的问题：特别是哪些结构特性导致网络具有高或低的核心韧性？为了衡量这一点，我们引入了两个新的节点属性：核心强度和核心影响力。我们表明，在来自各种领域的真实世界网络中，核心强度和核心影响力是网络核心韧性的有效预测因子（第4.5节）。这使得基础设施的设计者或运营商能够通过改善网络的核心韧性来提高网络的性能。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France0.830.840.850.86012345Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France6100添加的边缘（％）0核心韧性0图1：添加边缘以增加TECH_Router网络的k-核的韧性。MRKC方法显示为红色，并且优于基准方法。0计算机或其他技术网络在攻击发生之前评估网络的强度。基于这些特征，我们提出了一种算法，称为最大化k-核的韧性（MRKC），以确定应该添加到网络中的哪些边以提高其韧性，同时限制节点的核心数不变。这在复杂网络（如技术网络）中具有重要应用，其中节点可以随机且无警告地丢失，并且我们希望提高网络的韧性同时保持其整体核心结构。我们展示了MRKC通过11.1％和19.7％分别改善了核心韧性，对抗边缘删除和节点删除，而最佳基准方法只能提高2％和3％。图1展示了MRKC和基准方法在TECH_Router网络中对核心韧性改进的比较。我们在第5.3节中详细介绍了我们的结果以及其他网络上的结果。我们的贡献可以总结如下：0（1）我们提出了核心韧性度量，用于描述网络的核心结构在节点和边缘丢失时的韧性。（2）我们引入了两个简单的基于节点的度量，核心强度和核心影响力，以快速有效地预测网络的核心韧性。（3）我们提出了一种新颖的算法，用于向网络中添加边缘以增加其核心韧性，同时保持核心数不变。（4）我们在各种真实网络数据集上进行实验证明，我们的算法在增加网络的核心韧性任务上优于一组基准方法。02 相关工作0在本节中，我们描述了关于核心分解和评估k-核韧性的先前文献。核心分解：Erdős和Hajnal[11]在1966年描述了第一个与k-核相关的概念，定义了图的退化性。0作为图中顶点的最大核心数。Matula引入了min-max定理[17]来描述相同的概念，但是在图着色的背景下。同时，Seidman[21]和Matula和Beck[16]定义了k-核子图，作为每个顶点至少具有k度的最大连通子图。Seidman指出k-核是可以用来找到更密集子结构的良好种子床，但是没有提供找到k-核的原则性算法[21]。另一方面，Matula和Beck[16]给出了找到顶点核心数和找到图的所有k-核（及其层次结构）的算法，通过使用这些核心数，因为对于相同的k值可能存在多个k-核。Batagelj和Zaversnik引入了一种使用桶数据结构来找到顶点核心数的高效实现[6]。与之前的工作[16,21]相比，他们将k-核定义为可能是不连通的子图。核分解在最近几年引起了极大的兴趣，被用于可视化[3]和互联网拓扑分析[5]等应用中。由于k-核分解的实际效益和线性复杂度，最近有很多工作在不同的数据类型或设置中适应k-核算法。Cheng等人[9]引入了第一个外部存储器算法，Wen等人[23]和Khaouid等人[15]在这个方向上提供了进一步的改进。Giatsidis等人将k-核分解适应了加权[13]和有向[12]图。为了处理现实世界数据的动态性质，Sariyuce等人[20]引入了第一个流算法，以在边插入和删除时维护图的k-核分解。受到现实网络数据的不完整和不确定性的启发，O'Brien和Sullivan[18]提出了在不了解整个图的情况下局部估计顶点的核心数（K值）的新方法，Bonchi等人[7]展示了如何在不确定图上高效地执行k-核分解，该图的边缘具有存在概率。核韧性：只有少数几项研究研究核分解的敏感性。与我们的工作最相关的是Adiga和Vullikanti的研究，他们研究了在采样和噪声网络中核心的鲁棒性[1]。他们报告说，在采样和噪声下恢复顶级核心的成功表现出随样本和噪声量的非单调行为。另一项相关研究是由Zhang等人[24]进行的，他们最近提出了折叠k-核问题来找到关键顶点。对于给定的k值和预算b，他们引入了删除b（关键）顶点的算法，以获得最小的k-核（按大小）。在我们的工作中，我们采用了一种更通用的方法来量化核心数的韧性，并量化了邻居顶点对稳定性的影响。此外，我们提出了插入边的启发式方法，以增强核心数，同时保留现有的核心分解。03 核韧性0在许多网络应用中，我们可能会遇到删除边缘或节点的问题。例如，在技术网络中，由于通信链路中断，边缘可能会丢失，在路由器网络中，由于路由器关闭，节点可能会丢失。因此，了解网络的k-核的韧性是很有价值的。0.20.40.60.80.400.450.500.550.250.500.750.400.450.500.55Mpr =K(u,G),K(u,Gp) : uVr·(p)r(G) = τb Mpr(1)R ·(pl,pu )r(G) =upl Rr(G)dxpup(2)6110核韧性0Jaccard相似度0（a）异常检测结果。0核韧性0Jaccard相似度0（b）社区检测结果。0图2：完整网络G和样本G'中发现的异常值（图2a）和社区（图2b）之间的相似性。x轴是不同网络的核韧性（Rn(0,50)50(G)）对节点删除的影响，y轴是Jaccard相似度。如预期，在核韧性高的网络中，样本上的结果与整个网络上的结果更加相似。0本节中，我们介绍了核韧性的概念，它量化了当节点或边缘以均匀随机方式删除时，网络的核结构发生变化的程度。我们将网络G的（r，p）-核韧性定义为原始网络中前r%个节点（按核数排序）与随机删除p%的边缘或节点后的网络之间的等级相关性。我们用Re(p)r(G)表示图G对边缘删除的（r，p）-核韧性，用Rn(p)r(G)表示图G对节点删除的（r，p）-核韧性。我们将用R∙(p)r来表示一般的（r，p）-核韧性。设G =�V，E�为一个网络，Gp表示从G中随机删除p%的边缘（或节点）得到的网络。设G中按核数排名前r%的节点为Vr。定义一个集合Mpr，使得0其中K(u,G)是节点u在网络G中的核数。（如果节点已被删除，则其在Gp中的核数为0。）那么，G的（r，p）-核韧性由以下公式给出：0其中τb(∙)是Kendall'stau-b等级相关性。（我们可以用任何其他等级相关性度量替换τb(∙)。）虽然R∙(p)r可以在不同水平的边缘或节点删除时对网络的不同核心的核韧性提供丰富的详细信息，但在某些应用中，使用更简单的度量可能更可取。因此，我们定义了一个综合度量，即（r，pl，pu）-核韧性。我们将网络G的（r，pl，pu）-核韧性定义为在p从pl到pu变化时的（r，p）-核韧性的平均值。我们用R∙(pl,pu)r(G)表示G的（r，pl，pu）-核韧性。0在实践中，我们用步长为1的求和来近似方程2中的积分。0需要注意的是，有许多图的鲁棒性度量，但核韧性的概念特别关注网络的k-核结构，因此与这些现有度量没有直接关系。为了验证这一点，我们将各种实际网络的自然连通性[14]与核韧性进行了比较，并没有观察到任何显著的相关性。由于篇幅限制，我们没有包含这些结果。由于根据方程1计算核韧性并不总是实际可行的，因此根据网络的结构特征确定网络的韧性高低具有很大的实际意义。因此，在第4节中，我们将讨论如何根据快速计算的结构特性来表征网络的核韧性问题。03.1 激励应用0核心弹性的概念在k-核结构对于缺失边缘或节点的网络很重要的应用中很有帮助。在本节中，我们将讨论两个这样的应用程序，即异常检测和社区检测，它们在采样数据上使用k-cores。假设我们有一个网络G = �V，E�和一个子图G' =�V'，E'�，其中G'是G上的随机游走的结果。如果我们在G'上执行异常检测[22]或社区检测[19]，那么G'上的结果如何反映G中的真实异常和社区？因为这些应用程序使用了k-核结构，我们期望结果更接近于原始图的结果，如果原始图具有较高的核心弹性。我们在多个真实网络上进行实验证实了这一点，我们使用的样本是由随机游走生成的，其节点数量为网络的一半。03.1.1异常检测。在这个应用中，我们使用[22]中提出的CORE-A方法在完整网络G上执行异常检测，以找到异常节点Vα。该方法基于这样的直觉，即具有高核心数的节点也具有高度。因此，对于给定的节点，度和核心数之间的差异（在[22]中称为dmp）应该相对较小。然而，异常节点（例如，社交网络中付费获取更多关注者的人）与这种模式显著偏离。通过查看节点的dmp值，可以在CORE-A算法中识别异常。我们使用相同的方法在子图G'中找到异常，并将这些异常的集合称为V'α。然后，我们使用Jaccard相似性确定G'上的结果与G上的结果的接近程度。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, Franceranking in terms of the degree and core number (referred to asdmp in [22]) should be fairly small. However, anomalous nodes(for example, someone in a social network who paid to get morefollowers) deviate significantly from this pattern. By looking atthe dmp values of the nodes, the anomalies are identified in theCORE-A algorithm.We find anomalies in the subgraph G′ with the same method,and refer to the set of these anomalies as V ′α . We then use JaccardSimilarity to deteon G′ is to that on G.∆<(u,G) = {v : v ∈ Γ(u,G) ∧ K(v,G) < K(u,G)}∆=(u,G) = {v : v ∈ Γ(u,G) ∧ K(v,G) = K(u,G)}∆>(u,G) = {v : v ∈ Γ(u,G) ∧ K(v,G) > K(u,G)}∆ (u,G) = ∆=(u,G)∆>(u,G)Vδ = {u : u ∈ V ∧ |∆=(u,G)| < K(u,G)}.CS(u,G) = ∆ (u,G)K(u,G) + 1.(3)6120J α ( V α , V' α ) = 交集(V0交集(V α , V ′) ∪ V' α交集的大小。我们在图2a中呈现结果。我们可以观察到，在具有较高核心弹性的网络中，样本中发现的异常更类似于完整网络中的异常。03.1.2社区检测。通过找到网络的中心区域，k-cores可以用于加速社区检测。我们使用[19]中提出的方法和Louvain方法在原始网络G上进行社区检测。我们用C表示G中的社区。然后，我们使用相同的方法在G'上进行社区检测，得到社区C'。我们计算C和C'之间的相似性，即C'中的社区与C中最佳匹配社区之间的平均Jac- card相似性。0J c ( C , C' ) = 1/ | C' |0�0c ∈ C'0| c ∩ β ( c , C )0| c ∪ ( β ( c , C ) ∩ V'0其中 β ( x , Y ) 是一个将社区 x 映射到另一个社区 y 的函数，使得 | x∩ y |，且没有其他 x' ∈ X 映射到y。图2b显示了这些实验在社区检测上的结果。在具有更高核心弹性的网络中，样本中被分组在同一社区的节点在原始社区中也更频繁地被分组在一起。唯一的例外是两个P2P网络，尽管它们具有相对较高的核心弹性，但相似性较低。这是因为原始网络中几乎没有社区，只有一个巨大的社区。因此，对于大多数 c ∈ C'，β ( c , C ) =�。这两个应用程序表明，如果我们知道网络的核心弹性，我们可以将其用作对不完整数据上基于核心的观察反映原始数据的指标。04 描述核心韧性0直接计算网络的 ( r , p )-核心韧性在许多情况下是不实际的，因为它需要重复进行 k-核心分解。因此，通过不直接计算网络的 ( n , p )-核心韧性来描述网络的核心韧性是有价值的（正如我们将看到的，这种描述允许我们开发一种有效的算法来提高网络的核心韧性）。在本节中，我们提出了两个基于网络结构的节点属性：核心强度和核心影响。节点的核心强度是一个衡量其核心数在网络中删除边时可能减少的程度的指标。节点的核心影响是一个衡量核心数较低的节点在其核心数方面依赖该节点的程度的指标。0数字取决于该节点的核心数。在第4.3节和第4.2节中，我们更详细地描述了核心影响和核心强度属性。我们还基于网络中节点的核心强度和核心影响定义了一个整体网络属性。我们在第4.4节中对此进行了更详细的描述。我们对各种类型的真实世界网络进行实验，以展示这些度量与网络的核心韧性之间的关系。04.1 符号表示0在描述核心影响和核心强度属性之前，我们首先介绍我们的符号表示。让 K ( u , G ) 和 Γ( u , G ) 分别表示节点 u 在 G中的核心数和邻居节点集合。我们将节点 u 的邻居分为三个集合 ∆ <( u , G ) 、 ∆ = ( u , G ) 和 ∆ > ( u , G )，分别表示核心数小于、等于和大于 u 的邻居节点。0我们还定义了一个节点集合 V δ ，其中每个节点 u ∈ V δ至少有一个邻居节点 v ，其核心数更大，即 K ( u , G ) < K ( v , G )。这也意味着以下内容：04.2 核心强度0节点 u 的核心强度是需要断开的 u 的邻居节点的最小数量，以使 u的核心数减少。我们用 CS ( u , G ) 表示 G 中节点 u的核心强度。对于网络 G 中的所有节点 u ，u 的核心数取决于与 ∆≥ ( u , G ) 的连接。因此，节点 u ∈ G 的核心强度由以下公式给出：0直观地，节点 u的核心强度描述了在失去连接时它保持其核心数的可能性。具有较高核心强度的节点具有许多冗余连接（即与其他具有相等或更高核心数的节点的连接），因此如果其连接被删除，它更不可能降低其核心数。运行时间：给定网络 G = � V ,  E �，计算所有节点的核心强度在进行 k -核心分解后是可能的，这需要O ( | E | )的时间。对于每个节点，我们需要计算具有更大或相等核心数的邻居节点的数量，这在边的数量上也是线性的，即 O ( | E | )。因此，计算所有节点的核心强度的时间复杂度为 O ( | E | ) 。04.3 核心影响0节点 u 在网络 G 中的核心影响是节点 u对核心数较低的邻居节点的核心数产生影响的程度的度量。对于节点u ，依赖于 u 的核心数的节点集合是 V δ ∩ ∆ < ( u , G )。考虑两个节点 v 0 ， v 1 ∈ V δ ∩ ∆ < ( u , G ) ，0Track：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂0.40.50.60.70.80.9100.30.40.510Sf (G) = u : uVCI (u,G)CIf (G) ]CISf (G) =.(5)2https://snap.stanford.edu/3http://networkrepository.com/Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France6130核心影响力-强度0核心弹性0（a）边缘删除的核心弹性0核心影响力-强度0核心弹性0（b）节点删除的核心弹性0图3：各种网络的核心弹性（R ∙（0，50）100（G））对核心影响力-强度（CIS95（G））的影响。图3a显示了核心弹性对边缘删除与核心影响力-强度的关系，图3b显示了核心弹性对节点删除与核心影响力-强度的关系。我们可以观察到，核心弹性对于具有更高核心影响力的网络来说更高，这与我们的预期一致。0其中v0和v1至少需要具有m'0和m'1个具有更高核心编号的节点0K（v1，G）。然后v1对∆ >（v1，G）的依赖性比v0对∆>（v0，G）的依赖性更强。为了解决这个问题，v1需要将其核心影响力的更大部分贡献给∆ >（v1，G）。因此，对于v ∈V，我们引入一个权重δ（v，G），使得v对∆>（v1，G）贡献δ（v，G）∙ CI（v，G）。0δ（v，G）= 1  -  | ∆=（v，G） |0K（v，G）0再次考虑节点v0和v1，并假设它们具有m0和m1个具有更高核心编号的邻居，并且m0 （v，G）中的所有节点。现在，我们用数学方式定义u的核心影响力0CI（u，G）= �0v ∈ Vδ ∩ ∆0δ（CI（0| ∆ >（v，G） | . （4）0要计算G中所有节点的核心影响力，我们将所有值初始化为1（可以使用任何正数）。然后我们开始计算具有最小核心编号的节点的核心影响力，并继续直到达到具有最大核心编号的节点。因为节点的核心影响力仅受到具有较低核心编号的节点的影响，所以我们只需要一次迭代来计算所有节点的核心影响力。10运行时间：为了计算G = � V，E�中所有节点的核心影响力，我们首先需要执行k-核心分解（O（| E|））。然后我们需要找到所有节点u的∆=（u，G），∆>（u，G）和∆ <（u，G）。这可以在O（| E|）中执行。然后我们在O（| V |）中找到集合Vδ。我们可以在O（| V|）中分配所有节点的核心影响力（使用公式4）。因此，总体计算需01核心影响力也可以定义为考虑具有相等核心编号的节点，除了较低的节点。然而，我们发现对于两种定义，整体结果都是相似的，并且一次迭代足以处理具有较低核心编号的公式。04.4 核心影响力-强度0核心强度和核心影响力描述了节点级别的属性。为了描述网络，我们需要一个综合的度量。假设CIf（G）是G中所有节点的核心影响力的f百分位数。让Sf（G）是G中核心影响力等于或大于CI f（G）的节点集。0然后我们将核心影响力-强度定义为Sf（G）的平均核心强度。我们用CIS f（G）表示它，0� u ∈ Sf（G）CS（u，G）0如果一个网络在高f值下具有高CIS f  ( G )，这意味着当它们失去与邻居的连接时，最有影响力的节点不太可能降低其核心数。我们期望这样的网络具有较高的核心弹性。相反，CIS f  ( G ) 较低的网络预计具有较低的核心弹性。04.5 实验0为了验证CIS是否反映了实际的核心弹性，我们对22种不同类型的真实网络进行了实验（表1）。这些网络是从SNAP 2和NetworkRepository 3下载的。边缘删除的核心弹性（R ∙ ( 0 , 50 ) 100 ( G )）与核心影响力强度（CIS 95  ( G )）的关系如图3a所示，节点删除的核心弹性与核心影响力强度的关系如图3b所示。在这些图中，每个点都是一个网络的核心弹性（以网络类型进行颜色编码），是10次实验的结果。我们观察到，如预期的那样，对于具有较高核心影响力的网络，其弹性较高。然而，核心影响力强度和核心弹性之间的关系是次线性的，即它在低值时迅速增加，但对于高值的网络而言，增加较慢。ASAS_733_19990309†4759889612Oregon1_010331†106702200217Oregon1_010428†108862249317BIOBIO_Dmela‡73932556911BIO_Yeast_Protein‡184622035CACA_GrQc†52411448443CA_HepTh†98752597331CA_Erdos992‡509475157INFINF_OpenFlights‡29391567728INF_Power‡494165945P2PP2P_Gnutella08†63012077710P2P_Gnutella09†81142601310P2P_Gnutella25†22687547055SOCSOC_Hamsterster‡2426166304SOC_Advogato‡5167394325SOC_Wiki_Vote‡88929149TECHTECH_Pgp‡106802431631TECH_Routers_rf‡2113663215TECH_WHOIS‡74765694388WEBWEB_Spam‡47673737535WEB_Webbase‡1606225593326140类型 网络 | V | | E | k max0表1：在此表中，| V | 是节点数，| E | 是边数，k max是最大度数。这些数据集是从SNAP（用†表示）和NetworkRepository（用‡表示）下载的。0核心影响力强度的差异对核心弹性没有显著影响。此外，我们观察到P2P网络的核心弹性通常较低，而SOC网络的核心弹性在边缘和节点删除方面倾向于较高。05 提高核心弹性0在许多类型的网络（如技术网络）中，边缘或节点可能会随机丢失。因此，我们可能有兴趣添加一定数量的边缘来提高网络的核心弹性，以确保即使丢失节点或边缘，网络仍保持其基本的核心结构。一种简单的方法是添加边缘以增加k壳之间的间隙（即通过添加壳内边缘，从最高壳开始）。然而，这将改变核心数的分布，这是网络的一个重要属性[4,10]。因此，我们添加了一个额外的约束条件，即节点的核心数不应改变。形式上，我们考虑以下问题：给定一个无向、无权网络G和一个边缘预算b，我们应该添加哪些b个边缘到G中，以使修改后的网络G'的核心弹性尽可能高，同时核心数不变？05.1 边缘删除和节点删除0我们在两种情况下定义核心弹性，即边缘删除和节点删除。请注意，节点删除可以视为0边删除的特殊类型，当删除一个节点时，它的所有边也会被删除。在本节中，我们展示了由于边删除和节点删除而导致的核心弹性之间的关系。考虑一个图 G = � V ,  E �。G 的 ( r , p ) -core弹性由 R n ( p ) r( G ) 和 R e ( p ) r ( G)（根据定义）给出，分别对应节点删除和边删除。假设删除 p个节点导致删除 p ′ 条边。合理地假设 p ′ >p，因为现实世界的网络很少具有平均度为1。也就是说，R e ( p ′ ) r( G ) ≈ R n ( p ) r ( G )，并且一般情况下 R e ( p ) r ( G ) ≥ R e ( p ′) r ( G )。因此，R n ( p ) r ( G ) ≤ R e ( p ) r ( G)。现在让我们考虑边删除和节点删除下的 ( r , p l , p u )-core弹性。0R n ( p l , p u ) r ( G )  − R e (p l , p u ) r ( G )  =0≤  p up l0≤ R n ( x ) r ( G )  − R e (x ) r ( G ) ≤ dx0p u  −0R n ( p l , p u ) r ( G )  ≤ R e ( p l , p u ) r ( G )(6)05.2 提出的方法：MRKC0在本节中，我们解决了通过添加固定数量的边来改善网络的核心弹性的问题。我们在第4节中的初步结果表明，应该添加边来增强具有高核心影响力的节点，即给它们更高的核心强度。我们提出了一种名为Maximize Resilience of k-core(MRKC)的新算法。节点删除可以被看作是边删除的特殊情况，因为删除一个节点等价于删除该节点的边。因此，改善网络对边删除的核心弹性的算法与改善网络对节点删除的核心弹性的算法相同。MRKC算法包括两个步骤：生成候选边和分配边优先级。我们在5.2.1和5.2.2节中详细讨论这些步骤。05.2.1 生成候选边。给定一个网络 G = � V ,  E�，MRKC的第一步是确定哪些边可以添加到网络中而不改变任何节点的核心编号。令 E ′ 为在 G 中不存在的边的集合。E ′ 的大小大约为 |V |2。这显然是太多的边需要检查，因此我们需要一种快速过滤掉那些如果添加到 G中会改变核心编号的边的方法。MRKC通过适应[20]中描述的基于purecore的方法来实现这一点，该方法检查每个潜在边的端点（节点 u的purecore是与 u 具有相同核心编号的节点的集合，可能会受到 u的核心编号变化的影响）。我们用 PC(u, G) 来表示图 G 中节点 u的purecore。我们将 E ′ 分为两个集合 E sim 和 Edif，使得对于所有 (u, v) ∈ E sim，有 K(u, G) = K(v, G)；对于所有(u, v) ∈ E dif，有 K(u, G) ≠ K(v, G)。从集合 E sim中，我们生成子集 E i sim，使得：0• 对于所有的 E sim 中的边，都属于 E i sim。 • 对于所有的 Ei sim 和 E j dif，它们是不相交的。0•  E i sim中没有两条边通过具有相同核心编号的节点连接。0因为所有的边的端点都不在对方的purecore中，所以我们可以将 E ′插入到 G 中，如果有一个节点发生变化0研讨会: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France0.600.650.700123450.350.400.450.500123450.8700.8750.8800.8850.8900.8950123450.500.520.540.560.580123450.830.840.850.860123450.500.550123450.8800.8850.8900.8950.9000123450.520.540.560123456150新增边的百分比0核心弹性0(a) AS_733_1999 (边删除)0新增边的百分比0核心弹性0(b) AS_733_1999 (节点删除)0新增边的百分比0核心弹性0(c) INF_OpenFlights (边删除)0添加的边数（%）0核心韧性0(d) INF_OpenFlights (节点删除)0添加的边数（%）0核心韧性0(e) TECH_Router (边删除)0添加的边数（%）0核心韧性0(f) TECH_Router (节点删除)0添加的边数（%）0核心韧性0(g) WEB_Spam (边删除)0添加的边数（%）0核心韧性0(h) WEB_Spam (节点删除)0图4：不同真实网络中新添加的边的百分比对核心韧性的影响。y轴为核心韧性，x轴为不同算法添加的新节点的百分比。左列的图（图4a,4c,4e,4g）是边删除的情况，右列的图（图4b,4d,4f,4h）是节点删除的情况。在所有情况下，MRKC优于基准算法。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France.(7)200400600123456160核心数，我们可以确定E'中的哪条边引起了它。假设有nsim个这样的子集。同样，我们按照相同的方式将E dif 分成E idif的子集，但是有额外的条件，即如果E idif中有两条具有相同端点的边，则其他两个节点的核心数不能相同。同样，在这种情况下，如果将E idif添加到G中，节点的核心数会发生变化。0任何节点的更改，我们可以确定Eidif中的哪条边引起了这种变化。假设有ndif个这样的子集。然后，我们不需要逐个检查所有|E'|条边，只需要检查n sim + ndif次。我们还可以加快候选边的生成。假设Ei∙是当前正在测试的节点集合。令k min和kmax为Ei∙中涉及的节点的最小和最大核心数。那么，添加Ei∙只能改变核心数满足k min ≥ K(u,G) ≥ kmax的节点u。因此，我们不需要在添加边之后对整个网络进行k-核心分解，而是将边添加到原始网络的kmin-核心子图中，并对子图进行k-核心分解。同样，因为不会影响核心数大于kmax的节点，所以我们不需要完全运行k-核心分解-在找到kmax-核心后可以停止。05.2.2分配边的优先级。一旦获得可以添加到网络中的边的集合，MRKC根据其端点u和v为每条边(u,v) ∈E'分配优先级。如前所述，目标是提高具有高核心影响力的节点的核心强度。因此，每个节点u的优先级值被分配为CI(u)0CS(u)。根据u和v的核心数，有三种情况需要考虑：(a) K(u,G) >K(v,G)，(b) K(u,G) < K(v,G)，以及(c) K(u,G) = K(v,G)。在K(u,G) >K(v,G)的情况下，添加边(u,v)只会影响CI(v,G)，CI(u,G)不受影响。另一方面，如果K(u,G) =K(v,G)，添加(u,v)会影响CI(u,G)和CI(v,G)。因此，对于所有的(u,v)∈ E'，MRKC按照以下优先级进行分配：0ρ(u,v) =0�0CI(u,G) CS(u,G) if K(u,G) < K(v,G) CI(v,G) CS(v,G) ifK(u,G) > K(v,G) CI(u,G) CS(u,G) + CI(v,G)0如果 K(u,G) = K(v,G)，则 CS(v,G)0在每一步中，MRKC选择优先级最高的边并将其添加到网络中，直到达到预算，即允许添加的最大边数。在插入任何边(u,v)之后，集合E'需要更新，但我们可以通过仅检查那些具有端点在PC(u,G) ∪PC(v,G)中的边来使其高效。核心影响力和核心强度的更新也可以以类似的方式进行。05.3实验0为了评估MRKC，我们在真实网络中添加了最多5%的新边缘，以提高它们的核心韧性。我们用于实验的网络在表2中给出。如第5.2节所述，添加边缘以提高核心韧性仅适用于某些类型的网络。例如，在社交0添加的边缘（%）0时间（秒）0图5：我们的方法在不同网络上改进核心韧性（MRKC）的运行时间。x轴是添加的新边的数量（以%表示），y轴是添加边的时间（以秒为单位）。网络，我们不能强迫人们建立连接。然而，为了完整起见，我们在实验中包括了这些类型的网络。为了比较，我们考虑了三种基准方法，其中E'中的边缘是按照（1）随机方式（RANDOM），（2）端点度数之和的递减顺序（DEGREE），以及（3）端点核心数之和的递减顺序（CORE）添加的。我们每个实验运行10次，并呈现平均值。在图4中，我们展示了MRKC和三个基准方法添加边缘后的核心韧性的比较。y轴是核心韧性，x轴是添加的边的百分比。由于空间限制，我们无法呈现所有网络的图表，因此当添加了5%的新边时，我们在表2中给出它们。我们观察到MRKC优于所有考虑的基准方法。在初始核心韧性较低的情况下，MRKC可以大幅改善它（例如在INF_Power，B