通信网中链路重要性的评价方法

本文提出了一种通信网链路重要性的评价方法,该方法可以评价全网范围内的链路重要性.最重要的链路是将其进行边收缩操作后,得到的图的生成树数目最多.通过比较生成树的数目,我们可以判断通信网中任意两条链路的相对重要性.基于生成树数目的边收缩方法反映了某条链路处于正常工作时,对整个通信网的贡献大小.实验结果和理论分析均证明了该方法的有效性和可行性.

Evaluation Method for Link Importance in Communication Networks

An algorithm to determine the most vital edges of a communication network is presented in this paper.Since a spanning tree consisting of non-failed edges must exist in order for a success state to occur in the all-terminal problem,the number of such spanning trees is a measure of reliability.For a given edge e in the graph G,G*e is the graph with the edge contracted,where the edge denotes a link and the vertex denotes a node respectively.The relative importance of the two edges in the graph can be compared by computing the number of spanning trees of G*e for each of the two edges.The most vital edge in G is an edge whose contraction maximizes the number of spanning trees and whose proper functioning contributes most to system reliability.Experimental results and theoretical analysis show that the edge-contraction algorithm is effective and feasible.