  For many important network types (e.g., sensor networks in complex harsh
environments and social networks) physical coordinate systems (e.g.,
Cartesian), and physical distances (e.g., Euclidean), are either difficult to
discern or inapplicable. Accordingly, coordinate systems and characterizations
based on hop-distance measurements, such as Topology Preserving Maps (TPMs) and
Virtual-Coordinate (VC) systems are attractive alternatives to Cartesian
coordinates for many network algorithms. Herein, we present an approach to
recover geometric and topological properties of a network with a small set of
distance measurements. In particular, our approach is a combination of shortest
path (often called geodesic) recovery concepts and low-rank matrix completion,
generalized to the case of hop-distances in graphs. Results for sensor networks
embedded in 2-D and 3-D spaces, as well as a social networks, indicates that
the method can accurately capture the network connectivity with a small set of
measurements. TPM generation can now also be based on various context
appropriate measurements or VC systems, as long as they characterize different
nodes by distances to small sets of random nodes (instead of a set of global
anchors). The proposed method is a significant generalization that allows the
topology to be extracted from a random set of graph shortest paths, making it
applicable in contexts such as social networks where VC generation may not be
possible.
