여튼 2007년에 PNAS에 실린 논문을 보면(...이라고 했지만 제대로 안 봄;;;) 다음과 같은 식이 나온다.
$$L(X)=L(Y)+L(X|Y)$$
$$L(Y)=n\log m+\frac{1}{2}m(m+1)\log l$$
$$L(X|Y)=\log\left[\prod_{i=1}^m {n_i(n_i-1)/2 \choose l_{ii}}\prod_{i>j}{n_in_j \choose l_{ij}} \right]$$
X는 기술하고자 하는 연결망(n개의 노드와 l개의 링크로 이루어짐)이고 Y는 연결망 X의 노드들을 m개의 모듈(군집)로 묶어주는 분할(partition)을 나타낸다. L(X)는 이런 연결망을 기술하기 위해 필요한 정보량을 나타내며, L(Y)는 분할을 위한 정보량을 나타낸다. 자연스럽게 L(X|Y)는 Y가 주어졌을 때 X를 기술하는데 필요한 정보량이다.
L(Y)의 첫번째 항부터 보자. 각 노드는 m개의 모듈 중 하나에 포함되어야 하는데 이를 기술하기 위한 정보량은 log m이다. 로그의 밑을 2라고 하면 예/아니오로 대답할 수 있는 질문을 몇 개를 해야 m개 중 하나를 확정할 수 있냐는 문제가 된다. m=16이라면 예/아니오로 대답할 수 있는 질문 4개를 던지면 16개 중에 어떤 것인지 밝혀낼 수 있다. 이 질문의 개수를 '정보량'이라 한다.
각 노드마다 log m의 정보량이 필요하므로, n개의 노드에 대해 n log m의 정보량이 필요하다.
L(Y)의 두번째 항을 보자. 앞에서 했던 대로 각 링크에 대해...라는 식으로 설명할 수 없다는 게 보인다. 지금은 노드들을 m개의 모듈로 구분하는 게 중요하며 링크는 거기에 따라 결정되어버리기 때문이다. 대신 링크들이 어떻게 각 모듈에 있는지, 또는 모듈 사이에 있는지를 생각해야 한다. n개의 노드를 m개의 모듈로 분할했을 때 링크는 m개의 모듈 중 하나 안에 있거나 서로 다른 모듈 사이에 있거나인데 그 가능한 경우가 모두 m(m+1)/2가 된다. 그래서 각 경우에 대해 어떤 링크가 있을 수 있는지를 기술하기 위한 정보량은 log l이다.
하지만 노드의 경우처럼 명확하게 이해되지 않는다. 노드의 경우는 m개의 상자에 n개의 구슬을 나눠 담는 문제로 생각하면 분명하다. 하지만 위 식에 따르면, 링크의 경우는 l개의 상자에 m(m+1)/2개의 구슬을 나눠 담는 문제가 되는데 각 상자에는 여러개의 구슬이 있을 수 있으므로 링크 하나가 여러 경우에 포함될 수 있다는 말이 된다. 그래서 이상하다. 강연자에게 이걸 질문했으나 명쾌한 답을 듣지는 못했다.
마지막으로 L(X|Y)를 보자. 이는 분할 Y가 주어진 상황에서 연결망 X를 어떻게 기술할 것인가에 관한 정보량을 나타낸다. n_i는 모듈 i에 포함된 노드 개수이며 이 노드 사이의 실제 링크수가 l_ii다. 모듈 i의 모든 노드와 모듈 j의 모든 노드 사이의 링크수가 l_ij다.
이로부터 m을 정해놓고 L(X)를 최소화하는 분할을 찾아서 그때의 L(X)를 구한다. m을 변화시키면서 L(X)이 가장 작아질 때의 m도 구할 수 있는데 이 경우가 연결망 X의 모듈을 가장 잘 기술한다고 해석할 수 있다.
여튼 마틴 로스발의 발표를 들으면서 이 방법의 영모형(null model)은 뭘까를 생각해보았다. 얼핏 정보이론의 틀을 이용함으로써 영모형 없이 군집찾기를 한 것 같은데, 군집찾기 방법에는 어떤 식으로든 영모형이 필요한 것 같은데도, 마틴의 방법이 명시적으로 이를 말한 것 같지는 않아 보였다(논문을 제대로 읽어보면 있을지도;;;). 영모형이 정말 필요하냐하면 그건 모르겠지만, 위의 L(X|Y)를 보면 결국 확률구역모형(stochastic block model)의 틀을 이용한 것 같다. 즉 확률구역모형을 영모형으로 썼다는 해석이 가능하다. 생각해보니 백판에 확률구역모형을 설명할 내용 중 하나로 써놓았군;;;
여전히 모호한 부분이 있어서 잘 아는 친구한테 물어보기도 했는데 여전히 모호하게 남겨져 있다. 논문을 제대로 읽어봐야겠지만 일단 이 정도로 메모를 남겨놓고 나중으로 미루자;;;
