# Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics

arXiv: https://arxiv.org/abs/1809.03319 · HTML: https://mlsanity.com/paper/1809.03319/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2018.

## Built on by (most cited first, 5 of 5)

- [Recurrent Neural Networks for Dynamical Systems: Applications to Ordinary Differential Equations, Collective Motion, and Hydrological Modeling](https://mlsanity.com/paper/2202.07022/) (2022)
- [Reconstruction of Fragmented Trajectories of Collective Motion using Hadamard Deep Autoencoders](https://mlsanity.com/paper/2110.10428/) (2021)
- [A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency](https://mlsanity.com/paper/2211.09272/) (2022)
- [A Pre-training Oracle for Predicting Distances in Social Networks](https://mlsanity.com/paper/2106.03233/) (2021)
- [Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks](https://mlsanity.com/paper/2312.01342/) (2023)

## Abstract (arXiv)

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.