在度量空间中生成一个完整的图

请帮助用最简单的方法生成一个给定大小为N的完全随机加权无向图，以便权重形成度量空间（服从三角不等式）。我知道有networkx库，但不知道如何做到这一点。在度量空间中生成一个完整的图

2017-09-21 VladimirLenin

不边权的随机分布的进一步规范，这个问题很简单 - 只需为每个边选择一个2到3之间的随机权重。得到的图将平凡地满足三角不等式。 –

@保罗当然会的。不等式是d（x，y）+ d（y，z）> = d（x，z）。左手边总是在4和6之间，而右手边在2和3之间。 –

@SvenMarnach我向你鞠躬。（对于那些想知道的问题，我在质疑Sven的洞察力，没有任何争论可以支持。） – Paul

虽然@SvenMarnach是正确的，我以为我会提到它是很容易在networkx从距离矩阵来初始化一个图：

import numpy as np 
import networkx as nx 

V = 100 # number of nodes 
D = 2 # dimensionality 

positions = np.random.rand(V, D) 
differences = positions[:, None, :] - positions[None, :, :] 
distances = np.sqrt(np.sum(differences**2, axis=-1)) # euclidean 

# create a weighted, directed graph in networkx 
graph = nx.from_numpy_matrix(distances, create_using=nx.DiGraph())

来源

2017-09-22 09:51:31 Paul

您可以随机地将图形嵌入任意度量空间。这个例子使用欧几里得平面。同样，我们需要回答的问题是权重的随机分布是否有任何要求。 –

@Paul我已经设法理解/可视化最终如何将随机坐标转换为距离矩阵，但对我来说仍然很困难。你能推荐任何好的阅读吗？ – VladimirLenin

据推测，这就是“差异=职位[:,无，：] - 职位[无，：，]”这是给你麻烦的吗？我所做的就是所谓的“广播”，以及非常方便的numpy阵列功能。本质上，它相当于在由'None'指示的维度中平铺数组（没有实际创建平铺数组）。看看[文档]（https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html）或谷歌一个体面的教程。 – Paul

在度量空间中生成一个完整的图

回答

相关问题