メトリック・スペースでの完全グラフの生成

重み付けがメトリック・スペース（三角不等式に従う）を形成するように、サイズNの完全無作為重み付け無向グラフを生成する最も簡単な方法を助けてください。私はnetworkxライブラリがあることを知っているが、これを行う方法がわからない。メトリック・スペースでの完全グラフの生成

出典

2017-09-21 VladimirLenin

辺の重みのランダム分布のいずれかをさらに指定せず、この問題は簡単です。各エッジごとに2と3の間のランダムウェイトを選択するだけです。得られたグラフは三角不等式を徹底的に満たす。 –

@Paulそうです。不等式は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

おそらく、それはあなたに問題を与えている 'differences = positions [:, None、：] - positions [None、：、：] 'という行です。私がやっていることは「放送」と呼ばれ、非常に便利な機能です。基本的には、（実際にタイル配列を作成することなく） 'None'によって示された次元で配列をタイリングするのと同じです。適切なチュートリアルについては、[docs]（https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html）またはgoogleをご覧ください。 – Paul

メトリック・スペースでの完全グラフの生成

答えて

関連する問題