在欧氏空间中嵌入图

Question

我有一个完整的无向图,其中节点表示平面上点上的点,而边是点之间的近似欧氏距离.我想把这个图"嵌入"二维空间.也就是说,我想将每个顶点转换为(x,y)位置元组,以便对于任意两个顶点v和w,边(v,w)具有接近dist(v,w)的权重.

例如,如果我有带有节点A,B,C和D的图形以及带有权重(A,B)的边:20; (A,C):22; (A,D):26; (B,C):30; (B,D):20,(C,D):19,然后你可以分配点A:(0,0); B:(10,0); C:(0,10); D:(10,10).显然这是不完美的,但它是一个合理的近似值.

我不关心获得最好的解决方案,我只想在合理的时间内找到合理的解决方案.

(如果你想要解决这个问题的动机.我有一个物理系统,我对所有点对的距离进行噪声测量.距离测量是嘈杂的,但往往是真实值的两倍.我有进行了所有这些测量,现在有一个包含数千个节点和数百万个边的图,并希望将这些点放在一个平面上.)

Answer 1

您可以根据您的需要调整基于力的图形绘制算法。

G(V,E)该算法尝试通过将每个顶点视为V笛卡尔点并将每个边视为E线性弹簧来为无向图找到良好的布局。此外，全局计算顶点之间的成对排斥力（即库仑定律），这可以防止笛卡尔空间中不相邻的顶点聚集G(V,E)。

在您的情况下，您可以将弹簧的平衡长度设置为等于您的边权重 - 这应该给出一个成对欧几里德顶点距离接近您的边权重的布局。

该算法根据每个顶点的力总和以伪时间步进方式更新初始分布（可能是随机的）。当达到近似稳态时，算法终止。简化的伪代码：

while(not converged)
    for i = vertices in V
        F(i) = sum of spring + repulsive forces on ith vertex
    endfor
    Update vertex positions based on force vector F 
    if (vertex positions not changing much)
        converged = true
    endif
endwhile

有许多优化可以用来降低算法的复杂性。例如，空间索引（例如四叉树）可用于允许有效计算“附近”顶点之间的近似排斥力，而不是缓慢的全局计算。还可以使用多级图聚合技术来提高收敛性和最优性。

最后，请注意，有几个很好的图形绘制库可以实现该算法的优化版本 -例如，您可能需要查看Graphviz 。