基于网络熵变率的节点重要性排序方法.pdf

2023 年第 5 期计算机与数字工程收稿日期：2022年11月5日，修回日期：2022年12月13日基金项目：国家自然科学基金项目（编号：62072217，61672269）资助。作者简介：陈前，女，硕士，研究方向：网络安全。王昌达，男，教授，研究方向：网络安全、网络通信、物联网等。1引言几乎所有的复杂系统（比如社会、生物、信息、技术、交通运输系统等）都可以表示为网络1。其中，节点代表系统构成要素，节点连边上的负载信息代表系统要素间的联系。对网络中少数关键节点的破坏就能导致网络整体瘫痪。其中，关键节点是指相对于网络中其他节点而言，能更大程度地影响网络通信或安全功能的特殊节点。因此对网络中关键节点进行保护，能够大幅度提高网络的可用性与抗毁性；对社交网络中的关键节点进行引导，能更好地干预网络舆情的发展。节点的重要性不仅与网络拓扑结构有关，也与当前网络负载状态有关。在不同的网络负载状态下，不同位置的节点会体现出不同的重要性。目前，基于网络拓扑的节点重要性评价方法主要可以分成五类：1）基于邻居节点：这一类方法主要考虑当前节点的临近节点信息。比如度中心性方法（DC）2使用相邻节点的数量作为节点重要性的度量。这种方法实现简单，但忽略了邻居节点自身的影响，因此度中心性方法的准确性不高。2）基于路径长度：这一类方法主要是通过节点在信息传递中所担任的角色来衡量节点重要性，比如接近中心性方法（CC）3通过计算节点与其他节点间的平基于网络熵变率的节点重要性排序方法陈前王昌达（江苏大学计算机科学与通信工程学院镇江212013）摘要在通信网络中，节点的重要性不仅与网络的拓扑结构有关，而且与当前的网络负载状态相关。论文在分析网络负载和网络熵之间变化关系的基础上，首先定义了网络熵变率，然后设计了以网络熵变率为基础的节点重要性排序方法MixR（Mix Ranking）。论文以Abilene 网和GEANT网的公开数据集作为分析对象，以SIR（Susceptible-Infected-Recovered）作为节点重要性评价的参考模型，通过与度中心性、接近中心性、特征向量中心性，以及半局部中心性方法对比，证实了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 communication 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 rate.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 centrality，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 卷均距离来衡量节点重要性。这类方法使用全局信息度量节点的重要性，准确性高但计算复杂度也高。3）基于特征向量：特征向量指标是从网络中节点的地位或声望角度考虑，将单个节点的声望看成是所有其它节点声望的线性组合，从而得到一个线性方程组。该方程组矩阵最大特征值所对应的特征向量就是各个节点的重要性4。特征向量中心性方法（EC）5和PageRank6方法是此类的典型方法。4）基于节点移除和收缩：通过删除节点或者收缩节点对网络产生的破坏性来衡量节点的重要性。比如艾新波提出的熵变量方法7，该方法将节点的重要性定义为某节点删除前后网络熵的变化值，但由于每一次节点删除后都需要计算网络熵，导致了算法计算复杂度也变大。5）混合方法：通过综合前几类方法以达到对节点重要性更全面的分析。此类方法包括文献 8 中通过信息熵加权方法，对节点位置属性和邻居属性进行加权来度量节点重要性；文献 9 中使用一种基于相对熵的综合评价方法。基于当前网络负载变化衡量节点重要性的代表性成果相对较少，其中比较有代表性的成果是我们课题组金甜甜等10提出的 DPCR（Direct Principal Component Ranking）和 CPCR（ComprehensivePrincipal Component Ranking）方法。此类方法可以根据网络的拓扑以及网络中数据包传输的方向性对节点的重要性排序。为了能综合考虑网络负载变化和网络拓扑结构对节点重要性的影响，本文提出一种基于网络熵变率的MixR（Mix Ranking）节点重要性排序算法。为了验证该方法的有效性，本文在两个公开数据集上使用SIR（Susceptible-Infected-Recovered）模型1度量节点的影响力，并将其与其他已知的节点重要性排序方法进行比较，实证了MixR的有效性和准确性。2相关概念本节首先给出流量矩阵的数学模型和基于有向图的网络拓扑的中心性方法；然后介绍了网络熵的几种形式；最后对SIR模型的评判标准和评判过程做简要总结。2.1网络负载的流量矩阵模型在网络流量矩阵OD（Origin-Destination）Matrix中，OD流（k1k2）的定义是从节点k1（源节点）进入，最后流出节点k2（目标节点）的所有流量的集合11。对于一个有着n个节点的网络，它的网络流量矩阵共有n n个元素。一般地，用T来表示流量矩阵，用tij表示OD流（i，j），其中矩阵第i行元素的和代表从节点i流出的总流量，矩阵第j列元素的和就代表着流入节点j的总流量。2.2基于网络拓扑的中心性度量方法度中心性：有向图中度中心性分为出度中心性、入度中心性和度中心性，节点的出度就是指以节点为头的节点数量，入度就是以其为尾的节点数量。节点的度就是节点的出度和入度之和，节点的度中心性值越大，节点能接触的其他节点越多，一般认为这样的节点在网络中越重要。接近中心性：节点的接近中心性值表示为一个节点到其他节点的平均最短距离的倒数，值越大，节点越接近其他节点，越能更好地控制网络中信息流动，一般认为这样的节点越重要。特征向量中心性：该方法的本质是将一个节点的重要性表达成它的邻居节点的重要性之和。节点的特征向量中心性值越大，节点连接的邻居节点越重要，节点本身也就成为一个重要节点。2.3半局部中心性方法节点的半局部中心性方法（semi-local centrality）12是一种基于半局部信息的节点重要性排序方法。该方法首先给出节点的两层邻居度的定义N(w)，其值为节点w两跳范围内邻居节数量和。在有向图中，节点的半局部中心性方法只考虑出度，因此将N(w)定义为从节点w出发两跳范围内可到达的节点数量，其定义为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和 Tsallis熵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）恢复状态。这三种状态节点在所有节点中所占个数分别为S（t），I（t）和R（t）。对于初始受到感染的节点，节点以概率感染其它易受感染的节点。在复杂网络 SIR 模型中，假设被感染的节点周围所有的邻居节点都有机会被感染。经过t时间后，将感染态的节点在整个网络中所占的个数F（t）作为传播范围衡量指标。3MixR动态节点重要性排序方法本节首先给出网络熵变率的定义，并对其原理进行分析，然后在此基础上设计了MixR算法。3.1网络熵变率网络熵可以用来描述网络安全性能，网络熵值越小，说明系统的安全性越好17。对于网络中某一项性能来说，可以将其熵值定义为H=i=1npilog2pi，pi是与这项性能相对应状态出现的概率。若将一个源节点附近聚集的所有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是网络熵差值。在网络中，大部分流量总是聚集在少量节点附近18，这些节点附近的流量变化对节点产生的影响越大，这些节点也被称为关键节点。以网络熵变率为指标，可以在网络中快速、准确地找到这些关键节点。3.2MixR算法为了兼顾网络拓扑结构对节点重要性产生的影响，本文在熵变率的基础上结合了网络拓扑结构信息，即基于节点出度的半局部中心性方法。半局部中心法能够衡量节点四跳范围内的邻居信息，这种方法比度中心性方法的准确度高，比接近中心性方法和特征向量中心性方法复杂度低。将其与网络熵变率的方法相结合，能在准确性和复杂性之间实现一个可接受的折中。最终得到的MixR算法是一个动态方法与静态方法相结合的方法。算法的具体操作过程为：基于不同时刻的网络流量矩阵求得节点的网络熵变率：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 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使用的数据集本文使用两个公开数据集来验证MixR的有效性，其中一个来自Abilene 网络19，另一个来自GEANT网络20，这两个数据集的下载地址是 https：/ 网络和 GEANT 网络的拓扑结构分别见图2和图3。图2Abilene网络的拓扑结构4.2实验方法本文首先使用DC，CC，EC，半局部中心性算法和MixR算法对网络中节点的重要性进行排序，然后使用SIR模型对排序的结果进行验证。具体方法是首先将上述各算法得到的排名前6的节点分别作为网络的初始传染源，然后使用SIR模型进行感染模拟，最后比较传染源节点在网络中感染的节点总数和达到稳态时所用的时间。需要强调的是本文网络熵变率在计算中都是采用的出流量，所以在计算节点的DC值和半局部中心性值时都是采用出度。图3GEANT网络的拓扑结构4.3结果分析实验得到的节点重要性排序序列会随着流量矩阵的更新而改变。为了节约篇幅，只给出排名前六的节点变化序列，表 1给出了 Abilene网络中每隔五分钟的节点重要性序列的变化，表 2 给出了GEANT网络中每隔15min的节点重要性序列的变化。表1Abilene网络的节点重要性变化情况TimeRanking16:00-16:0516:10-16:1516:20-16:2516:30-16:3516:40-16:4516:50-16:5518968272312368436891091241278212252114115965511468表2GEANT网络的节点重要性变化情况TimeRanking8:00-8:158:30-8:459:00-9:159:30-9:45123511132331313171310341113125521796712917结合网络拓扑观察节点的重要性变化，我们可以发现，虽然网络中节点的重要性是在不断变化，网络中仍然还是存在一个节点的重要区域。在Abilene网络中，在下午六点至七点这个时间，重要节点大多数都集中于右边的区域（图 2 加粗区陈前等：基于网络熵变率的节点重要性排序方法10842023 年第 5 期计算机与数字工程域）。在GEANT网络中，在早上八点至九点这段时间，重要节点大多数都集中于中间的区域（图3加粗区域）。表3和表4分别给出了两个网络中各种算法的前六名节点排序结果。我们将这些节点作为 SIR模型中的感染源进行影响力分析，并比较了几种方法的差异性，结果见图4。表3Abilene网络的前六名节点排序结果MethodRankingMixRDCECCCCL14262527445231151167466976537144691012810表4GEANT网络的前六名节点排序结果MethodRankingMixRDCECCCCL1122410122177817173131214217572513161716136101061310.950.90.850.80.750.70.650.60.550.5F（t）051015infection timeMixRCCDCECCL（a）Abilene网络10.90.80.70.60.50.40.30.2F（t）051015infection timeMixRCCDCECCL（b）GEANT网络图4两个网络上的SIR模型实验结果如图4（a）所示，在Abilene网络中，EC方法得到的前6名节点的传播性能最好，其次就是MixR。EC的表现如此好是因为特征向量中心性本身就适合于描述节点的长期影响力，如在疾病传播、谣言扩散中，一个节点的 EC 分值较大说明该节点距离传染源更近的可能性越大4。根据我们的节点排序结果，EC方法得到的排名前6的节点6，4，11，9，1，12在网络中相对分散，而且网络中只有12个节点，这导致剩下的节点每个都能找到与自己距离十分相近的感染源。由此，EC的表现优于我们的方法。但随着网络规模的扩大，在 GEANT 网络中，MixR算法要优于其他4种方法，这说明MixR得出的重要节点在规模较大的网络中处于更为关键的位置。5结语节点的重要性不仅与网络的拓扑结构有关，而且与当前的网络负载状态相关，本文提出了网络熵变率的概念，利用其来研究网络负载变化对节点重要性的影响。同时，我们利用半局部中心性方法来衡量节点附近的拓扑结构。通过两者相结合，得到的MixR算法从网络负载和网络拓扑两方面综合衡量节点重要性，这是一种静态方法和动态方法相结合的方法。方法的有效性最终也在公开数据集上进行实验得到了验证。参 考 文 献1任晓龙，吕琳媛.网络重要节点排序方法综述 J.科学通报，2014，59（13）：1175-1197.REN Xiaolong，LV Linyuan.A review of the ranking methods of important network nodesJ.Science Bulletin，2014，59（13）：1175-1197.2Freeman Linton C.Centrality in social networks conceptual clarification J.North-Holland，1978，1（3）：215-239.3Ulrik Brandes，Stephen P.Borgatti，Linton C.Freeman.Maintaining the duality of closeness and betweenness centrality J.Social Networks，2016，44：153-159.4刘建国，任卓明，郭强，等.复杂网络中节点重要性排序的研究进展 J.物理学报，2013，62（17）：9-18.LIU Jianguo，REN Zhuoming，GUO Qiang，et al.Research progress of node importance ranking in complexnetworks J.Acta Physica Sinica，2013，62（17）：9-18.5Stephenson Karen，Zelen Marvin.Rethinking centrality：Methods and examples J.Social Networks，1989，11（1）：1-37.6Sergey Brin，Lawrence Page.The anatomy of a large-scale（下转第1173页）10852023 年第 5 期计算机与数字工程9叶学义，庄镇泉，张云超.一种快速、新颖的虹膜定位算法 J.计算机工程与应用，2003，30：61-64.YE Xueyi，ZHUANG Zhenquan，ZHANG Yunchao.AFast and New Iris Location AlgorithmJ.Computer Engineering and Application，2003，30：61-64.10杨秀，张轩雄.一种快速有效的虹膜定位方法 J.软件导刊，2019，18（1）：61-64.YANG Xiu，ZHANG Xuanxiong.A Fast and EffectiveIris Location MethodJ.Software Guide，2019，18（1）：61-64.11李锦明，高文刚，张虎威，等.自适应实时边缘检测系统设计 J.电子技术应用，2017，43（2）：85-87，91.LI Jinming，GAO Wengang，ZHANG Huwei，et al.Adaptive Real-time Edge Detection System DesignJ.Application of Electrotechnics，2017，43（2）：85-87，91.12田子林，陈家新.基于最小二乘法与霍夫变换的虹膜定位算法 J.电子技术的应用，2019，45（2）：75-79.TIAN Zilin，CHEN Jiaxin.An algorithm of iris locationbased on least squares and Hough transform J.Application of Electronic Technique，2019，45（2）：75-79.13中国科学院化学研究所.CASIA 虹膜图像数据 EB/OL.http：/，2003.Institute of Chemistry，Chinese Academy of Sciences.CASIA Iris Image DatabaseEB/OL.http：/，2003.14马晓峰，高玮玮.基于Gabor滤波的改进虹膜识别算法J.软件，2019，40（7）：57-61.MA Xiaofeng，GAO Weiwei.Improved Iris RecognitionAlgorithm Based on Gabor FilterJ.Software，2019，40（7）：57-61.hypertextual Web search engine J.Computer Networksand ISDN Systems，1998，30（1）：107-117.7Xinbo Ai.Node Importance Ranking of Complex Networkswith Entropy VariationJ.Entropy，2017，19（7）：303-320.8Zhao Nan，Bao Jingjing，Chen Nan.Ranking InfluentialNodes in Complex Networks with Information EntropyMethod J.Complexity，2020，2020：1-15.9Bin Chen，Zhixue Wang，Chen Luo.Integrated evaluationapproach for node importance of complex networks basedon relative entropyJ.Journal of Systems Engineeringand Electronics，2016，27（06）：1219-1226.10T.Jin and C.Wang.Ranking node influence according todynamic network loadC/IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops（INFOCOM WKSHPS），Paris，France，2019，1-6.11Zhe Wang，Kai Hu，Ke Xu，Baolin Yin，Xiaowen Dong.Structural analysis of network traffic matrix via relaxedprincipal component pursuitJ.Computer Networks，2012，56（7）：2049-2067.12Chen，Duanbing，et al.Identifying influential nodes incomplex networksJPhysica A-statistical Mechanicsand Its Applications，2012，391（4）：1777-1787.13C.E.Shannon.A mathematical theory of communicationJ.Bell Syst.Tech.J，1949，27：379-423.14 A.Renyi，On measures of entropy and information，Proc 4thBerkeley Symposium on Mathematical Statisticsand ProbabilityD.Berkeley：University of CaliforniaPress，1961.15 Constantino Tsallis，RenioS.Mendes，A.R.Plastino.The role of constraints within generalized nonextensivestatisticsJ.Physica A：Statistical Mechanics and itsApplications，1998，261（3）：534-554.16闫光辉，张萌，罗浩，等.融合高阶信息的社交网络重要 节 点 识 别 算 法J.通 信 学 报，2019，40（10）：109-118.YAN Guanghui，ZHANG Meng，LUO Hao，et al.An algorithm for identifying important nodes in social networks fused with high-level informationJ.Journal onCommunications，2019，40（10）：109-118.17张义荣，鲜明，王国玉.一种基于网络熵的计算机网络攻击效果定量评估方法 J.通信学报，2004（11）：158-165.ZHANG Yirong，XIAN Ming，WANG Guoyu.A Quantitative Evaluation Method of Computer Network Attack Effect Based on Network Entropy J.Journal on Communications，2004（11）：158-165.18Andre Broido，Young Hyun，Ruomei Gao，et al.TheirShare：Diversity and Disparity in IP Traffic C/In PassiveandActiveNetworkMeasurementWorkshop（PAM），France，2004：113-125.19 The Internet2 Observatory Data CollectionsEB/OL.http：/www.internet2.edu/network，2011.20The Totem projectEB/OL.http：/totem.info.ucl.ac.be/dataset.html，2007.（上接第1085页）1173