网站首页  词典首页

请输入您要查询的论文：

　

标题 边权情形下代价指标的定量研究
范文


摘 要：传统网络抗攻击研究中通常采用度作为网络节点的重要性指标，但在现实网络中，节点的度并不是唯一的重要性判断标准。使用现实网络作为实验网络，基于代价攻击模型，使用权值作为节点的重要性指标。实验设置了对照组，将权值与度的相关程度作为变量，通过对网络的攻击效果对比判断，得出权值能够作为节点重要性指标使用于网络攻击中的结论。
关键词：代价攻击；相关度；权值
中图分类号：TP301
文献标识码：A 文章编号：1672-7800（2015）005-0032-04
作者简介：苏杨茜（1988-），女，广西南宁人，中南民族大学计算机科学学院硕士研究生，研究方向为软件工程。
0 引言
为了更加客观地对网络的抗攻击能力进行评价，网络的抗攻击性指标得到诸多学者的关注。
在网络抗攻击实验中，度作为一个重要指标被广泛使用。但在现实世界中，度仅考虑网络的拓扑结构是显然不够的，因为度小的节点或边也有可能十分重要，度相同的节点重要性也不一定相同。例如：军事占地网络中，某些节点之间的联系事关整个军事区安全，其重要程度与网络中的其它边相差很大[1]。若攻击者直接对这样的节点进行攻击，将直接对该网络造成致命性打击。因此在现实网络中，学者们采用权值来衡量节点或边的重要性程度。
1 问题提出
在对现实网络进行研究时，发现对比节点度使用权值作为攻击先后的度量指标更加科学。对于某些实际的网络权威实验室，也给出了在对应实验前提下较为合理的权值，而实验中发现这些权威的权值往往与度保持着很高的相关性。这种权值给定方式是否适用于网络的抗攻击范畴？在网络攻击中，攻击对象的先后顺序，即攻击策略，往往由该对象的重要程度决定，为了达到更好的攻击效果使网络尽快崩溃，越重要的节点或边攻击次序越靠前。在真实网络中，权值是网络中边或节点的主要度量标准之一，同样可以用作边或节点的重要性度量方式。这是否意味着与度的相关度越高的权值度量能带来更好的攻击效果？本文将使用不同的权值对网络进行攻击实验，考察网络攻击中权值与度的关系是否影响网络攻击效果。
2 基本定义
2.1 图的定义
2.3 攻击定义
网络可以定义为节点与边的集合，网络中个体为节点，两个体之间的联系为边。由此可知，网络攻击事实上是针对节点和边的攻击。因此攻击类型可以分为节点攻击和边攻击。节点攻击定义为删除一个节点的集合，边攻击定义为删除一个边的集合。
攻击过程可分为静态和动态。静态攻击指攻击过程参考初始的网络状态，攻击顺序不因攻击中网络的变化而改变。动态攻击则相反，攻击的对象顺序根据网络变化而发生变化。
从攻击顺序看，它可以是随机性或选择性的：随机边攻击即对边权网络进行攻击时，攻击顺序随机选择且不相互影响；选择性边攻击即对边权网络进行攻击时，根据网络的某项指标将边按一定顺序排列，并按照排序将边一一移除。本文中边攻击采用选择性边权攻击，先将边集按边权大小从大到小排序，再按照该顺序将边一一从网络中移除。
3 实验网络说明
3.1 数据来源说明
Usair97[6]：1997年北美航空交通网络。网络中不同节点表示不同机场，边表示两机场之间存在直飞航线，边权值对应两机场之间的航班座位数量。网络中的边为有向边。Collaborations in High-energy Physics（hep）[7]：该网络是1995年1月1日～1999年12月31日之间天体物理学领域科学家们的论文合作关系网络。边的权值指这条边出现的几率。网络中的边为无向边。
Netsecience[8]：2006年5月由 M Newman编制完成的合作关系网，合作关系的对象是研究网络理论和网络实验的科学家们。网络中的节点表示科学家，边表示两科学家的合作关系，边权表示共同完成的文章数。网络中的边为无向边。
4 实验思路
为了探究相关度（边度，边权）越高的权值度量能否为网络带来更好的攻击效果，本文使用选择性边权攻击进行实验，并使用定量分析的方式分析网络攻击效果。
在相关度的量化方式上，实验使用皮尔逊相关系数作为相关度的度量方式，本文中的相关度指边度和边权值的皮尔逊相关系数。在攻击策略上采用选择性的边权攻击，使用边权作为边的重要性度量。在攻击效果上，本文通过攻击代价和网络性能进行考量。实验将采用不同相关度的边权值进行边攻击，比较不同相关度权值之间的攻击效果差异。
4.1 相关系数和攻击策略
4.1.1 相关系数
在实际生活中往往认为度较大的节点或边更为重要，表现在数值上即为度越大其权值越大。在实验中也会认为网络中节点和边的重要性与度有着直接关系，这种关系称为相关性。为了量化边权值与度的相关性，采用皮尔逊相关系数来度量两者之间的相关程度。
p=ρx，y=cov（X，Y）σX，σY（3）
其中cov（X，Y）为X、Y的协方差，σX、σY分别是X和Y的标准差。当p>0时，两样本正相关，当p<0时，两样本负相关；当p=1时，两样本完全正相关，当p=0时，两样本不相关，当p=-1时，两样本完全负相关。计算权值和边度之间的皮尔逊相关系数，系数的绝对值越大说明该权值序列与度越相关。
4.1.2 攻击策略（选择性边权攻击）
实验将采用选择性攻击作为攻击策略，攻击对象为边。攻击采用静态攻击方式，使用边权作为边的重要性度量，优先攻击边权高的边。本文中称该攻击方式为选择性边权攻击。
选择性边权攻击中选用权值进行边的重要性度量，即边攻击的顺序按边权值由大到小进行。因此，不难看出在选择性边权攻击中，边权与边度的相关度与无权网络的攻击策略存在一定对应关系。
当p=1时，当前的边权值序列与边度序列完全正相关，意味着将边序列按权值进行排序的效果与按边度排序的效果完全一致，即当p=1时攻击效果等同于选择性边度攻击；当p=0时，边权值序列与边度序列完全无关，攻击效果等同于随机边度攻击；当p=-1时，边权序列与边度序列完全负相关，即在进行边排序时，其排序与p=1时的排序完全相反，即攻击顺序按度量指标由小到大，与选择性边攻击中按指标值由大到小相反，本文中称为选择性负边度攻击；当p>0时，边权序列与边度序列有部分正相关性，p值越接近1，边权序列更接近边度序列，p值越接近0，边权序列则越随机；同理当p<0时，边权与边度有部分负相关性，p值越接近-1，则越接近负边度攻击。
由此可以将p值与攻击策略等同起来，如图1所示。
p值与攻击策略有一定对应关系，一种攻击顺序可以对应多个p值，即任意攻击策略并不完全与p值一一对应。
4.2 攻击代价计算
若选取度作为计算代价的参数，在非带权图G=（V，E）中，假设攻击节点集或边集X∈V，在攻击后，将X从G中移除，移除之后得到G′=（V′，E′），计本次攻击的代价[9，10]为cost（X）：
cost（X）=∑v∈Xf（degree（v））（4）
根据实际情况可定义不同的f函数，同样也可以选用权值或边度与边权工作作为代价的计算参数。从网络抗攻击性的角度而言，网络抗攻击性越强（弱），攻击网络所花费的攻击代价则越高（低），因此攻击网络所花费的攻击代价直接反映网络抗攻击性的强弱。
本文目标为考察边权值作为边重要性度量的合理性，因此选用权值作为代价函数的计算参数。代价计算公式如下：
cost（X）=∑v∈Xf（weight（v））（5）
f（x）=x（6）
其中X为被攻击的边集合，攻击代价为该时间点已被移除的边集的权值之和。
4.3 网络性能和攻击效果指标
攻击实验中网络的攻击效果由攻击前后网络的性能差来衡量。对于网络性能指标，其形式并不唯一，本文采用最大连通子图的规模来衡量网络攻击效果。网络性能指标：对于初始网络G，记攻击后的网络为G′。最大连通子图用Com（G）表示，为了更好地进行比较，将最大连通子图的规模进行标准化。
E（G′）=|com（G′）||G| （7）
当最大连通子图中节点数等于原始网络的节点数时，E=1；当网络中全为散点，没有连通子图时，E=0，也即E∈[0，1]，E越大网络总体性能越好。
有了网络性能指标，即可通过网络的性能差来计算攻击效果。网络攻击前后的性能差则是本次攻击的效果，计算公式如下：
ΔE=E（G′）-E（G″）（8）
5 实验结果与分析
5.1 实验权值选取
为了综合考虑网络的拓扑和网络实际情况，实验采用边权值作为边度量指标，即在实验中边攻击按照权值从大到小依次进行。这种攻击方式本文中称之为选择性边权攻击。
为了对比不同p值边权情形下的攻击效果，本文中对每个网络选取4组边权进行实验。这4组边权选取分别如下：
（1）S1：将边度逆序作为权值序列。S1中的权值为边度的逆序，即权值序列和边度序列完全负相关，因此对应有P（S1，edge_degree）=-1。
（2）S2：选取的p值为近似0的随机序列。S2的选取考虑复杂网络中度符合幂律分布的特点，权值取符合正态（0，1）分布的随机数（正值），选取的边权序列均满足 P（S2，edge_degree）≈0。
（3）S3：选取权威实验室给出的边度序列。S3为权威实验室给出的边度序列，即原始数据中的边权值，这些权值均由密歇根大学复杂系统研究中心等权威网络研究实验室给出，经过计算P（S3，edge_degree）∈[0.6，0.9]，说明两者部分正相关。
（4）S4：选取边度作为权值序列，即P（S4，edge_degree）=1。
4组边权值对应的p值如表3所示。
由相关度值可以看出，S1对应负选择性边权攻击，S2近似于随机性边权攻击，S3对应部分正相关的选择性边权攻击，S4对应选择性边权攻击。
5.2 实验结果
在边攻击下实验网络的抗攻击效果如图2-图4所示。在图中横轴为攻击的代价，纵轴为网络性能。攻击性能曲线下降得越快，攻击效果越好；若攻击曲线下降慢，攻击效果则较差，采用这种攻击方式将需要更高的代价才能达到攻击效果。
由分段攻击效果表可以看出：S1的攻击效果最好，并且在每一分段中都十分稳定。S1的攻击效果与其它3种攻击策略有着较大差距。
在表7中，明显可以看到usair97中p值越高的攻击权值序列带来的攻击效果越差，当边权值与边度呈负相关时攻击效果最好。在hep和nets网络中同样也可以看到S1的攻击效果值/攻击难度最小，但并不是p值越大的攻击序列带来的攻击效果越差。Hep中攻击效果最差的是I（S3，COST=1），即p=0.9607的边权，nets攻击效果最差的是p近似于0的边权攻击。
综上可知，从数值和曲线上看，攻击效果最好的是S1权值，S2、S3、S4的攻击效果较为相近，但是都比S1差。因此在该实验前提下，当权值与边权负相关时攻击效果最好，当p≠-1时，p值与攻击效果没有明显的线性相关性。
5.3 分析与结论
从攻击策略而言，S1对应负选择性的边度负攻击，S2对应随机边度攻击，S3对应近似的选择性边度攻击，S4对应选择性边度攻击；从网络度角度而言，选择性边度应该是破坏网络效能的最好攻击方式，但在本次实验结果中，负选择性边度攻击却有最好的攻击效果；从攻击过程考虑，选择性边度攻击从边度最大的节点开始进行，边度越大的边相连节点的节点度也越大，所以刚开始进行边攻击时并不能很快改变最大连通子图的节点数。而负选择性边度攻击从边度最小的边开始移除，边度小的边连接的节点节点度较小，即移除这样的边后更容易产生散点，最大联通子图的规模更容易变小。从实验结果也可以看出，3个实验网络中选择性边度攻击的攻击效果曲线与其余曲线相差较大，说明其攻击效果优于其它攻击方式。即从边度小的边进行攻击时，网络最大子图规模减小的现象极易发生。因此，负选择性边度攻击效果更好是建立在网络效能由最大连通子图来度量的基础之上。
从相关度角度而言，随着相关度p的增大，3个实验网络中只有一个表现出攻击效果随之变差，另外两个网络中攻击效果最差发生在p≈0的随机攻击，一个发生在p≈1的近似选择性边度攻击。因此在本实验前提下，权值与边度的相关度大小对于边权攻击策略的攻击效果并未表现出明显的相关性。
6 意义
在网络节点和边的权值计算上，学者们一直未能给出科学合理的拟定方式，权威的实验室往往通过大量统计数据和网络本身的拓扑给出权值，而人们往往也认为度越大的节点或边对应的权值也越大。本文从权值与边度相关性的角度出发进行了网络抗攻击性实验，结果表明：此实验前提下负选择性边度攻击的攻击效果最好；权值与边度的相关度大小对于边权攻击策略的攻击效果并未表现出明显的相关性。本文对网络权值的拟定方式及其合理性程度判断提供了数据参考，并采用真实的网络数据进行实验，实验结果更接近实际，这不仅可为实验室中的网络数据模型提供数据，同时也可为现实网络应用提供参考。
参考文献：
[1] 黄丹.考虑代价的无标度网络抗攻击性研究[D].武汉：中南民族大学，2011.
[2] A NAIR，JM VIDAL.Supply network topology and robustness against disruptions–an investigation using multi-agent model[J].International Journal of Production Research，2011，49（5）：1391-1404.
[3] WANG B， TANG H W， GUO C H，et al.Entropy optimization of scale-free networks robustness to random failures[J].PhysicaA，2005.
[4] 周漩，张凤鸣，周卫平，等.利用节点效率评估复杂网络功能鲁棒性[J]. 物理学报，2012（19）：1-7.
[5] 杜巍，蔡萌，杜海峰.网络结构鲁棒性指标及应用研究[J].西安交通大学学报，2010（4）：93-97.
[6] Pajek datasets[EB/OL].http：//vlado.fmf.uni-lj.si/pub/networks/data/.
[7] E J NEWMAN M. The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences， 2001，98（2）：404-409.
[8] E J NEWMAN M.Finding community structure in networks using the eigenvectors of matrices.Phys[C].Rev. E. 2007.
[9] 吴泓润，覃俊，郑波尽.基于代价的复杂网络抗攻击性研究[J].计算机科学，2012（8）：224-227.
[10] BOJIN ZHENG，DAN HUANG，DEYI LI，et al.Some scale-free networks could be robust under the selective node attacks[J].EPL，2012（94）：28010-28015.
（责任编辑：黄 健）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/2/10 23:53:43