各ノードの接続数をベースにしたランダムに生成するグラフを生成する

Question

私が持っているデータを介してグラフを生成しようとしています。

このグラフには、各ノードが持っているエッジ数が乱数Nに等しいP(k)ノードを持つ必要があります。ここで、kはノードの "Index"（ほとんど任意）です。

私の質問は、これを行うための実際の方法がありますか？私は密度または別の接続を決定する（n1-> n2-> n3）のどちらかを決定するより多くのデータが必要だと思っていますが、私は完全に確信していません。

Answer 1

本質的にある程度の順序でグラフを生成したい（ランダムになりたいが、これは関連性がありません）。これはグラフ実現問題と呼ばれています。 Havel-Hakimiアルゴリズムは、アルゴリズムが戻ってくる可能であれば、希望の段階を持つ（単純な）グラフ（そのようなシーケンスは Graphic と呼ばれます）。 $ \ mathbb n $ のすべての有限シーケンスは、例えばグラフィックです。 ハンドシェイクLEMMA （それを述べている）グラフ内のすべての程度の合計は、グラフ内のエッジ数の2倍、したがって偶数です。 さらに、一般的には一般的には一意ではありません。次数シーケンス $（2,2,2,2,2,2）$ は、たとえば実現できます。サイクルグラフ $ c_6 $ のサイズ $ 6 $ 、またはdisjoint Union $ c_3 \ mathop {\ dot \ cup} C_3 $ の2サイクルグラフ $ c_3 $ のサイズ $ 3 $ それぞれ。

プログラミング言語のための多くのグラフライブラリは、この問題のためのアルゴリズムの実装、例えばPythonライブラリー networkx 。