（信号与信息处理专业论文）网络拓扑结构中节点重要性评价方法的研究.pdf

中文摘要 中文摘要 i n t e m e t 网络可以给人类带来巨大的信息资源，同时为这些信息资源的共享搭 建一个共享平台。网络中的各个设备承担着接受信息、传递信息的职责。为了保 证网络高效的运转，需要及时的处理网络中的故障。重要节点，需要给予更多的 保护和支撑。于是，网络节点重要性分析凸显出它的必要性。 现在大多用基于移除节点、节点收缩等方法来评估节点重要性，根据网络性 能的变化程度来确定网络中各个节点的重要度，但这会损坏网络拓扑结构，引起 其变化。基于改进的拓扑势的节点重要性评估算法，虽然保证网络拓扑结构的全 面性和节点问的相互依赖程度，但在两个固有属性( 节点的度和介数) 数量级相 差较大。针对上述算法的不足，本文提出了在基于改进的拓扑势的节点重要性评 估算法上进行节点加权，即采用熵权法通过分析两个指标的熵值确定出其对网络 的相对重要程度，该算法从拓扑结构的层面上，不仅注重节点之间的依赖程度和 节点对网络资源的控制能力，而且加权方法综合考虑两方面的因素，避免了一方 面的单一性。 研究对复杂网络进行边加权之后的网络节点重要性，结合节点收缩法，在其 基础上对此算法改进，重新定义加权节点重要度，最后利用实验分析验证算法的 可行性和有效的控制了算法的时间复杂度，而且有比较强的现实意义。 同时研究基于通信网络拓扑图的马氏链模型，根据上述模型，提出把其它节 点以最短路径到达该节点概率之和作为节点重要性评判指标，此算法复杂度相对 较低，精度较准，尤其适用于跳数较小的无线通信网络。 关键词：网络拓扑势；节点重要性；节点加权；边加权；马氏链 分类号：t p 3 9 3 a b s t r a c t 一 a bs t r a c t 1 1 1 t e m e ti sa 砌o w o f 也el i 危i ti sag r e a ts o u r c eo f i 面册a t i o l l a j l di t b r i l l g su s al o to fc o n v e l l i e n c e n e t w o r ks e e m sa ni i l f o 皿a t i o nn e t w o r k a n de a c hd e v i c eo r d e d v r e c e i v e sa i l d i r n p a r t si i l = f o m a t i o n i no r d e rt oe n s u r ee m c i e n tn e 铆o r ko p e r a t i o n ，w e n e e dt od e a l 、析t l ln e 铆o r k 筋l u r et i i n e l y i r n p o r t a n tn o d e sn e e dt o b eg i v e nm o r e p r o t e c t i o na n ds u p p o r t n u s ，i ti sv e r yi i i l p o n a n tt 0a i l a l y s i s 恤曲p o r t a i l c eo fn e 咖r k n o d e s t h ee x i s t i n gn o d ei m p o r t a j l c ee v a l u a t i o nm e m o db a u s e do nr e m o v m g n o d eo rn o d e c o n 仃a c t i o n ，c o m p 痂gt h ec h a n g e so fm en e 咖r kp e 墒n i l a n c et od e t e m i n et h e i l p o r 胁c eo fn o d e s ，b u ti t 淅1 i l e a dt oc h a n g eo r 妇n a g et h es 缸u c t i 鹏o f 廿l en 酿o r k t o p o l o g y ae x i s d n gn o d ei i n p o l l j a i l c e e v a l u a t i o n a l g o r i t h mb a s e d o ni m p i 0 v e d t o p 0 1 0 9 i c a lp o t e n t i a lp a y sa t t e n t i o nt ot h er e s o u r c e sc o l l 仃o la b i l ho ft l l en o d ei i lt h e w h 0 1 en e 觚o r k h o 、v e v e r ，t l l ed i 航r e n c eo fm a g n i t u d e b e 呐e e nm e 撕oi n t r i n s i c p r o p e r t i e s ( d e g r e ea i l db e 铆e e i l i l e s s ) i st o os e r i o u s i nv i e wo ft h ea b o v ea l g o r i 廿1 】 i l s ，a n o d ei m p o r t a n c ee v a l u a t i o n a l g o r i t h r n w l l i c h 印p l j e sn o d e 一、i g h t e dm e n l o d si s p r o p o s e d t l l i sa l g o r i 也mi sn o d ei m p o r t a i l c ee s t i m a t i o nm e m o db a s e do ne n 缸o p y m e t l l o d n l ew e i g h t e dm e t h o dc o n s i d e sc o m p r e h e n s i v e l yt w o f a c t o r s ，w h i c hc a na v o i d t h eo n e s i d e d t h en o d e si i n p o r t a n c eo fc o m p l e xn e 研o r k s 晰t l le d g e w e i g h t e di ss t u d i e di nt i l i s d i s s e r t a t i o n i tr e d e f i n e st l l e 、v e i g h t e dn o d e si m p o r t a u l c eb a s e do nn o d ec o n 垃a c t i o n ， w 1 1 i c hh a ss t r o n gp r a c t i c a ls i g i l i f i c a n c e m a r k o vc h a i l lm o d e lb a s e do nc o i l l 【n u i l i c a t i o nn e 铆o r kt 叩o l o g yi ss t u d i e di nt 1 1 i s d i s s e 嘣i o n i i lt h em o d e l ，t h es u mo ft h ep r o b a b i l 时o ft h es h o n e s tp a _ t 1 1 si 1 1w k c h o t l l e rn o d e sr e a c ht 1 1 en o d ei s 恤e v a l 吼t i o ni n d e xo fn o d e i i i l p o r r t a n c e 1 1 1 ea j g o r i t h r ni s r e l a t i v e l yl o wi i lc o m p l e x i 哆a n dm o r ea c c u r a t ew l l i c hi ss u i t a b l ef o rw i r e l e s s c o m m u n i c a t i o nn e “v o r k 腼v w o r d s ：n e 咖r k t o p o l o g y e d g e - w e i g h t e d ；m a r k o vc h a l i n c l a s s n o ：t p 3 9 3 v 1 l 致谢 两年时光弹指间，一幕幕深烙心底。我清楚地明白，这毕业论文完成后，毕 业也就在眼前了。而望着眼前的一切我要感谢太多的人。众位想必都会有感论文 的创作过程实属不易。她凝结了我两年的心血，也承载了我太多的所思所获。至 此非常感谢胡绍海导师、赵帅锋老师、赵瑞珍老师，论文课题选择到资料收集、 论文方向及实验开展与结果分析，一遍遍指出初稿中的问题所在。不断地指路照 明最终定稿形成了自己论文的独立风格。这其中也无不渗透着导师的心血和汗水。 在这过程也领教了导师渊博的知识和严谨的学风、耐心的指正、坚定的立场，这 将使我受益终身，在此表示深深的敬意和衷心的感谢。谢谢您，我的导师! 在实验室工作及撰写论文期间，谢谢孙月影、任伟、曹甜甜、秦周、任晓馨 等同学对我研究工作给予热情的帮助。谢谢同伴们创造了良好的学习研究氛围。 让我在这个枯燥的环境中解去倦怠。两年里我们朝夕相处，一起欢乐，一起苦忧。 让我如此留恋读研时光。谢谢你，知心亲们! 同时，感谢所有任课老师对自己的 指导和帮助。老师们如此和蔼可亲，如此善解人意、如此平易近人而又伟大，由 于你们我才能在各个方面取得显著进步与成长。谢谢你们，可敬老师! 最后，我还要感谢我的家人，一直以来，是他们在我学习和生活中给予我很 大的支持和鼓励，他们的关心永远是我前进的动力。谢谢你们，我引以自豪的家 人! 第一章引言 1 综述 1 1 研究背景 i n t e m e t 网络可以给人类带来巨大的信息资源，同时为这些信息资源的共享搭 建一个共享平台。网络中的各个设备承担着接受信息、传递信息的职责。它以 t c p 妒网络协议将各种处于不同地理位置、范围大小、类型的物理网络整合在一 起；同时它可以利用电信网络将信息资源联接起来，这些信息资源存储在信息总 库，可以实现相关资源的共享，以及通信和信息的交换。网络应用于各个领域， 比如教育、科研、军事、政治、经济、社会和文化等领域。为了保证网络高效的 运转，需要及时的处理网络中的故障。重要节点需要给予更多的保护和支撑。于 是，网络节点重要性分析凸显出它的必要性。 网络为我们带来新奇和便利的同时，它也给我们带来了更加严峻的挑战 网络安全性。随着计算机网络的不断扩大，中间设备的逐渐增多会导致可通路径 也随之增多。增加的中介点和路径可以更加快速的传递信息，这样同时也会造成 一定的信息流失和设备损耗，因此研究网络中的重要节点对增强网络的连通性有 着至关重要的作用。 网络已成为现代社会重要的基础设施，对网络控制权的争夺已成为网络攻守 双方争夺的焦点。我们在研究对网络攻击或者防守时，就需要识别可能构成重大 安全隐患的节点，即要对网络节点的重要性进行排序。这些问题的理论解决途径 可以归结为设计网络中节点重要性的测度方法问题。 1 2 研究意义 网络模型中各个节点在网络中的重要性测度是研究网络可靠性的重要途径。 这些重要节点通常称为集散节点。当集散节点被破坏，整个网络的连通性就有可 能为零。通过采用某种方法衡量网络中节点的重要性，找到网络中的最重要节点， 并对它们进行保护，这样就会提高整个网络的可靠性和安全性。同时，为了提高 信息流通的效率，降低网络信息共享的成本，需要对网络中重要节点的保障和维 护给与更多重视。在网络的各种基础研究工作中，对网络中节点的重要性进行评 估，发掘网络中的重要节点，都具有重要的实用价值。 通过分析网络结构，来评价网络中的节点重要性。在网络化数据挖掘研究中， 其是一个比较困难的问题。同样在互联网搜索和社会网络分析中，也是一个值得 北京交通大学硕士学位论文 研究的方向。那些重要节点对网络的连通性有着至关重要的作用，具有广泛的应 用价值。 1 3 国内外研究现状 现有的网络中节点的重要性判断主要有社会网络分析领域内的节点重要性排 序算法【lj 和系统科学领域内的节点重要性评价方法。 社会网络分析方法基于“重要性等价于显著性”，即根据该节点与其它节点的连 接使其所具有的显著性来判断该节点的重要性，评价指标的研究不会破坏网络的 整体性，而且这种分析方法没有考虑节点集的重要度。这些方法的一个重要思想 是，通过对网络中节点的度、最短路径、节点和与之相连的边的权值等基本属性 的统计和计算，然后定量的刻画节点所发挥的作用程度，进而反映出节点在网络 中的重要性程度。相对比较典型的节点重要性度量属性有节点的度、节点的介数 和中心接近度等。 系统科学分析方法基于“破坏性等价于重要性”，此研究方法是利用网络的连通 性来反映系统某种功能的完整性，通过测量删除某节点后对网络的破坏程度来评 价此节点的重要性，对网络的连通性破坏性越大的节点越重要。用节点( 集) 被 删除后形成的所有不连通节点之间的距离( 最短路径) 的倒数之和来反映节点删 除对网络连通的破坏程度，进而可以反映出所删节点( 集) 的重要性。典型的算 法有p a g e m k 算法【2 】和h i t s 算法。运用系统科学的方法删除节点和边来研究节 点重要性最大的一个不足就是删除节点或边后，会忽略网络本身所具有的诸多有 用的信息。 c o d e v 和s l l a 率先提出了确定网络中最短路径上的最重要节点的问题【3 j 。在他 们的研究基础之上，衍生出很多方法。比较具有代表性的是网络关联法、生成树 数目法、最短路径法和节点收缩法。同时，简单介绍一下基于改进的拓扑势的节 点重要性评价方法。 1 、网络关联法 在卫星通信网络中，由于卫星节点和地面中心节点不能被移除或收缩的固有 特性，因而在对其网络节点进行重要性评估时，必须要能够保证在整个网络上其 拓扑结构的完整性。而在上述几种方法中，无论是移除节点还是节点收缩都将会 导致整个网络拓扑结构的变化，因而以上方法不能应用于卫星通信网络。在这种 情况下，赵毅寰等人提出了适用于卫星网络的网络关联法1 4 j ，同时引出了贡献矩阵 的概念。贡献矩阵以节点的介数和节点的度为研究基础，其中介数为其节点重要 性的初值。在该方法中，同时使用了节点的度和节点的位置，能够获得较为精准 第一章引言 的评测结果。 此方法的优势在于：它是从节点控制网络资源能力的思路出发对节点的重要 性进行分析评价，对网格型或星型卫星网络的节点重要性研究中有着重要的优势。 同时存在一定缺点为：存在比较高的算法时间复杂度。 2 、生成树数目法【5 j 假设图g ( y ，e ) 为无向图且没有自环，g k 表示去掉：爷点m 及其关联链路的 图。在图论中，树表示一种无环连通图，图g 的树是指g 的一个无环连通子图， 而图g 的生成树则是指包含了g 中全部顶点的一个树。这里规定g 中全部节点的 可靠概率相同，但对其具体数值不做要求。 对于有向图g ，4 表示其关联矩阵，4 中的具体元素口。定义如下： fl射条链路与第f 个节点关联，且离开第所、节点 l q ，= 一l 第，条链路与第f 个节点关联，且指向第f 个节点( 1 1 ) l lo第，条链路与第衍节点无关联 在有向图关联矩阵4 中，它的任意的一个挖一1 行子矩阵彳都是图g 的关联矩 阵。 在无向图g 中，图g 对应生成树的数目丁( g ) 为： f ( g ) = d e t ( 州7 ) ( 1 2 ) 在该方法中，节点的重要性与生成树的数目相对应，生成树的数目越少，说 明节点的重要性越强。而对于不同的节点，若它们对应生成树的数目相同，说明 它们在网络中具有同等的重要性。 该方法的优点在于：能够对网络中所有的节点进行重要性评测，能够从网络 的拓扑结构层面上更好地反映出节点的重要性，可以同时对多个节点进行重要性 评测；此外，该方法存在着一定的缺陷，主要在于：要得到无向图在其每条链路 都任意规定方向后的有向图关联矩阵，复杂度较高并且过程繁琐。 3 、最短路径法【6 j 该方法主要是用来从指定的节点对最短路径上选取最重要的节点。以下我们 对该方法在应用中的工作原理进行简单介绍。先指定两个节点v 。，v 。，用( ，屹) 表 示它们之间组成的节点对，之后我们分别移除节点对( ，k ) 在其最短路径上的中 间节点，同时计算出节点移除后( ，) 间的最短距离，其中，能够使得最短距离 最大的中间节点为这两个指定节点v 。，v 。在其最短路径上最重要的节点。如图1 1 所示，移除v 1 前，( ，) 间的最短距离是2 ，移除h 后，( ，k ) 间的最短距离增 加到4 ，此时的最短距离最大，由此判断出( ，) 问最重要的节点是中问节点v 1 。 北京交通大学硕士学位论文 图1 1 最短路径法 f i g u r e l 1t h es h o n e s tp a t hm e t i l o d 与节点收缩法不同，最短距离法没有正而的对节点重要性进行评估，而是从 节点移除后整个网络的受影响程度对待测节点进行评测。该方法一般只用于指定 节点路径上最重要节点的选取，没有办法对整个网络上的节点进行重要性评估。 4 、节点收缩法 对网络中某一节点的重要性评估方法研究中，在引入了聚合度( a g g l o m e r a t e ) 概念的基础上提出了节点收缩法【7 1 。节点收缩法是以某一节点收缩后此网络的聚合 度剐为评价标准，聚合度越大，则说明该网络节点的重要性越高。在网络中，聚合 度一般由以下两项因素决定： ( 1 ) 节点的度：对于网络中的某一节点，其对应的度是指与其相关联的边的 总数目。在同一网络中，不同节点的度也不尽相同，对于其中度值越大的节点， 将其收缩后网络中会有较少的节点数和边数，这说明其相应的网络聚合度越大， 该节点的重要性越强。 ( 2 ) 节点的位置：对于网络中的某一节点，如果其处在很多网络节点对间的 最短路径上，则说明该节点所处的位置很重要，对其进行收缩后能够有效减小网 络的平均最短距离，从而进一步增大网络聚合度。 节点收缩法 9 】是网络中衡量和评估节点重要性的一种行之有效的方法。其优点 主要是：不需要对节点进行移除，在应用上有着较广泛的基础；与此同时，节点 收缩法还存在一定的缺点，主要有：没有办法对对称节点进行评价，对于一般节 点，也不易控制其收缩范围。 5 、基于改进的拓扑势的节点重要性评价方法i l o j 计算出每个节点的拓扑势后，根据其大小进行排序。节点的拓扑势越大，代 表此节点越重要。 基于改进的拓扑势的节点重要性评估算法，不仅重视节点对网络资源的操控 能力，而且更好的体现了网络中各个节点之间的相互依赖关系，在整个网络拓扑 4 第一章引言 结构层面上评估了网络节点的重要性。此算法有很好的划分精度，避免了网络拓 扑结构的变化和分割。但是此算法也存在着一定的问题。如两个固有属性( 度和 介数) 数量级相差交大，可能会导致拓扑势的值片面性从而造成节点重要性计算 有误差。算法得出的节点重要性评估结论，只能作为网络拓扑可靠性和抗毁性的 相对性能指标，方便我们对于计算机网络的节点有更进一步的了解，从而对我们 所关心的重要节点给予必要的支撑和保护，使计算机网络进行更为流畅、安全的 信息交换。 1 4 研究内容和组织结构 本文主要的研究内容分为以下三个部分。 1 、基于节点加权的节点重要性分析 基于改进的拓扑势的节点重要性算法中网络中节点的拓扑势可表示为 疗，d ，、2 缈( v ，) = ( 聊，1 + m ，2 ) e1 了】( 1 3 ) = 1 由于m 。和垅一数量级相差较大，这样会严重影响此算法对节点重要性的全面 判断，不能全面有效地反映出节点的重要性。本文提出对节点的两个固有属性进 行合理的加权，提出了基于熵权法的节点重要性估计方法，从熵入手，通过分析 两个属性指标的熵值，便可确定其对系统评估的相对重要程度，从而确定权重一 即熵权。 本章提出的基于拓扑势的节点加权重要性评估算法，不仅重视节点对网络资 源的操控能力，而且更好的体现了网络中各个节点之间的相互依赖关系，在整个 网络拓扑结构层面上评估了网络节点的重要性。此算法有很好的划分精度，避免 了网络拓扑结构的变化和分割。该方法可以保证网络拓扑结构的完整全面性，而 且算法复杂度低、精度高。 加权方法使得节点的度和节点的介数的数量级不再相差太大，可以将两个指 标相互综合，即综合考虑两方面的因素，从而可以更加全面的评价网络中的各个 节点重要性。 2 、基于边加权的节点重要性分析 在无权网络中，节点之间的连边只代表了它们之间是：否存在关系，因此只能 定性的描述节点间相互作用是否存在，这种定性的表述反映了节点间相互作用的 主要信息。但是在许多情况下，节点本身的强度以及节点之问的关系或相互作用 强度的差异起到了非常重要的作用( 比如不同路径上的带宽不同，会有很大差异) 。 北京交通大学硕士学位论文 此时，仅用一条边来表示连接关系的存在与否不能反映出实际网络的细致结构及 功能，这就需要引入权重的信息来刻画两节点的差异性以及节点之间相互作用强 度的差异性，从而产生了对边加权的加权网络。在加权网络中，节点和节点之间 连接关系的强度的差异性对节点本身的重要性具有不同的影响。 3 、基于马氏链的节点重要性分析 基于通信网络拓扑图的马氏链模型，指出若网络中存在经过奇数次跳转能够 回到自己的节点时，此网络图的马氏链是遍历的，且其极限概率为该节点的度比 上所有节点度之和；然后根据上述模型，提出把其它节点以最短路径到达该节点 概率之和作为节点重要性评判指标；最后进行了实验分析，实验证实了所建模型 的正确性，以及节点重要性评价算法的准确性。此算法采用其它节点以最短路径 到达该节点概率之和作为节点重要性评判指标，更为精确的反映了基于网络拓扑 的节点重要性。尤其适用于跳数较小的无线通信网络：现在的无线通信网络通信 范围一般在两跳范围之内，所以本算法复杂度相对较低，精度较准。 论文共分为六章，具体每章内容安排如下： 第1 章引言，主要介绍论文的研究背景、研究意义。重点介绍国内外的研究现 状和代表性的方法，以及本课题主要的研究内容。 第2 章计算机网络研究基础。用图论的思想对计算机网络进行表达和研究， 这对分析研究计算机网络的可靠性会有很大帮助。本章首先介绍图的相关概述， 以及图的矩阵表示。简单介绍网络中节点的相关概念，以及网络中节点重要性的 提出。并且从节点加权的影响和边权的影响两个方面来介绍加权网络，及其所具 有的优势和现实意义。 第3 章基于节点加权的节点重要性分析。本章提出在基于改进的拓扑势的节点 重要性评价算法上，运用熵权法进行节点加权，两个属性在数量级上相差不再太 大，可以充分利用已有算法的优点，可以很好的体现出节点间的相互作用和相互 依赖，以及真实网络中的模块特性和抱团特性。并且避免已有算法的不足和缺陷。 它反映的是当给定被评价对象集后各种评价指标值确定情况下，各个指标的相对 重要程度，从而可以是分析结果更加全面性，对网络中节点的重要性给出客观有 效的评价。 第4 章基于边加权的节点重要性分析。本章从分析加权复杂网络结构特点入 手，提出了相应的网络模型与符号假设，并给出加权节点重要度的新定义，在此 基础上改进节点收缩方法及其实现算法，有效控制了计算的时间复杂度，最后通 过实验分析验证了方法的有效性和可行性。 第5 章基于马氏链的节点重要性分析。本章首先建立了网络拓扑图的马氏链 模型，并提出了此马氏链的相关性质，然后采用其它节点以晟短路径到达该节点 6 第一章引言 概率之和作为节点重要性评判指标，更为精确的反映了基二f 网络拓扑的节点重要 性。 第6 章结论，主要对研究算法结果进行总结和概括，对现有存在的问题进行 分析。 第二章计算机网络研究基础 2 计算机网络研究基础 2 1 引言 网络( n e t w o r k ) 是一种用于实现信息交换和资源共享的虚拟平台，在一定 地域内，它实现了各个点一面一体之间的信息融合，从而达到了资源共享的 目的。在物理上，它是一类描述自然和工程系统的模型。在数学上，由于其 与图论的研究对象有着天然的相似性，因而，我们通常用图论的思想对其进行 表达和研究，这对分析研究计算机网络的可靠性 i l 】也有很大帮助 在图论中，图( g r a p h ) 是由一个有穷节点集合及其映射组成的数据结构， 而网络则是由若干结点和连接这些结点的链路组成，因此，基于这种相似性， 可以用图论中图的概念来描述网络：图中的节点( n o d e ) 对应表示网络中的基本 功能结点；边( e d g e ) 则对应描述网络中结点间的链路。图论的引入为计算机网 络的发展提供了全新的视角，它的很多研究成果在计算机网络的发展中得到了充 分的应用【1 2 】。 本章首先介绍图的相关概述，以及图的矩阵表示。简单介绍网络中节点的相 关概念，以及网络中节点重要性【l3 j 的提出。并且从节点加权的影响和边权的影响 两个方面来介绍加权网络，及其优势和具有的现实意义。 2 2 图论的理论 2 2 1图概述 定义2 1 ：可以用表示为图g = ( y ( g ) ，e ( g ) ) 的相应边吃的权。图2 1 左侧的是无 权图；右侧的是赋权图 9 北京交通大学硕士学位论文 2 图2 1 无权图和赋权图 f i g u r e 2 1o u 铆e i 曲e df 印h 锄dw e i 曲t e d 铲叩h 定义2 2 ：图g = ( 矿( g ) ，e ( g ) ) 的某一节点相关联的边的条数称为该节点的度( 或次 数) ，记为d ( 1 ，) 或如( v ) 。 下面以图2 2 为例说明度的计算，其结果如表2 1 所示。 图2 2 有向图 f i g u r e 2 2d i r e c t e d 黟印h 表2 1 网络中节点的度 t a b l e 2 1t h ed e 目e eo ft 1 1 en e 帆o r k 其中节点v l 、v 3 为奇点，节点v 2 、v 4 、v ，为偶点。 2 2 2图的矩阵表示 定义2 3 ：设有向图g = ( y ( g ) ，e ( g ) ) ，y ( g ) = v ，v ：，v 。 ， 她：忙竺窖凳至竺边有绦 ( 2 1 ) 令吻2 1o没有v ，到v ，丽边 ( ，2 1 ) 第二章计算机网络研究基础 则称0 盯) 为g 的邻接矩阵( a 由a c e n c ym 撕x ) ，记作彳( g ) ，简记么。 图2 3 有向图 f i g u r e 2 3d c t e dg r a p h 图2 3 所示有向图的邻接矩阵为4 ( g ) = o1 0 0 1l 10 o0 1l 0l 0 0 定义2 4 ：假如无向图g = ( y ( g ) ，e ( g ) ) ，y ( g ) = v 。，v ：，v 。) ， 锕= 骺溺主主 2 ， 则称( ) 为g 的邻接矩阵( a 哇j a c e n c y m a t r i x ) ，记作彳( g ) ，简记彳。 图2 4 无向图 f i g u r e 2 4s i m p l eu n d i r e c t e d 鲫h 图2 4 所示的无向简单图的邻接矩阵为4 = 2 3 网络中节点的相关概念 01110 10 0 0 0 1o 0lo l010 0 0 0 0 0 0 定义2 5 ：距离( d i s t a n c e ) 。两节点v j 和之问的距离吒是这两个节点之间的最短路 北京交通大学硕士学位论文 径1 4 1 。如果节点v ，和v ，不可达，即两节点之间的路径不存在，则吒j 。d 。 定义2 6 ：介数( b e 骶e n n e s s ) 。假如一对节点问存在g 肚条最短路径，其中有g 庸( f ) 条途经节点v ，那么相对这一节点的介数，节点v j 的贡献为g 庸( f ) g 庸。把节点v ，对 网络中全部节点的贡献加起来之后除以节点对的总数，就能得出节点1 ，。的介数e ， 即 鱼盟 b ，= 笔7 祟，七f ， 七 ( 2 3 ) 胛( 力一1 ) 2 。 。、 。 其中，玎是网络中节点总数。 2 4 网络中节点重要性的提出 在网络当中，确定最短路径上的最重要节点具体方法是：第一，定出两节点 ( 1 ，v ，) 问的最短距离。之后去除那些待分析的节点，再一次将两个节点( v ，v ，) 间 的最短距离计算得出。假如1 ，j 移除后，增加了最多的两节点间的最短距离，可以得 出节点( v ，v ，) 之问的最重要的节点是v ，。同时可以看到这一算法的局限性，其不能 评估整个网络中的节点重要性，仅仅得出两节点问的最重要节点。 根据网络中故障的管理的需要，提出节点重要性的研究。对于网络攻防两方， 其研究有着重要意义：将攻击目标锁定为重要节点，进攻方可以取得理想的攻击 效果；在其硬件质量和安全设置等方面，对网络中的重要节点，防御方可以给予 更多重视，网络的抗毁坏i l5 j 性会得到很大的提高。 2 5 加权网络 本节中重点介绍一下加权网路中权重信息对节点重要性的影响分析。现实中 的许多系统都可以抽象成网络，其中每个个体对应网络中的节点，个体之间的关 系或者相互作用对应于连接节点的边。在无权网络中，节点之间的连边只代表了 它们之间是否存在关系，因此只能定性的描述节点间相互作用是否存在，这种定 性的表述反映了节点间相互作用的主要信息。但是在许多情况下，节点本身的强 度以及节点之间的关系或相互作用强度的差异起到了非常重要的作用。如在科研 合作网络中作者之间的合作次数是影响整个网络的重要因素。此时，仅用一条边 表示连接关系的存在与否不能反映出实际网络的细致结构及功能，这就需要引入 权重的信息、来刻两节点的差异性以及节点之间相互作用强度的差异性，从而产 生了加权网络。在加权网络中，节点和节点之间连接关系的强度的差异性对节点 第二章计算机网络研究基础 本身的重要性具有不同的影响。 2 5 1节点权重的影响 因网络中的各个节点拥有的邻居节点数目不同，导致节点在网络的影响力也 有所不同。一般情况下，引用节点的度值来描述节点在网络中的影响力，度值越 大的节点表示与之相连的边数越多，该节点对网络的影响力也越大。实际网络中， 度值相同的节点可能会出现具有不同权重【l6 】的情况，那么度相同的节点对网络的 影响力仍然会有所不同。如果只考虑用节点的度值来描述节点的权重，与节点相 连的邻居节点的连接关系和强度就容易被忽略。因此，在定义节点权重时，应该 对节点的度值信息进行拓展，从而更加全面而准确地反映出节点的影响力。 选取科研合作网络【l7 l 为例进行一下简单的分析，即利用节点权重来描述各个 节点在科研合作网络中的影响。在科研机构中，一个科研人员的合作者数量以及 与合作者之间的合作强度都会影响该科研人员的科研绩效。如果一个科研人员具 有很多的合作者，且与部分合作者之间的合作强度也较大，那么该科研人员的影 响力就会较大。同时考虑科研人员自身不同学术地位的影响，地位更高的人往往 会吸引更多的科研人员或者新加入的科研人员与之进行合作，从而进一步提升他 的影响力。通过考虑以上因素，节点权重可以比较真实的反应出节点在网络中的 影响力，即节点的重要程度。 2 5 2 边权的影响 把一个实际网络构建成一个加权网络，并不是一个简单的过程。其中边权所 代表的实际意义是需要首先考虑的，在此基础上才能更准确地对边进行赋权。 边权代表个体之间相互作用的强度，即连接关系的强度，它既可以是现实存 在的物理权重，也可以是抽象的权重，当实际问题中存在着物理权重时，如电力 网络中的电流量、航空网络中的里程、i n t e m e t 网络的带宽等，可以直接把相关物 理量看成是网络的边权。当处理社会关系网络中的亲密程度、相似性等问题时， 需要把节点之间的某种属性转化为边权，或者根据节点之间连接关系所代表的现 实含义进行转化，而且边权值的大小会直接反映出与之相连节点的影响力。通过 这种赋权方式得到的边权大小，可以表示节点和边在某种意义上的重要性程度。 仍以科研合作网络为例来分析。在科研合作网络中，边由节点对应的作者间 合作关系生成，合作次数的多少就代表了边权值的大小，合作次数越多，边权值 越大，说明这两个节点之问的关系越紧密，在一定程度上会促进科研合作，从而 北京交通大学硕士学位论文 提高科研绩效。同时科研人员之间的每一次合作就代表了一篇合著论文的产出， 产出的论文质量越高，他们之间的合作效率也就越高，在消耗同样时间和精力的 情况下，合作效率高的科研人员会产出更多、更好质量的论文，他们的学术水平 也会随之升高，也就越具有影响力。对这类科研人员的识别和评价重点研究，可 以更好的体现边权值对节点重要性的影响。 2 6 本章小结 本章介绍了图论的理论基础。图论中的一个研究范围就是计算机网络，同时 图论学科的向前发展也要依靠快速发展的计算机网络，两者之间有着密切的关系。 计算机研究中的理论知识就是图论中相对基础知识，图论矩阵是有效的工具和研 究方法。最后介绍加权网络，提出了加权网络中的权重信息，从节点权重的影响 和边权的影响两个方面来分析。 1 4 第三章基于节点加权的节点重要性分析 3 基于节点加权的节点重要性分析 3 1 引言 本文提出在基于改进的拓扑势的节点重要性评价算法上运用熵权法的节点重 要性估计方法，从熵入手，通过分析两个属性( 节点的度和节点的介数) 指标的 熵值，便可确定其对系统评估的相对重要程度，从而确定权重一即熵权。对其中 的两个固有属性，采用熵权法对其进行节点加权，目的是在保证网络拓扑结构完 整性的前提下，关注节点之间的相互作用和节点对整个网络资源的控制能力，熵 权并非反映指标在实际意义上的重要性，而是在评估中的相对重要性，它反映的 是当给定被评价对象集后各种评价指标值确定情况下，各个指标的相对重要程度， 从而可以使分析结果更加全面性，对网络中节点的重要性给出更加客观有效的评 价。 3 2 基于改进的拓扑势的节点重要性评价算法 3 2 1拓扑势的引入 随着英国科学家迈克尔法拉第开创的电磁学，引入并证明了电磁场的存在， 革命性地推翻了牛顿力学中“超距作用”这一概念。随着研究的深入，他又在力 场方面取得了突破，推动了人类的进步。在物理学中，势场【l8 】有着及其特殊的地 位，即通过对微分算子v 的引入，完美的将对应的描述场标量势函数和空间矢量 强度函数联结在一起。除此之外，在势场理论中，还引入了势值的概念，对于空 间上的任意一点，其势值与点到场源的距离成一定的递减关系，同时还与其相对 应的场源强度参量成正比。在静电势场和重力势场中，势值大小与点源间距成反 比，如果在点到场源的距离较远的情况下依旧存在场力，则该场为长程场。而在 核子中心势场中，势值大小会随着点与场源间距离的增大而快速衰减。 基于上述物理场的描述，即可以把网络g 当作是一个包含，z 个节点及其关联的 物理场系统，其中，每个节点代表一个场源，关联表示节点场源的作用范围。结 合实际网络的模块特性和抱团的特点，可以认为场中的每个节点都可能与其它节 点相互作用，但这种相互作用是有局限性的，随着节点间距离的增大，其相互影 响能力将急剧减小。根据数据场i l9 。，我们一般采用高斯势函数描述节点间的相互 北京交通大学硕士学位论文 作用，该函数代表短程场并且具有很好的数学特性，将其相应的场定义为拓扑势 场【2 0 1 。 3 2 2网络节点拓扑势的定义 基于上一节的思想，首先我们假定一个网络g = ( y ，e ) ，然后将g 看作一个物 理系统，该系统包含有刀个节点及节点问的相互作用。在该系统中，每个节点代表 一个场源在其周围存在着一个空间上的虚拟场，场中的每个节点都将与其他节点 相互作用，这样就在网络的拓扑结构上形成了一个场，定义为拓扑势场。由数据 场中势函数的定义可知，对于场中任意的节点”y ，其拓扑势【2 1 】为： n，d f f 、2 缈( v ，) = ( ，z _ ，p 弋了) ( 3 1 ) ，= l 在上述公式中，d ，表示网络中节点问的距离；盯为影响因子，主要用于控制 节点的作用范围；朋，0 表示节点v ，( = 1 ，2 ，刀) 的质量，用于描述网络节点固有 的属性。 3 2 3基于改进的拓扑势的节点重要性评价方法 l 、改进的拓扑势公式的提出 在上一节中，我们了解到网络中某一节点的拓扑势是其在自身和邻近节点的 共同作用下产生的，运用该拓扑势方法能够对节点的重要性进行很好地评价，但 是，由于网络中的节点固有属性具有多样性和选取不确定性，容易导致评价结果 不能够在整个网络的拓扑结构上准确地反映节点重要性。所以，这里对拓扑势算 法提出了改进方案，改进后的节点拓扑势可以表示为： 在上述拓扑势公式中，坍。和m ，分别表示节点v ，( ，= l ，2 ，胛) 的质量；仃为影 响因子，和改进前作用相同，用于控制节点的作用范围。 2 、固有属性的确定 ( 1 ) 节点的度：对于网络中的某个单一节点，“度”反映的是其简单而又最 重要的特性。一般来说，“度 这一属性是指与某一节点相关联的边的总数目，主 要用来表示该节点与其邻近节点之间的内在联系程度，即不同节点间的重要性依 赖关系。因而，对于网络中的某一节点，我们可以认为其重要性在一定程度上与 p 、 m+m - 开一 = 矿 缈 第三章基于节点加权的节点重要性分析 “度”这一属性有着内在的必然联系，度的值越大表示该节点相比其它的节点越 重要。在这里，“重要”是相对的而非绝对的，因为对于同一网络而言，不同节点 考虑的侧重点可能不同，即对于节点重要性的评判标准不同。基于上述理论，本 论文选取节点的度作为一个固有属性，目的是为了能够从网络中各节点的相互依 赖关系中更好的分析节点重要性。 ( 2 ) 节点的介数：对于网络中的一个待测节点而言，其对应的“介数”是指 该待测节点所对应的全部节点对的累加贡献除以全部的节点对个数。“介数”一般 用来反映待测节点在网络通信中提供可用最短路由的能力，同时也用于表示该节 点对于网络资源控制能力的衡量。基于上述理论，本论文选取节点的介数作为另 一个固有属性，目的是为了能够从顾全整个网络的全局性上对节点的重要性进行 分析。 3 、影响因子【2 2 】的确定 在网络中，各个节点的势熵对影响因子的确定有着关键性作用。各个节点能 够影响的范围关联着拓扑势值的精准性。介绍势熵如下： 给定网络g = ( y ，e ) ，同时在某个确定影响因子下拓扑势场，令v l ，的势值 为缈( h ) ，矽( ) ，其定义是： h ：一窆掣l o g ( 掣) ( 3 3 ) 扛l 厶厶 其中，z = 缈( _ ) 是标准化因子。 势熵的值可豉体现出拓扑势结构不稳定性的大小。 矿仃= 0 时，缈( 歹jf ) j o ，伊( f ) = 他= m ，势熵j 日一= l g ； 矿仃j0 0 时，妒( ，专f ) j 聊i ，即任意两节点之间的影响没有差异，缈( f ) = 埘， 经过z 归一化后，势熵专心。= 1 9 。 结合上面内容得出影响因子势熵关系曲线图如图3 1 所示。 从图3 1 得出，仃的单调递增会导致势熵的变化为：由极大值风。= l g 递减 后再增大到风。= l g 。势熵的选取会影响网络中节点的拓扑势分布的不均匀性 和不确定性，当势熵取值最小时，此时为最优影响因子。研究仃的最优问题，我 们可以去研究相对单一的变量，即非线性势熵日( 盯) 的最小化问题。 1 7 北京交通大学硕士学位论文 1 6 0 9 5 1 6 0 9 1 6 0 8 5 1 6 0 8 仝1 7 5 壤 霖1 6 0 7 1 6 0 6 5 1 6 0 6 1 6 0 5 5 1 6 0 5 基于势熵的影响因子优选 0123456 7891 0 影响因子( s i g m a ) 图3 1 基于势熵的影响因子优选 f i g u r e 3 1 i m p a c t t o ro p t i m i 劢i o nb a l s e do np o t e n t i a le n 打o p y 4 、基于改进的拓扑势的重要节点评价算法可用如下算法流程图3 2 展示： 图3 2 算法流程图 f i g u r e 3 2a l g o r i t h mf l o wc h a n 1 8 第三章基于节点加权的节点重要性分析 3 3 基于熵权法的节点重要性评价算法 3 3 1熵权的引入 虽然3 2 中的基于改进的拓扑势的节点重要性评价算法已经改进了以前算法中 很多不足之处和缺陷，具备了很多优点( 从表3 4 评估结果中，相比于基于网络关 联性算法、基于生成树算法，可以看出基于拓扑势算法的优势) ，例如上述提出的 算法不涉及复杂的矩阵计算；节点移除带来的负面影响可以避免；从网络拓扑结 构全局来分析节点的重要性：可以很好的体现出节点间的相互作用和相互依赖， 真实网络中的模块特性和抱团特性；但不足之处在于，计算所得的两个固有属性 ( 节点的度和节点的介数) 在数量级上相差较大( 从表3 1 中的各个节点的m 。和 m i ，可以看出) ，这样会导致判断节点重要性的算法有一点的片面性，不能全面客 观的分析节点的重要性。 由于基于改进的拓扑势的节点重要性评价算法可能在某些方面不能全面、有 效地反映出节点的重要性。因而本文提出了基于熵权法的节点重要性估计方法， 从熵入手，通过分析各类指标的熵值，便可确定其对系统评估的相对重要程度， 从而确定权重一即熵权，进而对系统做出客观评价。 3 3 2熵权的计算 在系统评估中，人们常常需要根据指标的重要程度，确定其权重系统。就目 前( 层次分析法、模糊评价法等) 来看，在确定各个指标的重要程度时，不仅中间 过程繁琐、计算量大，而且都会有一些主观因素在其中。按照信息熵思想，在评 估可靠性和精度时，从系统中获得的信息的多少是决定因素。可以从熵入手，由 各类指标的熵值来决定各个指标在系统