랜덤 그래프

정의

쉬운 정의

비결정론적인 절차로 만들어지거나 어떤 확률 분포에 따라 표현되는 그래프를 랜덤 그래프^{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}$ 가 그 이름도 유명한 에르되시-레니 모델이다.