The Link Rank of an Undirected Network
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.