뿌아송 랜덤연결망은 이웃수 분포가 뿌아송 분포인 경우를 뜻하는데, 이웃수 분포가 뿌아송 분포가 아닌 임의의 분포에 적용할 수 있도록 일반화할 수 있다. 그중에서도 짜임새모형(configuration model)을 소개한다. 역시 뉴만의 SIAM Review 논문을 참고(라고 쓰고 요약이라 읽는다)했다.
각 노드의 이웃수를 나열한 이웃수 열(degree sequence)을 생각하자. 즉 1번 노드 이웃은 3개, 2번 노드 이웃은 11개... 같은 식이다. 그런데 아직 실제 링크는 없고 이 이웃수들은 각 노드에 달려 있는 '빈 손'의 개수라고 보면 된다. 이 노드들을 두 개씩 랜덤하게 골라서 두 노드 모두 빈 손이 남아 있으면 연결하는데, 그러면 각 노드의 빈 손의 개수는 하나씩 줄어든다. 이 과정을 모든 노드의 빈 손이 모두 사라질 때까지 반복하면 이웃수 분포 p_k를 제외하고 완전히 랜덤한 연결망이 얻어진다. (물론 이웃수의 합은 짝수여야 한다는 조건이 붙는다.)
이웃수 분포 p_k는 노드 하나를 랜덤하게 골랐을 때 그 노드의 이웃수가 k일 확률이다. 그렇다면 노드가 아니라 링크 하나를 랜덤하게 골랐을 때 그 링크를 따라 도착한 노드(링크의 양끝 노드 중 하나)의 이웃수가 k+1일 확률은 얼마일까? 여기서 k+1이라고 쓴 건 우리가 고른 바로 그 링크를 제외하고 나머지 링크수가 k개일 확률을 구하고 싶기 때문이다. 이 k를 '여분 이웃수(excess degree)'라고 부른다.
이웃수가 k+1인 노드는 말 그대로 k+1개의 링크를 갖는다. 즉 연결망에서 링크를 랜덤하게 고를 때 이 노드가 선택될 가능성은 k+1배만큼 높아진다(이웃수가 1인 노드에 비해서). 그래서 여분 이웃수 분포는 다음과 같다.
z는 평균 이웃수인데 이는 q_k를 정규화하기 위해 필요하다. 즉 q_k도 확률이며 모든 k에 대해 더하면 1이 되어야 한다.
다음으로 중요한 점은 짜임새모형에서 고리(loop)를 찾을 확률이 매우 낮다는 점이다. 더 정확히 노드 개수의 역수에 비례하여 줄어든다. 이에 대한 설명은 생략한다. 이런 성질 덕분에 여기서 공부하는 연결망은 '나무 같은 구조(tree-like structure)'라고 부를 수 있다.
다음으로 생성함수(generating function)를 이용해 간단한 분석을 해보자.
식을 보면 띄엄띄엄 값인 k에 관한 정보가 연속값인 x로 변환(?)되었다. G들을 x로 적당히 미분한 후 x에 0이나 1 같은 값을 넣음으로써 이웃수 분포나 여분 이웃수 분포로부터 유도되는 다양한 양들을 비교적 손쉽게 구해낼 수 있다.
그 중 하나를 보면, 노드 하나를 랜덤하게 골랐을 때 이 노드로부터 도달가능한 노드의 총 개수를 s라고 하자. 즉 연결망이 여러개의 요소들로 이루어졌다고 하면(요소들의 크기의 합은 연결망의 크기다.) 노드 하나를 골랐을 때 그 노드가 속한 요소의 크기가 s가 될 확률을 구하는 문제가 된다. 이 확률분포에 관한 생성함수를 위 식들처럼 정의하되 이를 H_0(x)로 나타내자. 비슷하게, 링크 하나를 랜덤하게 골랐을 때 이 링크를 따라서 도달가능한 노드의 총 개수를 t라고 하고, t의 확률분포에 관한 생성함수를 H_1(x)라고 하자.
그럼 위와 같은 식을 얻는다. 왜 이런 식이 얻어졌는지 설명하기 귀찮;;; 일단 넘어가자;;; 이제 평균 요소 크기, 즉 <s>를 H_0(x)로부터 구할 수 있다.
여기서 z_2는 이웃들의 이웃수의 평균이다. 다음으로, 거대요소의 크기를 연결망 크기로 나눈 값 S는 다음 식으로부터 얻어진다.
여기서 u는 앞글의 u와 같다. 위 오른쪽 식이 뜻하는 바는, 노드 하나가 거대요소에 포함되지 않을 확률은, 그 노드에 달린 링크를 따라가서 도착한 노드 역시 거대요소에 포함되지 않을 확률의 기대값과 같다는 말로 볼 수 있다. 이 글은 여기까지.
