在2D空间中可视化加权图（带权重作为顶点之间的距离）

Question

我有一个加权邻接表，其中权重是顶点之间的距离。我想通过将每个顶点转换为x，y坐标来想象这一点。

是否有一个算法，将采取这种邻接表和绘图在二维空间，使该图与列表一致（即所有图线是由距离权重规定的长度）？

Answer 1

一般来说，答案是否定的，在精确保留距离的同时，不能在2d中绘制一个常规图。

原因是，为了能够嵌入一个没有距离失真的图形，距离必须有非常特殊的属性。例如，他们必须完成triangle inequality等等。 （A，B）= 1 d（B，C）= 2 d（A，C）= 5，我们可以看到一个包含3个顶点A，B，C和顶点A的距离为d的图。你可以很容易地看到这不起作用。事实上，无论何种维度，您都无法将其嵌入到ANY欧几里德空间中！

您可以做的事情如下：尝试使用像PCA这样的算法来降低维度（将图嵌入到2d空间中）。 PCA被广泛使用，您可以使用任何您喜欢的编程语言轻松找到实现。它会给你一些二维的表示，但不能保证距离。但是，如果您的图恰好具有与2D嵌入相一致的距离，PCA可以找到它。

顺便说一句，将PCA直接应用于距离有时称为Multidimensional Scaling（MDS）。