뿌아송 랜덤연결망의 거대요소 구하기

요즘 하고 있는 일과 관련된 공부를 하다가 오랜만에 블로그에 글을 남긴다. 뿌아송 랜덤연결망에서 거대요소(giant component)의 크기를 구하는 문제를 풀어볼까 한다. 뉴만(M.E.J. Newman)의 SIAM Review 논문을 참고했다.

n개의 노드가 있는 연결망이 있다고 하자. 가능한 링크의 총 개수는 M=n(n-1)/2이 된다. 각 '가능한 링크'는 p의 확률로 실제 링크가 되거나 1-p의 확률로 링크가 만들어지지 않는다. 그럼 각 노드의 평균 이웃수는 z=p(n-1)이 된다. 각 노드는 n-1개의 나머지 노드 각각과 연결될 수도 아닐 수도 있는데 연결될 확률이 p이기 때문이다. 이로부터 이웃수 분포(degree distribution)는 다음처럼 주어진다.

$$p_k={n\choose k}p^k(1-p)^{n-k}\simeq \frac{z^k e^{-z}}{k!}$$

첫번째 식부터 보면, n이 아니라 n-1이어야 할 것 같은데... 여튼 n-1개의 '가능한 이웃' 중 k개를 고르는 경우의 수에 그렇게 선택된 k개의 이웃과 연결될 확률을 곱하고 나머지 '가능한 이웃'들과는 연결되지 않을 확률을 곱한 것이다. 이 식을 k를 고정시키고 n을 무한히 크다고 가정하면 두번째 식이 나온다. 간단히 풀어보자.

$${n\choose k}=\frac{n!}{k!(n-k)!}\approx \frac{n^k}{k!}$$

$$(1-p)^{n-k}\approx (1-p)^n \approx e^{-pn}$$

바로 위 식의 두번째 어림에서 p가 매우 작다는 가정을 썼다. z=pn이고 z는 고정, n은 매우 크기 때문이다. n이 무한히 크다고 하면 위의 '근사/어림'을 뜻하는 기호는 등호로 바뀐다. 결과적으로 얻은 이웃수 분포가 뿌아송 분포여서 뿌아송 랜덤연결망이라고 부른다.

이제 거대요소를 구해보자. 노드 하나를 랜덤하게 골랐을 때 이 노드가 거대요소의 일부가 아닐 확률을 u라고 하자. 이 노드가 거대요소에 포함되지 않았다면 이 노드의 이웃들도 거대요소에 포함되지 않아야 한다. 이 노드가 k개의 이웃을 가지고 있을 때, 이웃들이 모두 거대요소에 포함되지 않을 확률은 u^k이며 이걸 가능한 모든 k에 대해 기대값을 구하면 그게 바로 u가 되어야 한다.

$$u=\sum_{k=0}^\infty p_ku^k=e^{-z}\sum_{k=0}^\infty \frac{(zu)^k}{k!}=e^{z(u-1)}$$

거대요소의 크기, 즉 거대요소에 포함된 노드 개수를 n으로 나눠준 값을 S라고 한다면 S=1-u다. 위 식은 다음처럼 씌어진다.

$$S=1-e^{-zS}$$

이 식을 풀면 당연히 S는 z의 함수이며, z가 1보다 작으면 S=0이고 z가 1보다 크면 S가 0보다 큰 값을 해로 갖는다. 그래서 z=1을 임계점이라 부를 수도 있다. 하지만 사실 이건 스미기(percolation) 문제라서 스미기 전이라고 부르는 게 좀더 정확하다고 생각한다.

z=1은 무엇을 뜻하는가. z는 평균 이웃수이므로, 평균 이웃수가 1일 때 거대요소가 생긴다는 말이다. 즉 각 노드가 평균적으로 1개의 이웃을 가질 때라는 말인데... 더도 말고 덜도 말고 1개의 이웃이라는 말이다. 모르겠다;;;