基于拓扑势的网络毁伤最大算法.pdf
《基于拓扑势的网络毁伤最大算法.pdf》由会员分享,可在线阅读,更多相关《基于拓扑势的网络毁伤最大算法.pdf(7页珍藏版)》请在咨信网上搜索。
1、第 卷第期 年月系统工程与电子技术 文章编号:()网址:收稿日期:;修回日期:;网络优先出版日期:。网络优先出版地址:通讯作者引用格式:俞锦涛,肖兵,熊家军基于拓扑势的网络毁伤最大算法系统工程与电子技术,():犚犲 犳 犲 狉 犲 狀 犮 犲犳 狅 狉犿犪 狋:,():基于拓扑势的网络毁伤最大算法俞锦涛,肖兵,熊家军(空军预警学院信息对抗系,湖北 武汉 ;空军预警学院预警情报系,湖北 武汉 )摘要:针对攻击代价相等时的有限资源网络毁伤问题,给出了网络毁伤最大化的定义。为了改进近似求解算法求解毁伤最大化问题时复杂度较高的缺陷,提出了基于拓扑势和()的()算法。利用无标度网络和实测网络进行实验,结
2、果表明,算法在计算速度上有较大的提升,网络平均毁伤效果接近于近似求解算法;且优于采用常见重要性度量指标排序算法得到的平均毁伤效果。所提方法可从网络毁伤的角度为复杂网络关键节点挖掘提供参考。关键词:复杂网络;拓扑势;毁伤最大化;算法中图分类号:文献标志码:犇犗犐:犖犲 狋 狑狅 狉 犽犱 犪犿犪 犵 犲犿犪 狓 犻 犿 犻 狕 犪 狋 犻 狅 狀犪 犾 犵 狅 狉 犻 狋 犺犿犫 犪 狊 犲 犱狅 狀狋 狅 狆 狅 犾 狅 犵 狔狆 狅 狋 犲 狀 狋 犻 犪 犾 ,(犇犲 狆犪 狉 狋犿犲 狀 狋狅 犳犐 狀犳 狅 狉犿犪 狋 犻 狅 狀犆狅 狌 狀 狋 犲 狉犿犲 犪 狊 狌 狉 犲,犃 犻
3、 狉犉狅 狉 犮 犲犈犪 狉 犾 狔犠犪 狉 狀 犻 狀犵犃犮 犪犱 犲犿狔,犠狌 犺 犪 狀 ,犆犺 犻 狀 犪;犇犲 狆犪 狉 狋犿犲 狀 狋狅 犳犈犪 狉 犾 狔犠犪 狉 狀 犻 狀犵犐 狀 狋 犲 犾 犾 犻 犵 犲 狀 犮 犲,犃 犻 狉犉狅 狉 犮 犲犈犪 狉 犾 狔犠犪 狉 狀 犻 狀犵犃犮 犪犱 犲犿狔,犠狌 犺 犪 狀 ,犆犺 犻 狀 犪)犃犫 狊 狋 狉 犪 犮 狋:,(),犓犲 狔狑狅 狉 犱 狊:;()引言随着复杂网络理论研究的不断发展,其在实际生活中如交通网、电网、通信网、城市绿色设施网络等领域的应用也越来越广泛。对于军事作战体系,也常借助复杂网络这一工具来对体系中的
4、实体进行结构和功能上的刻画,描述实体在现实世界的具体行为,从而为优化指挥控制的结构提供相关参考。军事作战体系包含了情报搜集处理、支援保障、指挥控制、打击毁伤等不同功能的装备,在体系网络中具有不同的重要程度。为了更好地评价作战体系的能力,无论从攻击还是防御的角度来看,挖掘体系网络中的关键节点都具有重要意义:对攻击方而言,知道关键节点可以实现毁伤最大化;而对防御方来说,可以对关键节点进行重点保护。对于网络毁伤问题,在对每个节点的攻击代价相等的前提下,目前常用的方法是根据节点度值、节点介数、接近度、邻居指数 等节点重要性指标进行排序,筛选出排名靠前的关键节点集合然后进行攻击,但是上述指标一方面不能很
5、全面地描述网络拓扑结构的演化,另一第期俞锦涛等:基于拓扑势的网络毁伤最大算法 方面对用上述方法筛选出的关键节点集进行攻击也未必能使毁伤最大化。因为用上述方法进行排序得到的排序靠前的节点组成的集合并不一定是所谓的关键节点集。事实上,网络毁伤最大问题可以类比社会网络中的影响最大问题,参考社区网络中犽个节点的影响最大的定义,研究攻击代价相等时,对有限的犽个节点进行打击,如何使毁伤最大的问题。关于社会网络影响最大的研究不断深入,已从同质网络扩展到了异质网络 ;影响力最大化还是一个()难的数学优化问题,主要的最优化手段或者近似求解算法都有着时间复杂度高、不适合大型网络等问题,为了克服上述缺陷,学者们基于
6、启发式算法、群智能算法 和强化学习方法 等手段进行了一些有益探索。在本文中,首先类比社会网络影响力最大问题给出网络毁伤最大化问题的定义。其次,为了降低算法计算复杂度,便于工程实现,考虑启发和贪心两个阶段,提出新的网络毁伤最大算法。启发阶段用一种合理的节点重要性评价指标筛选出备选种子节点集,由于军事作战体系网络具有实体单元模块化、层次化的特点,节点之间的相互影响具有一定的局域化特征,这种特性可以用有短程场特性的拓扑势 指标描述,而且相对于常用的节点重要性指标更有优势。贪心阶段用()算法 来选择关键节点。实验表明,本文的算法相对于直接通过节点重要性指标排序获取关键节点集的方法有较好的效果,相对于贪
7、心算法有良好的近似并且速度上有显著的提升。网络毁伤最大问题 问题描述假设本文讨论的军事体系网络为无自环简单网络,其数学表示形式为犌(犞,犈),其中,犞狏,狏,狏犖代表节点的集合,犈犲,犲,犲犕代表边的集合。当攻击的资源有限时,只能对网络犌中有限的犽个节点进行打击。在对每个节点攻击代价相等的前提下,毁伤最大化问题描述为攻击网络犌中由犽个节点组成的集合犛,使得网络毁伤的效果最大,即犚(犛)犚(犛)犛犞,犛犽()式中:犚()为目标函数,表示攻击后网络能力损失。目标函数目标函数犚()的选择有多种方式,但是需要满足以下几个性质:()犚();()犚(犃)犚(犅),犃犅犞;()对犃犅犞,狏犞犅,有犚(犃狏)
8、犚(犃)犚(犅狏)犚(犅)。这里采用网络效率 指标,考虑到两个节点之间的距离犱犻 犼越短,传输就越高效,可令节点对之间的效率为犱犻 犼,则整个网络的效率用所有节点对效率平均值表示为犖(犖)狏犻狏犼犞犱犻 犼()式中:犱犻 犼,),节点间相邻时最短距离为,不连通时最远距离为无穷。网络效率的两种极端情形为全连通时的和全是孤立节点的。在网络毁伤最大化问题中,为了具有可比性,认为只删除被攻击节点所连的边,保留原来的节点即将其变为孤立节点,更新后的网络拓扑结构为犌,则目标函数可定义为网络效率下降的百分比,即犚(犛)(犌)(犌)()易证式()满足前文的个性质。近似求解算法因为网络毁伤最大问题能够类比社区网
9、络影响最大问题,所以网络毁伤最大化也是一个难的问题。在网络规模很大时,当前的计算能力很难满足求解最优问题的要求,通常采用贪心算法迭代近似求解来获得关键点集。等 证明了基于单位损失的贪心算法能有很好的近似,能够保证目标函数的值至少可以达到最优值的()。在最优值犛无法求解时,可以用近似算法,但是该算法同样面临大规模网络难以适用的困境,其复杂度约为犗(犽犖(犖犕)。刘凤增等 把节点度值和节点介数相结合作为节点重要性指标,然后在此基础上用犳(犞,犜)函数选出犜个重要节点(其中,犜(犽犻),为参数,犽为打击节点数,犻为迭代数),提出了一种基于重要节点的贪婪算法(,),从而提高计算效率,当犽犖时,算法复杂
10、度约为犗(犽(犽)犖(犖犕)。基于拓扑势的毁伤最大算法受文献 的启发,为了提高算法的计算效率,采用启发和贪心两步:启发阶段利用节点的拓扑势排序获得备选种子节点集,贪心阶段在种子节点集中筛选出使得网络毁伤最大的节点,提出一种获取关键节点集使毁伤最大的算法。拓扑势拓扑势源自场理论,认为网络中节点周围存在一个虚拟场,场内的节点会受到其他节点共同作用。对于军事作战体系网络,节点的作用范围限制在有限的区域,可以用拓扑势来描述;基于类似特性,拓扑势的应用还常见于在骨干网络提取 和染色体结构研究 等方面。对于网络犌,节点集犞中的节点狏犻的拓扑势可用描述短程场并且有优良数学性质的高斯势函数表示为(狏犻)狀狀犼
11、犿犼犱犼 犻()()式中:犱犼 犻表示节点之间的距离,这里采用最短路径来表示;犿犼表示节点的质量,描述节点固有属性;表示影响因子。犿犼在实际网络中含义十分丰富,要结合实际情况具体分析。如果忽略节点之间固有属性的差别,将其视为同质节点,则式()可以化为(狏犻)狀狀犼犱犼 犻()()系统工程与电子技术第 卷在式()中,影响因子控制着节点狏犻的作用范围,对拓扑势的分布具有很大影响,其值通常利用数据场理论中的拓扑势熵 来进行优化,具体为犎()狀犻(狏犻)犣(狏犻)犣()式中:犣犖犻(狏犻)为标准化参量。只要求解单变量函数犎()的最小值即可得到最优的,进而利用拓扑势对节点重要度进行排序。但是有些情况下,
12、若存在距离为无穷大的不连通节点对,则会导致犎()取不到最小值从而;另外在给定后,节点的作用范围会在槡跳后迅速衰减到,考虑到拓扑势是短程场,以及军事作战体系节点之间具有局域限制的相互作用效果,取最优影响因子 (槡),使得节点的作用范围为一阶邻节点和二阶邻节点 。为说明拓扑势的可用性,基于体系作战相关理论 设计了一个简单的军事作战体系想定模型,如图所示,分别对应实体的关系和用 生成的网络结构图。以上级指挥所(犞)为中心,下辖两个战术级指挥所(犞和犞),上级指挥所与战术级指挥所可分别指挥两架作战飞机(犞 和犞),同时还接收来自雷达情报处理节点(犞和犞)的情报信息,两个雷达情报处理节点分别辖个(犞、犞
13、和犞)和个(犞和犞)雷达站,雷达站还可以直接和战术级指挥所进行通信。图军事作战体系模型及对应的网络拓扑图 从实际模型分析,犞、犞、犞、犞以及犞为重要实体集合,用式()计算上述模型的拓扑势,排名依次为犞、犞、犞、犞、犞、犞、犞、犞、犞、犞、犞和犞,符合实际的重要性的排名,因此可以作为启发阶段种子节点筛选的依据,在此基础上进行网络毁伤。犆犈犔犉思想算法 是一种经典的社会网络影响力最大化算法,其在贪心算法的基础上,利用节点影响力存在次模性对原算法进行改进,使得效率提升了近 。对于毁伤最大问题,考虑当前迭代轮次下增益排名前三的节点狏、狏和狏,将节点狏加入关键节点集后,在下一轮选择节点时,若狏在此轮的毁
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 拓扑 网络 毁伤 最大 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。