在2D空间中可视化加权图(权重为顶点之间的距离)

Question

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

有没有一种算法可以获得这个邻接表，并在2D空间中绘制，使图与表一致(即所有图线都是由距离权重规定的长度)？

Answer 1

一般来说，答案是否定的，你不能在精确保持距离的情况下在2d中绘制一般的图。

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

为了理解这一点，考虑一个有3个顶点A，B，C，距离d(A，B)=1 d(B，C)=2 d(A，C)=5的图。你可以很容易地看到这是行不通的。事实上，您不能将其嵌入到任何欧几里得空间中，无论维度是多少！

你可以做的是:尝试使用像PCA这样的算法来降低维度(将图形嵌入到2d空间中)。PCA被广泛使用，您可以很容易地找到您喜欢的任何编程语言的实现。它将在2D中为您提供一些表示，但不保证保持距离。但是，如果您的图形恰好具有与2D嵌入一致的距离，则PCA可以找到它。

顺便说一句，直接对距离应用主成分分析有时被称为Multidimensional Scaling (MDS)。