랜덤 그래프

랜덤 그래프

정의

쉬운 정의

비결정론적인 절차로 만들어지거나 어떤 확률 분포에 따라 표현되는 그래프를 랜덤 그래프Random Graph라 한다.

어려운 정의

확률 공간 $( \Omega , \mathcal{F} , P)$ 이 주어져 있고, $2^{\binom{n}{2}}$ 는 버텍스가 $n$ 개인 라벨링 된 그래프를 모두 모은 그래프 패밀리를 나타낸다고 하자.

$\mathcal{F}$-가측인 함수 $\mathbb{G} : \Omega \to 2^{\binom{n}{2}}$ 를 랜덤 그래프Random Graph라 한다. 다시 말해, $\mathbb{G}$ 는 모든 (그래프의) 보렐 셋 $B \in 2^{\binom{n}{2}}$ 에 대해 $\mathbb{G}^{-1} \left( B \right) \in \mathcal{F}$ 를 만족시키는 함수다.

설명

21세기 들어 네트워크 이론이 점점 더 많은 분야에 응용되는만큼 랜덤 네트워크Random Network에 대한 논의 역시 활발해지고 있다. 통계학에서 확률변수가 데이터를 의미하듯, 응용수학에서 랜덤 네트워크는 우리가 원하든 원치않든 지금 손에 떨어져있는 어떤 데이터의 구조를 의미하게 될것이다.

가령 어떤 학과에서 각 학생을 노드, SNS 팔로잉 상태로써 링크로 보고 네트워크를 만들면 그야말로 랜덤 네트워크의 좋은 예가 된다. 노드를 잇는 규칙은 명확하지만 실제로 조사(샘플링)를 하기 전엔 이 네트워크의 형태를 정확히 알 수는 없다. 전형적인 구조는 있겠지만 학과를 바꿔서 조사할 때마다 우연에 따라 다른 네트워크를 얻을 것이다.

다만 이런 설명은 수리적으로 사고하기엔 너무 나이브Naive하다. 어려운 정의에서 랜덤 그래프는 측도론을 사용하는 확률론에서 확률 변수Random Variable를 정의하는 것과 정확히 같은 방식으로 정의됐다. Random Variable란 결국 현실 속의 실험이나 시행 같은 $\omega \in \Omega$ 를 Variable로 매핑 시켜주는 함수고, Random Graph는 Graph로 매핑 시켜주는 함수다.

손으로 직접 적어보면 더 이해하기 쉽다. 특정 그래프 $G_{0}$ 가 있다고 할 때, 랜덤하게 만든 그래프가 $G_{0}$ 일 확률이 $3/4$ 이라면 다음과 같이 적으면 된다. $$ P \left( \mathbb{G} = G_{0} \right) = {{ 3 } \over { 4 }} $$ 위 수식에서의 사건은 $\left\{ \mathbb{G} = G_{0} \right\} \in \mathcal{F}$ 이다. 확률이라는 함수 안에 들어가는 것은 언제나 사건이라는 점을 명심하자. 랜덤 그래프는 일반적인 확률론에서 단지 공역이 그래프 패밀리인 랜덤 엘러먼트Random Element에 불과하다.

예시

예로써 $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$ 개의 링크를 가지는 모든 그래프의 뽑힐 확률이 동등한 것이 된다. 이런 확률 분포를 가지는 랜덤 그래프 $\mathbb{G}_{n, m}$ 가 그 이름도 유명한 에르되시-레니 모델이다.

댓글