The Link Rank of an Undirected Network

Free registration required

Executive Summary

The authors consider the problem of identifying link metrics in an arbitrary undirected network using measurement nodes and establishing paths/cycles that start and end at these nodes. They assume that the link metrics are unknown constants and combine in an additive manner. They introduce the concept of link rank - the maximum number of linearly independent cycles/paths that may be established between a given set of measurement nodes - and develop a linear time algorithm to compute the link rank. They show that a network with less than three edge connectivity will be rank-deficient and identify the minimum number of links whose metrics need to be known a priori to achieve full link rank.

  • Format: PDF
  • Size: 658.69 KB