代码编织梦想

参考文献:
Laishram R , Sariyüce, Ahmet Erdem, Eliassi-Rad T , et al. Measuring and Improving the Core Resilience of Networks[C]// World Wide Web Conference. 2018:609-618.
文献引入了核心强度核心影响,这两个属性衡量了单个节点的核心数量以及它们对节点核心数量的影响,同时本文提出了MRKC算法来增加边以提高网络的核心弹性。(这边增加边是固定的边,并且增加的方式比较好后面细讲~)
两种攻击场景:
①随机删除边
②随机删除节点

k-core:网络中的k-core是指每个节点至少有k个邻居的最大子图。
一个顶点的核数被定义为最大的k值,这样就存在一个包含该顶点的k核,并且高核中的节点被认为是网络中更中心的节点。
k-core代表节点的内聚子群,并被广泛应用于各种重要的应用,如研究互联网网络的结构,预测蛋白质的功能,或了解网络的演化。
网络G的(r, p)核心弹性用 R r ⋅ ( p ) ( G ) \mathcal{R}_{r}^{\cdot(p)}(G) Rr(p)(G)表示,直观地它预测了网络中前r%核心顺序是否在网络受到攻击时大致相同。
R r ⋅ ( p l , p u ) ( G ) \mathcal{R}_{r}^{\cdot\left(p_{l}, p_{u}\right)}(G) Rr(pl,pu)(G):聚合(r, pl, pu)的核心弹性度量
R r ⋅ ( p l , p u ) ( G ) \mathcal{R}_{r}^{\cdot\left(p_{l}, p_{u}\right)}(G) Rr(pl,pu)(G):当p从pl变到pu时的平均核心弹性

MRKC算法:k-core的最大弹性算法,即在节点核数不变的条件下,确定网络中应该加入哪些边来提高网络的弹性。
这在诸如技术网络这样的复杂网络中有着重要的应用,在这些网络中,节点可以随机、无预警地下降,我们希望在保持网络整体核心结构地同时提高网络的弹性。本文证明了MRKC可以有效地插入边,使网络对此类攻击(节点随机减少?)更具有弹性。
本文采用更通用地方法,量化了核心数的弹性以及相邻顶点对稳定性的影响,此外还提出了边插入启发法以增强核数,同时保留现有的核心分解。

核心弹性量化了当随机一致删除节点或边缘时,网络核心结构的变化程度。
R r e ( p ) ( G ) \mathcal{R}_{r}^{e(p)}(G) Rre(p)(G):表示图G的(r, p)-核心弹性对边删除的恢复力。
R r n ( p ) ( G ) \mathcal{R}_{r}^{n(p)}(G) Rrn(p)(G):表示图G的(r, p)-核心弹性对节点删除的恢复力。
定义了一个集合 M r p M_{r}^{p} Mrp
M r p = { ( K ( u , G ) , K ( u , G p ) ) : u ∈ V r } M_{r}^{p}=\left\{\left(K(u, G), K\left(u, G^{p}\right)\right): u \in V_{r}\right\} Mrp={(K(u,G),K(u,Gp)):uVr}
G p G^{p} Gp表示从图G中随机移除p%的边(或节点)得到的网络。
其中**K(u, G)**是网络中节点u的核心数量。(如果一个节点已被删除,则它在 G p G^{p} Gp中的核心数为0)
则图G的(r, p)-核心弹性由下式得到:
R r ⋅ ( p ) ( G ) = τ b ( M r p ) \mathcal{R}_{r}^{\cdot(p)}(G)=\tau_{b}\left(M_{r}^{p}\right) Rr(p)(G)=τb(Mrp)
其中 τ b ( ⋅ ) \tau_{b}\left(·\right) τb()是肯德尔等级秩相关系数。

肯德尔等级相关系数:用于反映分类变量相关性的指标,适用于两个分类变量均为有序分类的情况。
dmp值:对于一个给定的节点,在度和核心数方面的排名之间的差别应该很小。
可以通过观察dmp值,在CORE-A算法中识别异常。
使用Jaccard相似性来确定G’上的结果与G上的结果有多接近。
J α ( V α , V α ′ ) = ∣ V α ∩ V α ′ ∣ ∣ ( V α ∩ V ′ ) ∪ V α ′ ∣ J_{\alpha}\left(V_{\alpha}, V_{\alpha}^{\prime}\right)=\frac{\left|V_{\alpha} \cap V_{\alpha}^{\prime}\right|}{\left|\left(V_{\alpha} \cap V^{\prime}\right) \cup V_{\alpha}^{\prime}\right|} Jα(Vα,Vα)=(VαV)VαVαVα
Jaccard相似性:用于比较有限样本集之间的相似性和差异性。定义为A与B交集的大小与并集的大小的比值, 值越大说明相似度越高。

核心强度:是衡量当从网络中删除边时其核心数量减少的可能性。
核心影响:衡量具有较低核心数的节点对该节点自身核心数的依赖程度。
K(u, G):核心数
Γ(u,G):邻域数
节点u的核心强度是为了使u的核心数减少而需要断开连接的最小邻居数量。
CS(u,G):u的核心强度

对于网络G中的所有节点u,u由连接到∆≥(u,G)获得它的核心数量。所以节点u ∈ G 的核心强度为:
C S ( u , G ) = ∣ Δ ≥ ( u , G ) ∣ − K ( u , G ) + 1 C S(u, G)=\left|\Delta_{\geq}(u, G)\right|-K(u, G)+1 CS(u,G)=Δ(u,G)K(u,G)+1
具有高核心强度的节点具有许多冗余连接(与具有相同或更高核心数的其他节点的许多连接),因此如果其连接被删除,则不太可能丢失其核心数量。
核心强度和核心影响描述节点级属性,为了描述网络需要一个聚合度量。
C I f ( G ) C I_{f}(G) CIf(G):G中节点的核心影响力的前百分之f。
S f ( G ) S_{f}(G) Sf(G):G中核心影响等于或大于 C I f ( G ) C I_{f}(G) CIf(G)的节点集。
S f ( G ) = { u : u ∈ V ∧ C I ( u , G ) ≥ C I f ( G ) } ] \left.S_{f}(G)=\left\{u: u \in V \wedge C I(u, G) \geq C I_{f}(G)\right\}\right] Sf(G)={u:uVCI(u,G)CIf(G)}]
然后将核心强度定义为 S f ( G ) S_{f}(G) Sf(G)的平均核心强度,用 C I S f ( G ) C IS_{f}(G) CISf(G)表示:
C I S f ( G ) = ∑ u ∈ S f ( G ) C S ( u , G ) ∣ S f ( G ) ∣ C I S_{f}(G)=\frac{\sum_{u \in S_{f}(G)} C S(u, G)}{\left|S_{f}(G)\right|} CISf(G)=Sf(G)uSf(G)CS(u,G)
这个式子中的分子是所以G中核心影响等于或大于 C I f ( G ) C I_{f}(G) CIf(G)的节点的核心强度之和,分母是节点集 S f ( G ) S_{f}(G) Sf(G)中节点的个数,即最后得到的是平均核心强度。

如果一个网络具有高的 C I S f ( G ) C IS_{f}(G) CISf(G)和f,这意味着最优影响力的节点不太可能在失去与邻居的连接时丢失其核心数。我们希望这样的网络具有较高的核心弹性。
在本文的实验中有这样一个结果:P2P网络的核心弹性通常较低,而SOC网络的核心弹性在边和节点删除方面的核心弹性较高。
本文在网络中加边是指在网络中增加固定数量的边来提高网络的核心弹性,以确保即使节点或边丢失,网络仍将保持其基本的核心结构。同时还有一个附加约束,即节点的核心数量不应改变。
那么问题就是:在G中加入哪些边可以使修改后的网络G’的核心弹性尽可能高并且核心数量不改变?
节点删除可以视为特殊的边删除。(在删除节点的时候就相当于删除了该节点的所有边)
对具有高核心强度影响的节点赋予它们更高的核心强度-通过添加边来实现。

MRKC算法的两个步骤:
①生成候选边–确定哪些边可以添加到网络中,而不需要改变任何节点的核心编号。
②分配边优先级

E . i E_{.}^{i} E.i:当前正在测试的节点集。
KminKmax E . i E_{.}^{i} E.i中涉及的节点的最小和最大核数。加入 E . i E_{.}^{i} E.i只会改变节点u的核数,其中Kmin≥K(u, G)≥Kmax。所以我们不需要在添加边之后对整个网络进行k-core核心分解,而是将这些边添加到原始网络的Kmin-核心子图中,然后在子图上运行k-core核心分解。同样,因为超过Kmax的节点都不会受到影响,所以不要进行k-core分解来完成,即我们可以在找到Kmax核心之后停止。
一旦获得可以添加到网络中的一组边,MRKC将选择要添加的边的子集并根据其端点u和v为每个边(u, v)分配一个优先级,目的是为了提高具有高核心影响力的节点的核心强度。每个节点的优先级值被分配为: C I ( u ) C S ( u ) \frac{C I(u)}{C S(u)} CS(u)CI(u)

MRKC的优先级分配规则如下:
ρ ( u , v ) = { C I ( u , G ) C S ( u , G )  if  K ( u , G ) < K ( v , G ) C I ( v , G ) C S ( v , G )  if  K ( u , G ) > K ( v , G ) C I ( u , G ) C S ( u , G ) + C I ( v , G ) C S ( v , G )  if  K ( u , G ) = K ( v , G ) \rho(u, v)=\left\{\begin{array}{ll}\frac{C I(u, G)}{C S(u, G)} & \text { if } K(u, G)<K(v, G) \\ \frac{C I(v, G)}{C S(v, G)} & \text { if } K(u, G)>K(v, G) \\ \frac{C I(u, G)}{C S(u, G)}+\frac{C I(v, G)}{C S(v, G)} & \text { if } K(u, G)=K(v, G)\end{array}\right. ρ(u,v)=CS(u,G)CI(u,G)CS(v,G)CI(v,G)CS(u,G)CI(u,G)+CS(v,G)CI(v,G) if K(u,G)<K(v,G) if K(u,G)>K(v,G) if K(u,G)=K(v,G)

在每一步中,MRKC都会选择优先级最高的边并将其添加进网络中,直到达到允许添加的最大边数。
如果一个网络一开始就已经有了很高的核心弹性,MRKC就不能对其进行太多的改进。

本文献的Conclusions:
本文献讨论了捕获网络的k-core结构如何因删除的边或节点而改变的问题。为了解决这一问题提出了一种称为网络核心弹性的度量方法,这个方法测量当存在丢失的边和节点时,按核心数量排列的节点的顺序受到了多大的影响。
核心强度和核心影响力这两个度量可以一起用来告诉我们一个网络是否可能具有高核心弹性。提出了一种最大化k-core弹性方法(MRKC),在不改变任何节点核数的情况下向网络中天机阿扁,从而提高网络的核心弹性。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/weixin_44072036/article/details/111089047

Android - 秒懂TCP连接的三次握手、四次挥手-爱代码爱编程

背景 在涉及网络知识时总是记不太清相关概念,因此期望通过简短的文字描述,理解并记住相关概念。 定义 Http 协议是在 TCP 协议基础上封装的应用层协议。 所以它在建立连接的时候会经历三次握手,断开连接会经历四次挥手。 相关标识 SYN 表示建立连接,FIN 表示关闭连接,ACK 表示响应,PSH 表示有 DATA数据传输,RST 表示连接重置

Android - 秒懂TCP_UDP_IP_Socket-爱代码爱编程

背景 在涉及网络知识时总是记不太清相关概念,因此期望通过简短的文字描述,理解并记住相关概念。 TCP 属于七层协议中的传输层,是面向连接的协议。 面向连接意思就是通信双方建立连接才能通信,没建立连接不能通信。 因此是安全的。 安全可以指:能够知道通信双方,也可以指数据能够保证按顺序收到。 UDP 属于七层协议中的传输层,是面向无连接的协议。

什么是云服务器ECS?云服务器是干什么的?-爱代码爱编程

云服务器ECS(Elastic Compute Service)是阿里云提供的性能卓越、稳定可靠、弹性扩展的IaaS(Infrastructure as a Service)级别云计算服务。云服务器ECS免去了您采购IT硬件的前期准备,让您像使用水、电、天然气等公共资源一样便捷、高效地使用服务器,实现计算资源的即开即用和弹性伸缩。阿里云ECS持续提供创新型

【实验报告】网络渗透实验一 网络扫描与网络侦察-爱代码爱编程

实验目的:理解网络扫描、网络侦察的作用;通过搭建网络渗透测试平台,了解并熟悉常用搜索引擎、扫描工具的应用,通过信息收集为下一步渗透工作打下基础。 系统环境:Kali Linux 2、Windows 网络环境:交换网络结构 实验工具: Metasploitable2(需自行下载虚拟机镜像);Nmap(Kali);WinHex、数据恢复软件等 实验

华三 h3c private vlan配置-爱代码爱编程

[SWA]vlan 2 [SWA-vlan2]port  g1/0/1 [SWA]vlan 3 [SWA-vlan3]port g1/0/2 [SWA]vlan 10 [SWA-vlan10]port g1/0/3 [SWA-vlan10]private-vlan primary [SWA-vlan10]private-vlan seco

Win10 开启ping但是不关闭防火墙-爱代码爱编程

Win10 开启ping但是不关闭防火墙 面临的问题网上的解决方案方案不可行?修改方案 面临的问题 在学校的局域网内,两个不同子网/网段的PC,ping 不同,我使了下发现可以ping同对方的网关,因此可能是防火墙的问题(原理没有深究)。关闭正在使用网络的防火墙,关闭之后就可以ping通了。但是我的电脑关闭防火墙就没有任何防护了,因此不太像关

整数n拆成平方数的和 (20分)-爱代码爱编程

对于一个正整数n(<100000),想把它拆成k个不同正整数x1,x2,…,xk的平方和, 即满足n=x12+x22+…+xk^2,求x1+x2+…+xk的最大值。如果无法拆分,则输出0。 输入格式: 一个正整数n。 输出格式: 分2行,第一行为对应x1+x2+…+xk的最大值, 如果最大值不为0时,则紧接着换一行输出最小字典序的x1 x2 …x

习题3.5 求链表的倒数第m个元素-爱代码爱编程

ElementType Find(List L, int m) { int sumnumber = 0,temp=0,sum=0; List P; P = L->Next; while (P != NULL) { sumnumber++; P = P->Next;

枚举求和-爱代码爱编程

这道题是一个很简单的枚举题:给定n,m,k求: 符号意义均为数学表达中的一般意义。 符号解释:为防止读不懂符号意义,做符号解释: gcd(i,j)表示i与j的最大公因数。 表示的是k为gcd(i,j)的因子; [ ]表示当[ ]内的命题为真,则结果为1,若为假,则为0;例如[ 这道题是一个很简单的枚举题 ]等于1   输入描述: 第一

判断两个顶点之间是否存在路径-爱代码爱编程

此算法为“用邻接矩阵表示的深度优先搜索算法”简化版,DFS算法已在注释中标出,可进行对比。 visited数组用于记录遍历到的节点,若visited[i]=1和visite[j]=1,则i和j节点连通。IsOrNot函数和DFS函数如下 void IsOrNot(GraphMatrix *graphMatrix,int *visited,int sour

106. 从中序与后序遍历序列构造二叉树-爱代码爱编程

题目 思路 后序遍历的序列的最后一个元素是根节点。根据这个根节点切割、新建数组。和前序与后序遍历序列构造二叉树类似 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * T

greedy algorithm·贪婪算法·python-爱代码爱编程

来自《算法图解》 # greedy algorithm # 贪婪算法 # 使用依据:快速度,与最优解的接近度 """ 集合覆盖 某广播节目要让全国都能收听,为此需决定在那些广播台播出 每个广播台都覆盖特定区域,且覆盖区域可能重叠 目的:尽可能少的广播台播出 思路:重复选择覆盖最多未覆盖区域的电台,直到完全覆盖 ""