📂그래프이론

에르되시-레니 모델

빌드업

$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")