第4期 饶育萍等：基于最短路径数的网络抗毁评价方法 ·117·基于最短路径数的网络抗毁评价方法饶育萍，林竞羽，侯德亭（解放军信息工程大学 信息工程学院，河南 郑州 450002）摘 要：由于全连通网络具有最强的抗毁性，且节点间最短路径数对于网络抗毁性有重要意义，通过对计算节点之间的最短路径数，并将待评价网络与全连通网络进行结构差异比较，提出了一种基于最短路径数的网络抗毁评价方法在此基础上建立了网络节点重要性的评价模型，一个节点与网络中其他节点之间的平均等效最短路径数越多，则该节点越重要由于评价模型的关键是最短路径数的计算，因此，还提出了一种基于邻接阵的最短路径数计算方法关键词：拓扑；抗毁性；最短路径；节点重要性中图分类号：TN915.02 文献标识码：A 文章编号：1000-436X(2009)04-0113-05Evaluation method for network invulnerability based on shortest route numberRAO Yu-ping, LIN Jing-yu, HOU De-ting (Information Engineering Institute, Information Engineering University, Zhengzhou 450002, China)Abstract: Fully connecting network has the best invulnerability, and also the shortest route numbers between nodes is important for network invulnerability. Therefore, by calculating shortest route numbers and comparing the topology difference between target network and fully-connecting network, a method based on the shortest route numbers was proposed for evaluating network invulnerability. Further more, a method to evaluate node importance was proposed with it. The more the efficient shortest routes between one node and others, the more important the node was. Also，a method for calculating shortest way numbers between nodes was put forward because it is the key to evaluate model that is to calculate shortest route numbers. Key words: topology; invulnerability; shortest route; node importance1 引言收稿日期：2007-07-02；修回日期：2009-01-09基金项目：国家高技术发展计划（“863”计划）基金资助项目Foundation Item: The National High Technology Research and Development Program of China(863 Program)网络的抗毁性是从图论的概念中提出来的，在通信网的可靠性分析中得到广泛应用，尤其在军事通信网中更是一个非常重要的概念。
抗毁性从网络连通性的角度描述网络拓扑结构对通信网可靠性的影响，它是可靠性的一种确定性测度，实质是研究网络拓扑结构的可靠性，是网络可靠性的一种静态指标对于一个网络，抗毁性是指至少需要破坏几个节点或几条链路才能中断部分节点之间的通信，即指出破坏一个网络的困难程度国内外不少文献就网络拓扑结构抗毁性、节点重要性及其量度进行了论述[1~8]，其中网络拓扑结构抗毁性评价方法有基于割集信息、最小割集或最弱割集的全局性网络拓扑结构抗毁性度量[1]、基于熵的网络拓扑结构抗毁性度量[2]、基于节点抗毁性度量值均方差的评估模型[3]、跳面节点法[4]等，节点重要性评价方法有生成树数目法[5]、网络凝聚度[6]、删除后最短路方法[7]等，这些模型各有其评估侧重点，也各有其局限性另外，基于跳面节点的网络抗毁性评估模型是不够严谨的，该模型认为跳面之间以串行连接，例如在图1中，认为节点1到跳面2的可靠性等于节点1到跳面1的可靠性乘以跳面1到跳面2的可靠性，现假设每个节点的可靠性为1，每条链路的可靠性为p0，按照该模型先计算并联可靠性再计算串联可靠性，节点1到跳面1的可靠性为，跳面1到跳面2的可靠性也为，那么节点1到节点4的可靠性等于，结果显然是错误的，原因在于节点1和4之间的可靠性应该先计算2链路串联可靠性再计算并联可靠性，正确的结果为。
图1 节点1的跳面图2 网络抗毁评价模型全连通网络是结构最紧凑的网络，也是抗毁性最强的网络，并且所有节点具有同等重要性，只是出于建设成本和运行效率等方面的考虑，实际网络极少采用全连通的形式不难理解，一种网络和全连通网络的结构差异越大，结构越疏松，抗毁能力越差那么，是否可以将网络抗毁性评价的着眼点放在实际网络与全连通网络的结构差异上？本文研究发现这是可行的，由此提出了一种基于节点间最短路径数的网络抗毁性评价方法2.1 全连通网络的结构特点对于具有N个节点的全连通网络，任意节点之间可以有1跳，2跳，…，N−1跳的路径，假设跳数为的路有条，易知 (1)那么节点和之间跳数不大于跳的路有条，且 (2)例如图2所示的全连通网络，节点1与节点4之间跳数为2的路有条，节点1与节点4之间跳数不大于2跳的路有条图2 4个节点的全连通网络2.2 非全连通网络与全连通网络的差异对于N节点网络中的节点和，将和之间跳数最少的路径称为最短路径，将最短路径的跳数称为最短路长，记为易知，全连通网络与非全连通网络的一个显著差异就是节点之间路径数的多少，前者任意节点间的路径数总是多于后者如果网络结构庞大，那么节点之间各种跳数的路径就会非常多，甚至难以计算，为了减小计算复杂度，只考虑节点间的最短路径。
一方面，网络节点间进行通信的首选路径是最短路径，只有最短路径不可用的情况下才会选择其他更长的路，在通信网可能遭受攻击和破坏的情况下，如果节点间的最短路径有多条，则在某条最短路径遭到破坏后仍能以其他最短路径进行通信；另一方面，跳数越多的路径其可靠性越差，跳数越少的路径其可靠性越好，因而抗毁性越强，因此网络节点间的最短路径数对于通信网可靠性和抗毁性有着重要的意义可见，从最短路径数的角度考察网络的抗毁性是合理的但是，全连通网络节点之间的最短路径数却未必比非全连通网络多以图3所示的连通图为例，图3(a)是非全连通网络，节点1与节点2之间的最短路长为2，共有3条最短路，图3(b)是全连通网络，节点1与2之间的最短路长为1，只有1条最短路，前者的最短路径数反而比后者多但是图3(b)中节点1与2之间长度不大于2的路径有4条，比图3(a)中节点1与2之间的最短路径数多因此，可以将非全连通网络节点间的最短路径数与全连通网络相应节点间不大于跳的路径数进行比较，该比值总是小于或等于1，并且只有在(节点间有直连边)时该比值才等于1，这样就能准确刻画出2种网络之间的差异，本文将该比值定义为节点之间的“等效最短路径数”。
图3 5个节点的连通图定义1 对于一个N节点的网络，如果节点与节点之间有条长度为的最短路径，则节点与节点之间的等效最短路径数为 (3)其中，是相应N节点全连通网络中节点间不大于跳的路径数显然，，当且仅当2节点之间有直连边时，对于任意的与，若，则为全连通网络 2.3 抗毁性测度函数根据以上分析，提出一种网络抗毁性测度函数 (4)其中，分子是全网的等效最短路径数之和，分母是N节点网络可建立连接的端对数目，该函数实际上表示网络的平均等效最短路径数只有全连通网络任意节点之间的等效最短路径数为1，因而全网平均等效最短路径数Inv=1，抗毁性最强，因其网络结构是最紧凑的，任意非全连通网络的平均等效最短路径数0
同时易知，对于有N个节点的网络，一个节点与网络中其他N−1个节点建立的等效最短路径数越多，反映了该节点与其他N−1个节点的联系越紧密，并表明该节点的核心作用越强，因而该节点在网络中的重要性越大，因此，需要建立节点重要性的评价方法定义2 对于N节点网络，节点的重要性表现为该节点与其他N−1个节点可建立的平均等效最短路径数，记为 (5)2.4 最短路径数的计算节点间最短路长的计算普遍采用较成熟的D算法[9]和F算法[9]，但这些算法适合计算最短路径的长度，没有实现最短路径数的计算本文基于邻接阵的k次幂（Rk），提出一种同时计算网络所有节点间最短路长和最短路径数的方法首先定义矩阵的求非运算定义3 矩阵是矩阵的“非”矩阵，则 (6)引理 对于一个N节点M条边的非赋权无向图G，其邻接阵R为布尔阵，则节点间长度为k的最短路径数矩阵 (7)矩阵中的元素表示节点与之间最短路径（长度为k）的数目，式中符号表示2矩阵内的对应元素相乘而非3矩阵相乘（下同）证明：任意节点间长度为1的路就是它们之间的直连边，因此节点间长度为1的最短路径数矩阵是；当且仅当节点与之间没有t=1,2,…,k−1的链，即=0时，才是与之间长度为的最短路径数。
因为如果存在一个使得，就表明与之间的最短路长为t或者小于t，则与之间长度为的最短路径数因此必有 因此 其中，为对称阵，右斜对角线上的元素没有最短路径数的意义3 举例分析如图4所示，比较2个简单网络G1(6,8)和G2(6,8)的抗毁能力和节点重要性图4 6个节点的图G1和G2(1) 对G1分析 ， ， ，网络抗毁度 节点重要性 (2) 对G2分析 ， ， ，网络抗毁度 节点重要性 从上述可见，网络的抗毁能力强于，因为至少需要断开4条链路才能使分成2部分，而只需断开2条链路就能使分成2部分与中的节点2（或3、4、5）比节点1（或6）更重要，这同生成树数目法的评价结果是一致的4 结束语由于全连通网络具有最强的抗毁性，因此，本文以全连通网络的拓扑结构为基准，将待评价网络与全连通网络进行比较，提出了一种基于最短路径数的网络抗毁评价方法，反映了与全连通网络的拓扑结构差异所导致的网络抗毁性差异在此基础上还建立了网络节点重要性的评价模型文中提出的网络抗毁性和节点重要性评价方法的计算核心是全网各端对间的最短路径数，为此，文中同时给出了一种基于邻接阵k次幂的最短路径数计算方法文中提出的网络抗毁评价方法和节点重要性评价方法主要针对非赋权无向网络，是拓扑层次的抗毁性研究，实际网络的抗毁性涉及诸多因素，下一步可以结合节点之间信息传输带宽、节点业务量等因素综合评价网络抗毁性和节点重要性。
参考文献：[1] LIN W, VARSHNEY P K．On survivability measures for military networks[A]. Proceedings of the IEEE Military Communications Conference[C]. US, IEEE Press, 1990.1120-1124.[2] SCHROEDER M A, NEWPORT K T. Tactical network survivability through connectivity optimization[A]. Proceedings of the IEEE Military Communications Conference[C]. US, IEEE Press, 1987, 590-597.[3] 陈建国, 张永静. 通信网络拓扑抗毁性评估算法研究[J]. 通信系统与网络技术,2006,32(1):6-8.CHEN J G, ZHANG Y J. Study on evaluation algorithm for topology survivability of communication network[J]. Radio Communications Technology, 2006,32(1):6-8.[4] 郭伟. 野战地域通信网可靠性的评价方法[J]. 通信学报, 2000,28(1):3-6.GUO W. Reliability evaluating method of tactical communication network[J]. Journal of Communications, 2000, 28(1):3-6.[5] 陈勇,胡爱群,胡啸. 通信网中节点重要性的评价方法[J]. 通信学报,2004,25(8):129-134.CHEN Y, HU A Q, HU X. Evaluation method for node importance in networks[J]. Journal of Communications, 2004, 25(8): 129-134.[6] 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J]. 系统工程理论与实践,2006,11:79-83.TAN Y J, WU J , DENG H Z. Evaluation method for mode importance based on node contraction in complex networks[J]. Systems Engineering Theory & Practice. 2006,11: 79-83.[7] 李鹏翔, 任玉晴, 席酉民. 网络节点（集）重要性的一种度量指标[J]. 系统工程, 2004, 22(4):13-20.LI P X, REN Y Q, XI Y M. An important measure of actors(set) within a network systems engineering[J].Systems Engineering, 2004, 22(4): 13-20.[8] 赫南, 李德毅, 淦文燕. 复杂网络中重要性节点发掘综述[J]. 计算机科学.2007,34(12): 1-5.HE N, LI D Y. GAN W Y. Mining vital nodes in complex networks[J]. Computer Science. 2007,34(12): 1-5.[9] 周炯磐. 通信网理论基础[M]. 北京: 人民邮电出版社, 1991,94-96.ZHOU J P, Communication Networks Basic[M]. Beijing: Posts & Telecom Press, 1991. 94-96.作者简介：饶育萍（1979-），女，江西上饶人，解放军信息工程大学博士生，主要研究方向为信息网络的HPM打击效应。
林竞羽（1978-），男，浙江定海人，解放军信息工程大学讲师，主要研究方向为信息网络的HPM打击效应侯德亭（1963-），男，河南洛宁人，解放军信息工程大学教授，主要研究方向为信息网络的HPM打击效应。