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

Question

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

是否有一种算法会采用此邻接列表并在 2D 空间中绘制，以使图形与列表一致（即所有图形线的长度都是距离权重规定的长度）？

Answer 1

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

原因是为了能够在不扭曲距离的情况下嵌入图形，距离必须具有非常特殊的属性。例如，它们必须满足三角不等式等。

要查看这一点，请考虑具有 3 个顶点 A、B、C 且距离 d(A,B)=1 d(B,C)=2 d(A,C)=5 的图。您可以很容易地看到这不起作用。事实上，无论维度如何，您都无法将其嵌入任何欧几里得空间！

您可以执行以下操作：尝试使用诸如PCA之类的算法来降低维数（将图形嵌入到二维空间中） 。PCA 被广泛使用，您可以轻松找到任何您喜欢的编程语言的实现。它会给你一些二维的表示，但不能保证保持距离。但是，如果您的图形恰好具有与 2D 嵌入一致的距离，则 PCA 可以找到它。

顺便说一句，将 PCA 直接应用于距离有时称为多维缩放(MDS)。