@InProceedings{Mao_IMC_2004,
  title = {Modeling Distances in Large-Scale Networks by Matrix Factorization},
  author = {Yun Mao and Lawrence K. Saul},
  booktitle = {Proceedings of {the 2004 ACM SIGCOMM Internet Measurement Conference (IMC-04)}},
  address = "Taormina, Sicily, Italy",
  pages = {278-287},
  year = 2004,
  month = {Oct}
}

Abstract:

In this paper, we propose a model for representing and predicting distances in large-scale networks by matrix factorization. The model is useful for network distance sensitive applications, such as content distribution networks, topology-aware overlays, and server selections. Our approach overcomes several limitations of previous coordinates-based mechanisms, which cannot model asymmetric routing or sub-optimal routing policies. We present two algorithms---singular value decomposition (SVD) and nonnegative matrix factorization (NMF)---that learn scalable models of network distances from limited numbers of measurements. Extensive simulations on real-world data sets show that these models lead to more accurate and robust predictions of latencies in large-scale networks than previous approaches.

Full version in PDF
Matlab code