在度量空間中生成一個完整的圖

請幫助用最簡單的方法生成一個給定大小爲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

在度量空間中生成一個完整的圖

回答

相關問題