基于网络熵变率的节点重要性排序方法.pdf
《基于网络熵变率的节点重要性排序方法.pdf》由会员分享,可在线阅读,更多相关《基于网络熵变率的节点重要性排序方法.pdf(6页珍藏版)》请在咨信网上搜索。
1、2023 年第 5 期计算机与数字工程收稿日期:2022年11月5日,修回日期:2022年12月13日基金项目:国家自然科学基金项目(编号:62072217,61672269)资助。作者简介:陈前,女,硕士,研究方向:网络安全。王昌达,男,教授,研究方向:网络安全、网络通信、物联网等。1引言几乎所有的复杂系统(比如社会、生物、信息、技术、交通运输系统等)都可以表示为网络1。其中,节点代表系统构成要素,节点连边上的负载信息代表系统要素间的联系。对网络中少数关键节点的破坏就能导致网络整体瘫痪。其中,关键节点是指相对于网络中其他节点而言,能更大程度地影响网络通信或安全功能的特殊节点。因此对网络中关键
2、节点进行保护,能够大幅度提高网络的可用性与抗毁性;对社交网络中的关键节点进行引导,能更好地干预网络舆情的发展。节点的重要性不仅与网络拓扑结构有关,也与当前网络负载状态有关。在不同的网络负载状态下,不同位置的节点会体现出不同的重要性。目前,基于网络拓扑的节点重要性评价方法主要可以分成五类:1)基于邻居节点:这一类方法主要考虑当前节点的临近节点信息。比如度中心性方法(DC)2使用相邻节点的数量作为节点重要性的度量。这种方法实现简单,但忽略了邻居节点自身的影响,因此度中心性方法的准确性不高。2)基于路径长度:这一类方法主要是通过节点在信息传递中所担任的角色来衡量节点重要性,比如接近中心性方法(CC)
3、3通过计算节点与其他节点间的平基于网络熵变率的节点重要性排序方法陈前王昌达(江苏大学计算机科学与通信工程学院镇江212013)摘要在通信网络中,节点的重要性不仅与网络的拓扑结构有关,而且与当前的网络负载状态相关。论文在分析网络负载和网络熵之间变化关系的基础上,首先定义了网络熵变率,然后设计了以网络熵变率为基础的节点重要性排序方法MixR(Mix Ranking)。论文以Abilene 网和GEANT网的公开数据集作为分析对象,以SIR(Susceptible-Infected-Recovered)作为节点重要性评价的参考模型,通过与度中心性、接近中心性、特征向量中心性,以及半局部中心性方法对比
4、,证实了MixR方法的有效性和准确性。关键词网络熵;网络拓扑;节点重要性排序中图分类号TP393DOI:10.3969/j.issn.1672-9722.2023.05.019Node Importance Ranking Method Based on Network the Rate ofEntropy ChangesCHEN QianWANG Changda(School of Computer Science and Communication Engineering,Jiangsu University,Zhenjiang212013)AbstractIn the communica
5、tion network,the importance of nodes is not only related to the topology of the network,but alsorelated to the current network load status.Based on the analysis of the relationship between network load change and network entropy changes,this paper puts forward the concept of network entropy change r
6、ate.On this basis,a further design of the node importance ranking method MixR(Mix Ranking)is proposed.Taking the public data sets of Abilene network and GEANT network as theanalysis object,SIR(Susceptible-Infected-Recovered)is utilized the reference model for evaluation.Comparing to degree centralit
7、y,closeness centrality,eigenvector centrality and semi-local centrality,the results prove the effectiveness and accuracy of MixR.Key Wordsnetwork entropy,network topology,node importance rankingClass NumberTP393总第 403期2023 年第 5期计算机与数字工程Computer&Digital EngineeringVol.51No.51081第 51 卷均距离来衡量节点重要性。这类方法
8、使用全局信息度量节点的重要性,准确性高但计算复杂度也高。3)基于特征向量:特征向量指标是从网络中节点的地位或声望角度考虑,将单个节点的声望看成是所有其它节点声望的线性组合,从而得到一个线性方程组。该方程组矩阵最大特征值所对应的特征向量就是各个节点的重要性4。特征向量中心性方法(EC)5和PageRank6方法是此类的典型方法。4)基于节点移除和收缩:通过删除节点或者收缩节点对网络产生的破坏性来衡量节点的重要性。比如艾新波提出的熵变量方法7,该方法将节点的重要性定义为某节点删除前后网络熵的变化值,但由于每一次节点删除后都需要计算网络熵,导致了算法计算复杂度也变大。5)混合方法:通过综合前几类方法
9、以达到对节点重要性更全面的分析。此类方法包括文献 8 中通过信息熵加权方法,对节点位置属性和邻居属性进行加权来度量节点重要性;文献 9 中使用一种基于相对熵的综合评价方法。基于当前网络负载变化衡量节点重要性的代表性成果相对较少,其中比较有代表性的成果是我们课题组金甜甜等10提出的 DPCR(Direct Principal Component Ranking)和 CPCR(ComprehensivePrincipal Component Ranking)方法。此类方法可以根据网络的拓扑以及网络中数据包传输的方向性对节点的重要性排序。为了能综合考虑网络负载变化和网络拓扑结构对节点重要性的影响,本
10、文提出一种基于网络熵变率的MixR(Mix Ranking)节点重要性排序算法。为了验证该方法的有效性,本文在两个公开数据集上使用SIR(Susceptible-Infected-Recovered)模型1度量节点的影响力,并将其与其他已知的节点重要性排序方法进行比较,实证了MixR的有效性和准确性。2相关概念本节首先给出流量矩阵的数学模型和基于有向图的网络拓扑的中心性方法;然后介绍了网络熵的几种形式;最后对SIR模型的评判标准和评判过程做简要总结。2.1网络负载的流量矩阵模型在网络流量矩阵OD(Origin-Destination)Matrix中,OD流(k1k2)的定义是从节点k1(源节点
11、)进入,最后流出节点k2(目标节点)的所有流量的集合11。对于一个有着n个节点的网络,它的网络流量矩阵共有n n个元素。一般地,用T来表示流量矩阵,用tij表示OD流(i,j),其中矩阵第i行元素的和代表从节点i流出的总流量,矩阵第j列元素的和就代表着流入节点j的总流量。2.2基于网络拓扑的中心性度量方法度中心性:有向图中度中心性分为出度中心性、入度中心性和度中心性,节点的出度就是指以节点为头的节点数量,入度就是以其为尾的节点数量。节点的度就是节点的出度和入度之和,节点的度中心性值越大,节点能接触的其他节点越多,一般认为这样的节点在网络中越重要。接近中心性:节点的接近中心性值表示为一个节点到其
12、他节点的平均最短距离的倒数,值越大,节点越接近其他节点,越能更好地控制网络中信息流动,一般认为这样的节点越重要。特征向量中心性:该方法的本质是将一个节点的重要性表达成它的邻居节点的重要性之和。节点的特征向量中心性值越大,节点连接的邻居节点越重要,节点本身也就成为一个重要节点。2.3半局部中心性方法节点的半局部中心性方法(semi-local centrality)12是一种基于半局部信息的节点重要性排序方法。该方法首先给出节点的两层邻居度的定义N(w),其值为节点w两跳范围内邻居节数量和。在有向图中,节点的半局部中心性方法只考虑出度,因此将N(w)定义为从节点w出发两跳范围内可到达的节点数量,
13、其定义为Q(u)out=wT(u)N(w)out(1)其中T(u)是从节点u出发一跳范围邻居节点的集合,最终给出节点i的半局部中心性CLiout=uT(i)Q(u)(2)bcagdef图1拥有七个节点的有向图以图 2 为例,计算节点a的半局部中心性,Q(a)out=N(b)out,从节点b出发到达节点g,而节点g可以到达的节点有a,c,d,e,f,所以N(b)out=6,依此陈前等:基于网络熵变率的节点重要性排序方法10822023 年第 5 期计算机与数字工程类推,我们有以下结果:CLaout=Q(b)out=N(g)out=6。2.4网络熵网络熵有香农熵13、Rnyi熵14和 Tsalli
14、s熵15等多种不同的形式。在Rnyi熵和Tsallis熵中,参数可以调节不同概率p分布对整体结果产生的影响。当=1时,Rnyi熵和Tsallis熵就退化成香农熵;当1时,由于p值的范围是01之间,p值越小,pa的值越趋近于0,此时高概率事件的分布相比于低概率事件更明显,因此主要体现的是高概率事件的分布状态;当0时,主要体现的是低概率事件的分布状态。2.5SIR模型SIR模型是一种常用的节点影响力评估模型 1,16。在SIR 模型中,节点重要性的评判标准一般有:给定时间内感染源感染的节点总数以及感染总数达到稳态时的用时。在SIR模型中,每一个节点都有3种状态:1)易感染状态;2)已感染状态;3)
15、恢复状态。这三种状态节点在所有节点中所占个数分别为S(t),I(t)和R(t)。对于初始受到感染的节点,节点以概率感染其它易受感染的节点。在复杂网络 SIR 模型中,假设被感染的节点周围所有的邻居节点都有机会被感染。经过t时间后,将感染态的节点在整个网络中所占的个数F(t)作为传播范围衡量指标。3MixR动态节点重要性排序方法本节首先给出网络熵变率的定义,并对其原理进行分析,然后在此基础上设计了MixR算法。3.1网络熵变率网络熵可以用来描述网络安全性能,网络熵值越小,说明系统的安全性越好17。对于网络中某一项性能来说,可以将其熵值定义为H=i=1npilog2pi,pi是与这项性能相对应状态
16、出现的概率。若将一个源节点附近聚集的所有OD流看成是基本状态,则在节点i附近网络熵的定义如下:Hiout=j=1j=ntijj=1j=ntijlog2tijj=1j=ntij(3)文献 17 中利用熵差来反映网络遭受的攻击效果。而在本文中,熵差是网络流量变化导致的网络熵值的变化,所以单靠熵差无法体现网络熵随网络负载变化的快慢。因此本文给出了网络熵变率的概念,即用网络熵值变化的速率来反映网络流量的变化快慢。我们选取不同时刻的网络流量矩阵T1和T2,最终得到节点i附近的网络熵变率为RECi=TH(4)其中T=|j=1j=ntij1-、j=1j=ntij2,即从节点i的出流量变化值;H是网络熵差值。
17、在网络中,大部分流量总是聚集在少量节点附近18,这些节点附近的流量变化对节点产生的影响越大,这些节点也被称为关键节点。以网络熵变率为指标,可以在网络中快速、准确地找到这些关键节点。3.2MixR算法为了兼顾网络拓扑结构对节点重要性产生的影响,本文在熵变率的基础上结合了网络拓扑结构信息,即基于节点出度的半局部中心性方法。半局部中心法能够衡量节点四跳范围内的邻居信息,这种方法比度中心性方法的准确度高,比接近中心性方法和特征向量中心性方法复杂度低。将其与网络熵变率的方法相结合,能在准确性和复杂性之间实现一个可接受的折中。最终得到的MixR算法是一个动态方法与静态方法相结合的方法。算法的具体操作过程为
18、:基于不同时刻的网络流量矩阵求得节点的网络熵变率:REC=r1,r2,r3T,同时基于网络的邻接矩阵求出节点的出度半局部中心性:CLout=c1,c2,cnT,最后将两者相结合得到MixR的公式:MixR=r1r2rn c1c2cn=r1c1r2c2rncn(5)得到的是最终的节点重要性指标,值越大的元素对应的节点越重要。以下是算法的伪代码:输入网络的邻接矩阵A和不同时刻的网络流量矩阵,输出由Ranknode表示,我们通过对Ranknode进行排序来得到最终的节点重要性排序序列。算法:MixR算法输入:Traffic1N*NTraffic2N*NANN输出:Ranknode1)For i=1
19、to N do2)For j=1 to N do3)pj=traffic1 i jsumtraffic1i1083第 51 卷qj=traffic2 i jsumtraffic2i4)H1=j=1NpjlogpjH2=j=1Nqjlogqj5)REC i=|sumTraffic1 i sumTraffic2 i|H1H2|6)End For7)While i|V|do8)Q(u)=wT(u)N(w)9)CL()i=uT(i)Q(u)10)End While11)For i=1 to N do12)Ranknodei=RECiCLi13)End For4实验4.1使用的数据集本文使用两个公开数据
- 配套讲稿:
如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。