2009, Volume 11, Issue 9
Strategic Study of CAE >> 2009, Volume 11, Issue 9
An evaluation method for link importance based on the characteristic of network communication
Information Science and Engineering School, Southeast University, Nanjing 210096, China
Next Previous
Abstract
A method for finding the most vital edge based on the characteristic of network communication is proposed. The link importance is determined by its using frequency in all-pairs shortest paths and the most vital edge results in the highest frequency. Without the commonly used edge-deletion and edge-contraction methods, the proposed algorithm directly reflects the edge's contribution to the network communication and the relative importance of the two edges in the network can be evaluated. The algorithm analyses and the experimental results show that this algorithm overcomes the currently existent problems and provides a more reasonable principle for ranking edges which is consistent with our intuitive judgments.
Keywords
communication networks ; link importance ; shortest paths ; serial links
Figures
图1
图2
图3
References
[ 1 ] Malik K, Mittal A K, Gupta S K.The k most vital arcs in the shortest path problem [ J] .Operations Research Letters, 1990 , 9 ( 4 ) : 283 link1
[ 2 ] Ball M O, Golden B L, Vohra R V.Finding the most vital arcs in a network[ J] .Operations Research Letters, 1989 ,8 ( 2 ) : 73 -76 link1
[ 3 ] Nardelli E, Proietti G, Widmayer P.Finding the detour -critical edge of a shortest path between two nodes [ J] .Information Pro- cessing Letters,1998 ,67 ( 1 ) :51 -54 link1
[ 4 ] Nardelli E, Proietti G, Widmayer P.A faster computation of the most vital edge of a shortest path[ J] .Information Processing Let- ters, 2001 ,79 ( 2 ) : 81 -85 link1
[ 5 ] Page L B, Perry J E.Reliability polynomials and link importance in networks[ J] .IEEE Trans Reliability,1994 ,43 ( 1 ) : 51 -58 link1
[ 6 ] Liang Weifa.Finding the k most vital edges with respect to mini- mum spanning trees for fixed k [ J] .Discrete Applied Mathemat- ics, 2001 ,113 ( 2 ~3 ) : 319 -327 link1
[ 7 ] Liang Weifa, Shen Xiaojun.Finding the k most vital edges in the minimum spanning tree problem [ J] .Parallel Computing, 1997 , ( 23 -13 ) : 1889 -1907 link1
[ 8 ] Tsen F P, Sung T Y, Lin M Y, et al.Finding the most vital edges with respect to the number of spanning trees[ J] .IEEE Trans Re- liability, 1994 ,43 ( 4 ) :600 -602 link1
[ 9 ] Rao V V B.Most -vital edge of a graph with respect to spanning trees[ J] .IEEE Trans Reliability, 1998 ,47 ( 1 ) :6 -7 link1
[10] 陈勇,胡爱群,蔡天佑,等.通信网中链路重要性的评价方法[J].电子学报,2003,31(4):573-575 link1
[11] Traldi L.Commentary on: Reliability polynomials and link im- portance in Networks [ J ] .IEEE Trans Reliability, 2000 , 49 ( 3 ) : 322 link1
[12] Moffat A, Takaoka T.An all pairs shortest path algorithm with expected time o( n2logn) [ J] .SIAM J Comput, 1987 , 16 :1023 -1031
[13] Page L B, Perry J E.A practical implementation of the factoring theorem for network reliability [ J] .IEEE Trans on Reliability, 1988 , 37 ( 3 ) : 259 -267 link1
[14] Ke Weijenn, Wang Shengde.Reliability evaluation for distribu- ted computing networks with imperfect nodes [ J ] .IEEE Trans Reliability, 1997 , 46 ( 3 ) : 342 -349 link1
京公网安备 11010502051620号
