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

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.