graph - グラフのエッジの確率を見つける

Question

n = 5000 の頂点と p = 0.004 のエッジ確率を持つランダム グラフ G(n, p) があります。グラフのエッジの予想数はどうなるのだろうかと思いますが、確率論の知識はあまりありません。

誰でも私を助けることができますか？

どうもありがとう！

編集: pE がグラフ内の可能なエッジの数である場合、グラフ内のエッジの予想数を取得するために 0.004 * pE を計算する必要はありませんか?

Answer 1

まず、グラフ内で可能なエッジの最大数を自問してください。これは、すべての頂点が他のすべての頂点に接続されている場合です (nC2 = n * (n-1)/2)。これが自己ループのない無向グラフであると仮定します)。

考えられる各エッジの尤度が 0.004 であり、考えられるエッジの数が n(n-1)/2 である場合、期待されるエッジ数は 0.004*(n(n-1)/2) になります。

Answer 2

予想される頂点の数は、E = p(n(n-1)/2) のように、ノードの数とエッジの確率によって異なります。

任意の i を任意の j に i->j および j->i の両方としてリンクできる場合、グラフで可能なエッジの総数は n(n-1) です。私はあなたの友達です、あなたは私のものです。グラフが無向の場合 (そしてエッジは私たちが友達であることを意味するだけです)、エッジの総数は半分に減少します: n(n-1)/2 i->j と j->i は同じだからです。

可能性のあるすべてのエッジが確率に応じて実数になるかどうかが決まるため、p を掛けると予想されるエッジ数が得られます。p=1 は、考えられるすべてのエッジが実際に発生したため、n(n-1)/2 個のエッジを与えます。p<1 のグラフの場合、選択した p と n を使用して実際にランダム グラフを生成した場合、実際のエッジ数は (明らかに) 時々異なる場合があります。ただし、無限の数のランダム グラフを生成する場合、期待されるエッジ カウントは、最も一般的に観察されるエッジ カウントになります。NetLogo は、ランダムなグラフを生成し、さまざまな構造のランダムなグラフからネットワーク測定値がどのように発生するかを感じたい場合に、非常に教育的なツールです。