랜덤 유향 네트워크

정점수:n＝1,000,000개
변수:m＝약 5,000,000개
이 조건 하에서 랜덤 유향 네트워크를 파이썬으로 생성해 보자.

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

이 확률로 변을 생성한다.
이것은 정점 수 n의 네트워크가 완전 그래프이면 변수 l은

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

된다. 유향 네트워크에서 나오는 변, 들어가는 변의 2 개가 있기 때문에
가능한 최대 변수는

l=n(n-1)

따라서 확률 p는 위와 같습니다.

랜덤 유향 네트워크 생성

파이썬의 networkx를 사용하여 실제로 생성해 보겠습니다.

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

정점수 100만, 변수 약 500만의 랜덤 네트워크가 생겼다.

차수 분포

포아송 분포

변을 붙일지 붙이지 않는가 하는 랜덤 네트워크는 이항 분포로 되어 있다.
또, p<<1, 1<
어느 정점 v의 차수의 기대치는

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

된다.

$\lambda =\frac{2m}{n}$라고 하면, 포아송 분포 $P_0(\lambda)$는 이하가 된다.

비교

포아송 분포와 차수 분포를 비교한다.