ランダム有向ネットワークと次数分布

#ランダム有向ネットワーク
頂点数：ｎ＝1,000,000個
辺数：ｍ＝約5,000,000本
この条件のもとランダム有向ネットワークをpythonで生成してみる。

p=\frac{m}{n(n-1)}=5.000005000005e-06

この確率で辺生成を行う。
これはもし頂点数ｎのネットワークが完全グラフならば辺数lは

l=\frac{n(n-1)}{2}

となる。有向ネットワークより出る辺、入る辺の２本があるので
考えられる最大の辺数は

l=n(n-1)

よって確率ｐは上のようになる。

#ランダム有向ネットワークの生成
pythoｎのnetworkｘを使い、実際に生成してみる。

import networkx as nx

A = nx.fast_gnp_random_graph(n, p, directed=True)

生成したネットワークの辺数、頂点数を調べてみる。

print(nx.number_of_edges(A))
#=>5000971
print(nx.number_of_nodes(A))
#=>1000000

頂点数１００万、辺数約５００万のランダムネットワークができた。
#次数分布

#ポアソン分布
辺を貼るか貼らないかというランダムネットワークは二項分布になっている。
また、p<<1, 1<<nであるのでポアソン分布になっているのでそれを確認する。

ある頂点ｖの次数の期待値は

E[X]=2(n-1)p=2(n-1)\frac{m}{n(n-1)} = \frac{2m}{n}

となる。

$\lambda = \frac{2m}{n}$とすると、ポアソン分布$P_0(\lambda)$は以下になる。

#比較
ポアソン分布と次数分布を比較する。