python - 在二维空间中可视化加权图(权重作为顶点之间的距离)

Question

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

是否有一种算法可以采用此邻接列表并在二维空间中绘制，以使图形与列表一致(即所有图形线的长度均由距离权重规定)？

Answer 1

一般来说，答案是否定的，您不能在精确保留距离的情况下绘制 一般 二维图。

原因是为了能够在不扭曲距离的情况下嵌入图形，距离必须具有非常特殊的属性。例如，他们必须满足 triangle inequality ，除此之外。

要了解这一点，请考虑一个具有 3 个顶点 A、B、C 且距离为 d(A,B)=1 d(B,C)=2 d(A,C)=5 的图。您可以很容易地看出这是行不通的。事实上，无论维度如何，您都无法将其嵌入到任何欧几里德空间中!

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

顺便说一句，直接将 PCA 应用于距离有时称为 Multidimensional Scaling ( Material 数据表)。