📂그래프이론

길버트 모델

정의 ^{1 2}

쉬운 정의

심플 네트워크의 링크가 각각 독립적으로 확률 $p \in [0,1]$ 에 따라 연결되는 랜덤 네트워크를 길버트 모델^{gilbert model} $\mathbb{G}_{n,p}$ 라 한다.

어려운 정의

확률 공간 $( \Omega , \mathcal{F} , P)$ 이 주어져 있고, $n$ 개의 라벨링 된^labeled 노드를 가진 네트워크의 프로퍼티 $2^{\binom{n}{2}} \subseteq 2^{\binom{n}{2}}$ 가 주어져 있다고 하자. 링크의 수 $0 \le m \le \binom{n}{2}$ 에 대해 다음의 확률질량함수를 가지는 $\mathcal{F}$-가측 함수 $\mathbb{G}_{n,p} : \Omega \to 2^{\binom{n}{2}}$ 를 길버트 모델이라 한다. $$P \left( \mathbb{G}_{n,p} = G \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \qquad , \forall G \in \mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$$

설명

길버트 모델은 에르되시-레니 모델 (ER 모델)과 더불어 정말 많은 문헌에서 언급되나 말만 ER 모델이고 실제로는 길버트 모델을 사용하는 경우가 아주, 아주 많다. 두 모델의 차이점이 없는 것은 아니다. 아니 사실 파고들어보면 아예 두꺼운 책 한권이 나올 정도로 다른 모델이지만, 특히 응용 네트워크 이론의 맥락에선 이 둘을 구분하지 않고 ER 모델로 퉁치는 경향이 극심하다. 잘 쓰는 표현은 아니지만, 확률분포가 이항분포이라는 센스에서 이항 랜덤 네트워크^{binomial Random Network}라 부를 수도 있다.

$\mathbb{G}_{n,p}$ 는 대략 $\displaystyle m = \binom{n}{2} p \approx {{ n^{2} p } \over { 2 }}$ 개만큼의 링크를 가지고 있을 것으로 기대된다. ER 모델이 얄짤없이 정확히 $m$ 개의 링크를 가진 것과 달리 길버트 모델은 네트워크의 덩치에 계수 $p$ 로 정비례할 뿐 링크의 수가 정해져 있지는 않다.

정의는 어렵게 적어놨으니 어려워 보이지만 알고리즘을 읽어보면 사실 간단하다. 길버트 모델로 네트워크를 샘플링하는 알고리즘은 다음과 같다.

알고리즘

Input

노드의 수 $n \in \mathbb{N}$ 과 링크 확률 $p \in \left( 0, 1 \right)$ 이 주어져 있다고 하자.

---

Step 1. 초기화

$n$ 개의 노드를 가진 널 그래프 $G$ 를 만든다.

---

Step 2. 베르누이 시행

for $i = 1 , \cdots , n$
　　for $j = 1 , \cdots , n$
　　　　if $i \ne j$
　　　　　　$p$ 의 확률로 다음과 같이 네트워크 $G$ 에 링크 $ij$ 를 추가한다.$$G \gets G + ij$$

---

Output

노드가 $n$ 개고 링크가 $m \approx n^{2} p / 2$ 개 정도 있는 심플 그래프 $G \in 2^{\binom{n}{2}}$ 를 얻는다.

성질

• [1]: 길버트 모델 $\mathbb{G}_{n,p}$ 에서 샘플링한 네트워크의 링크 수가 정확히 $m$ 이어야하면 $\mathbb{G}_{n,m}$ 에서 샘플링한 것과 같다.
• [2] 차수의 분포: $\lambda = np$ 면 $n \to \infty$ 일 때 각 노드의 차수는 푸아송분포 $\displaystyle \text{Poi} \left( np \right)$ 로 분포수렴한다. $$P \left( \deg v = k \right) \to {{ e^{-\lambda} \lambda^{k} } \over { k! }} \qquad , \lambda \approx np$$

증명

[1]

에르되시-레니 모델: 다음과 같은 확률 질량 함수를 가지는 랜덤 그래프를 에르되시-레니 그래프^{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}$$

Claim: 임의의 $G_{0} \in \mathscr{G}_{n,m}$ 를 생각했을 때 다음을 보이면 된다. $$P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) = \binom{\binom{n}{2}}{m}^{-1}$$

---

당연하지만 $\mathbb{G}_{n,p}$ 가 정확히 $G_{0}$ 인 것보다는 $\mathbb{G}_{n,p} \in \mathscr{G}_{n,m}$ 일 가능성, 그러니까 길버트 모델로 샘플링했는데 링크가 다 합쳐서 $m$ 개일 가능성이 더 크다. 이를 사건으로 나타내보면 $$\begin{align*} \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \subset \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} \\ \implies \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \cap \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} = \left\{ \mathbb{G}_{n,p} = G_{0} \right\} \qquad \cdots (\star) \end{align*}$$ 이다. 여기서 각각의 확률을 계산해보면 $\displaystyle P \left( \mathbb{G}_{n,p} = G_{0} \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m}$ 이므로 $$\begin{align*} & P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) \\ =& P \left( \bigcup_{G \in \mathscr{G}_{n,m}} \left\{ \mathbb{G}_{n,p} = G \right\} \right) \\ =& \sum_{G \in \mathscr{G}_{n,m}} P \left( \mathbb{G}_{n,p} = G \right) \\ =& \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \end{align*}$$ 이다. 이제 조건부 확률을 계산해보면 $$\begin{align*} P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \land \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} \\ =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} & \because (\star) \\ =& {{ p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} } \over { \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} }} \\ =& \binom{\binom{n}{2}}{m}^{-1} \end{align*}$$ 을 보일 수 있다. 여기서 $\land$ 는 논리곱이다.

[2]

$n$ 개의 노드를 가지고 각 노드가 연결될 확률 $p$ 가 주어져 있고 노드의 차수는 나머지 $(n-1)$ 개의 다른 노드와 연결되었느냐 연결되지 않느냐에 달려 있으므로, 이항분포 $B(n-1,p)$ 를 따르게 된다. 수식으로 깔끔하게 적어보면 다음과 같다. $$P \left( \deg v = k \right) = \binom{n-1}{k} p^{k} \left( 1 - p \right)^{n-1-k}$$

이항분포의 극한분포로써의 푸아송분포: $X_{n} \sim B(n,p)$이라고 하자.

$\lambda \approx np$ 이면 $$X_{n} \overset{D}{\to} \text{Poi} (\lambda)$$

위 보조정리에 따라 충분히 큰 길버트 네트워크의 노드의 차수는 푸아송 분포를 따른다.

■

시각화

다음은 $n = 50$, $p = 12\%$ 일 때 샘플링한 ER 네트워크와 그 노드의 차수들의 히스토그램이다.

코드

줄리아의 Graphs, GraphRecipes 패키지를 사용한 코드다.

cd(@__DIR__); pwd()

@time using Graphs
@time using Plots
@time using GraphRecipes

n = 50
G_np = erdos_renyi(n, 6/n, seed = 0)
plot_G_np = graphplot(G_np, title = "n = 50, p = 12%", curves=false, size = (300,300), node_weights = degree(G_np).^2,
 node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_np, "plot_G_np.png")
histogram_G_np = histogram(degree(G_np), title = "Histogram of Degree",
 color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_np, "histogram_G_np.png")

일반화

• 청-루 피트니스 모델