에르되시-레니 모델
빌드업
$n$ 개의 라벨링 된labeled 버텍스와 $m$ 개의 에지를 가진 심플 그래프라는 프로퍼티 $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ 를 생각해보자.
정확히 $m$ 개의 링크를 가진 랜덤 그래프는 $\mathbb{G}_{n, m} : \Omega \to \mathscr{G}_{n,m}$ 과 같이 나타낼 수 있다. 이렇게 만들어지는 그래프는 $n$ 개의 노드와 $m$ 개의 링크만 가지면 누가 어떤 확률로 만들어지든 아무래도 상관 없다. 다시 말해, 아직까지는 확률 분포가 주어지지 않았다. 여기서 우리가 가장 쉽게 생각할 수 있는 확률 분포는 다음과 같이 모두가 같은 확률인 일양 분포다.
심플 그래프는 서로 다른 노드를 이어야하므로 $n$ 개의 노드 중 $2$ 개를 골라 $\binom{n}{2}$ 가지의 링크를 가질 수 있으며, 그 중에서 특히 $m$ 개의 링크를 골라서 가지므로 $\displaystyle \left| \mathscr{G}_{n,m} \right| = \binom{\binom{n}{2}}{m}$ 이다. 이에 모든 $G \in \mathscr{G}_{n,m}$ 에 대해 $$ P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} $$ 라고 하면 $n$ 개의 노드와 $m$ 개의 링크를 가지는 모든 그래프의 뽑힐 확률이 동등한 것이 된다.
정의 1 2
확률 공간 $( \Omega , \mathcal{F} , P)$ 이 주어져 있고, 프로퍼티 $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ 를 생각해보자.
다음과 같은 확률 질량 함수를 가지는 랜덤 그래프를 에르되시-레니 그래프erdős–Rényi Graph $\mathbb{G}_{n,m}$ 이라 한다. $$ P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} \qquad , \forall G \in \mathscr{G}_{n,m} $$
설명
에르되시-레니 모델은 랜덤 그래프의 대표격인 네트워크로써 과학계 전반에서 자주 발견되고 쓰이며, 줄여서 ER 모델이라고도 부르기도 한다. 모든 $G \in \mathscr{G}_{n,m}$ 이 뽑힐 확률이 모두 같은 일양분포를 따른다는 센스에서 유니폼 랜덤 네트워크uniform Random Network라 부를 수도 있다.
길버트 모델 $\mathbb{G}_{n,p}$ 는 다른 방식으로 ER 모델 $\mathbb{G}_{n,p}$ 과 유사한 네트워크를 구성한다. 알고리즘적으로나 수리적으로나 두 모델은 다른 모델이지만 두 모델의 차이점에 주목하지 않는다면 사실 두 모델은 거의 똑같다. 안타깝게도 ER 모델이 너무 유명하다보니 그냥 길버트 모델도 ER 모델로 퉁쳐서 이야기하는 경우가 많은데, 저자가 그 차이를 구분하지 못하거나 구분할 필요성을 느끼지 않는 것이니 우리도 너무 집착하지 말도록 하자.
ER 네트워크를 샘플링하는 알고리즘은 다음과 같다.
알고리즘
Input
노드의 수 $n \in \mathbb{N}$ 과 링크의 수 $m \in \mathbb{N}$ 이 주어져 있다고 하자.
Step 1. 초기화
$n$ 개의 노드를 가진 널 그래프 $G$ 를 만들고, 다음과 같은 튜플의 리스트(시퀀스) $\left\{ l_{k} \right\}$ 를 만든다. $$ \left\{ l_{k} \right\} = \left\{ (i,j) \in [n]^{2} : i \ne j \right\} \qquad , [n] = \left\{ 1, \cdots , n \right\} $$ 시퀀스 $\left\{ l_{k} \right\}$ 의 순서를 무작위로 섞는다.
Step 2. 샘플링
for $k = 1 , \cdots , m$
$l_{k} = (i,j)$ 에 대해 다음과 같이 네트워크 $G$ 에 링크 $ij$ 를 추가한다. $$G \gets G + ij$$
Output
노드가 $n$ 개고 링크가 $m$ 개인 심플 그래프 $G \in \mathscr{G}_{n,m}$ 를 얻는다.
시각화
다음은 $n = 50$, $m = 150$ 일 때 샘플링한 ER 네트워크와 그 노드의 차수들의 히스토그램이다.
코드
줄리아의 Graphs, GraphRecipes 패키지를 사용한 코드다.
cd(@__DIR__); pwd()
@time using Graphs
@time using Plots
@time using GraphRecipes
n = 50
G_nm = erdos_renyi(n, 3n, seed = 0)
plot_G_nm = graphplot(G_nm, title = "n = 50, m = 150", curves=false, size = (300,300), node_weights = degree(G_nm).^2,
node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_nm, "plot_G_nm.png")
histogram_G_nm = histogram(degree(G_nm), title = "Histogram of Degree",
color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_nm, "histogram_G_nm.png")