앞 글에서 넘어간 내용을 하나 짚어보겠다. 뿌아송 랜덤연결망에서 고리가 나타날 확률이 1/N (N은 연결망의 크기, 즉 노드 개수)으로 줄어드는 이유에 관해서다. 카러와 뉴만이 2010년 PRE에 낸 논문에 간단한 설명이 나와있는데 이를 소개한다.
우선 아무나 두 노드를 잡았을 때 둘이 연결될 확률 p는 c/N이다. c는 사실 평균 이웃수에 해당하는데 c는 고정시키되 N이 매우 큰 경우를 생각하려는 것이다. 그러다보면 p가 매우 작아지는데 특히 1/N에 비례하여 줄어든다.
뿌아송 랜덤연결망에서 n개의 노드가 m개의 링크로 연결되어 있는 부분연결망(subgraph)이 나타날 때 이 부분연결망 개수의 기대값을 구해보자. 다시 말해서 N개 중 n개 노드를 고르는 경우의 수에 n(n-1)/2개의 가능한 링크 중 실제 m개의 링크만 있을 확률을 곱하면 된다.
개수의 기대값이 N에 따라 어떻게 달라지는지만 관심 있으므로 나머지 상수들은 무시하되 위 식에서 두 요인만 본다.
나머지 요인들은 무시해도 된다. 결과적으로 위에서 말한 부분연결망 개수는 N에 따라 N^{n-m}에 비례하여 커지거나 작아진다. 일단 우리는 n개의 노드가 연결된 경우만 관심을 가지므로, m의 최소값은 n-1이다. 즉 나무(tree)여야 한다. 이때 부분연결망의 개수는 N에 비례하여 커진다. 반면 나무에 링크가 적어도 하나 보태지면 그때부터 고리(loop)가 나타나기 시작한다. 그리고 그러한 부분연결망의 개수는 m=n인 경우 1에 비례하는데, 즉 N이 아무리 커져도 그 개수는 상수로 머무른다. 더구나 링크가 하나씩 많아질수록 그런 부분연결망은 1/N, 1/N^2 등 훨씬 덜 나타난다.
한 마디로, 나무가 N개 나타날 때마다 고리는 1개 꼴로 나타나며 그 비율을 보면 1/N이 된다는 것이다. 끝.
