어제 <네이처>에 나온 파파도풀로스 등의 논문과 이에 대한 바라바시의 논평을 읽고 트위터에서 지인들과 토론을 했는데 내 블로그에 정리하려고 한다. 앞으로 이 두 글을 편의상 '논문'과 '논평'으로 줄여서 부르겠다. 논문의 제목은 "Popularity versus similarity in growing networks"이며 논평의 제목은 "Luck or reason(운이냐 이유냐)"이다.
논문은 사이프러스, 미국, 스페인의 연구그룹들이 공동연구한 결과인데, 그중에서도 미국 UCSD의 CAIDA 그룹이 이 논문의 주요 방법론인 '복잡연결망에서 쌍곡기하(hyperbolic geometry)'를 꾸준히 연구해왔다고 한다. 사실 별로 관심이 없어서 이 그룹의 논문은 본 적이 없다;; 그런데 이 논문에서 쌍곡기하는 방법 또는 트릭일 뿐이라 주요 내용을 이해하는데 별 상관이 없다는 게 내 생각이다.
바라바시의 척도없는 연결망 모형은 새로 생긴 노드가 이미 있던 노드를 선택하여 연결할 때 이미 있던 노드가 선택될 확률을 그 노드의 이웃수에 비례하도록 한 것이었다. 이 규칙을 선호적 연결(preferential attachment; PA)이라 부른다. 이로부터 이웃수 분포가 거듭제곱 꼴이 된다. (자세한 내용은 내 글을 참고.) 이 선택규칙은 이미 있던 링크를 랜덤하게 골라서 그 링크의 양끝 노드 중 하나를 고르는 것과 같다. 결과적으로, 먼저 생긴 노드는 늦게 생긴 노드보다 더 많은 이웃을 갖게 되는데 이를 파파도풀로스 등의 논문에서는 '인기'라고 표현했다. 이는 논평 제목에서 '운'에 해당한다.
파파도풀로스 등의 모형은 이러한 인기뿐 아니라 노드들 사이의 유사도에 기반한 요인까지 고려한다. 기존 노드의 인기도는 그 노드의 생성 시각이 빠를수록 커진다고 가정한다. 기존 노드와 새 노드 사이의 유사도를 정의하기 위해 단위원을 생각하자. 노드가 새로 생길 때마다 0부터 360도 사이의 각도를 랜덤하게 골라서 단위원 위에 표시한다. 노드 사이의 유사도는 이 단위원 위에서의 거리가 가까울수록 커진다. (개념 설명에 초점을 맞추다보니 정확한 정의와 좀 다르다.)
노드가 새로 생길 때마다 기존 노드의 인기도에 기존 노드와 새 노드 사이의 유사도를 곱한 값이 큰 순서대로 일정한 개수를 골라서 연결하게 한다. 여기서 인기도 곱하기 유사도가 "큰 순서대로"라는 게 중요하며, 새 노드가 이 값을 '최적화'하여 기존 노드를 선택했다고 볼 수 있다. 이는 논평 제목에서 '이유'에 해당한다.
이렇게 해도 '결과적으로' 기존 노드가 새 노드에 의해 선택될 확률은 기존 노드의 이웃수에 비례하기 때문에 척도없는 연결망이 나온다. 즉 PA가 결과로서 발현되었으며 이는 PA가 모형의 일부로 들어가 있는 바라바시 모형과 다른 점이다. 물론 논문의 모형에서 인기도가 노드의 생성 시각의 함수가 아니라면 PA는 나타나지 않을 것이다. 어떤 식으로든 빈익빈 부익부 원리가 포함되어야 한다.
그래서 PA를 명시적으로 모형에 포함시키는 것과 인기도를 도입하는 것이 질적으로 얼마나 차이가 있는지는 잘 모르겠다. 또한 바라바시 모형에는 없는 유사도가 분명 자기만의 역할을 하기는 하는데, 모형에서는 어차피 랜덤한 값으로 추상화하여 도입했기 때문에 적당한 해석을 덧붙이면 그만이지만, 이 개념을 실제 연결망에 적용하는 부분에 모호한 점이 있다.
논문에서는 이 개념을 인터넷 AS 연결망, E. coli 신진대사 연결망, 사람들 사이의 신뢰연결망(web of trust)에 적용했는데, 노드가 생긴 시각, 즉 인기도는 데이터로부터 잘 정의되지만 유사도는 모호하게 정의되어 있다. 실제로 각 노드의 유사도(또는 단위원 위의 각도)는 데이터로부터 바로 직관적으로 정의되지 않고 연결망의 전체적인 성질들(평균이웃수, 평균뭉침계수 등)로부터 몬테카를로 방법을 이용하여 '추정'된다. 나는 이게 함정이라고 보는데 논문에서 강조한 바라바시 모형과의 차이가 뭉침계수를 조절할 수 있다는 점이기 때문이다. 바라바시 모형의 뭉침계수는 0인데 반해 이 논문에서는 뭉침계수를 조절할 수 있다. 왜냐하면 모형에 이미 '명시적으로' 들어가 있으니까.
물론 실제 연결망으로부터 그 전체적 성질들을 이용하여 거꾸로 노드의 단위원 위의 각도를 추정할 수 있다고 주장한다면 문제 없다. 하지만 그 '각도'를 유사도라고 굳이 불러야 할 이유가 있는지 모르겠다. 논문에서 이용한 방법에 의하면 이렇게 추정된 각도는 그냥 뭉침계수와 관련된 어떤 양일 뿐이기 때문이다.
마지막으로 '최적화'라는 용어에 대해 언급하고 마치겠다. 분명히 인기도 곱하기 유사도가 큰 순서대로 일정한 개수만큼 고른다는 면에서 최적화라는데 동의한다. 하지만 인기도 곱하기 유사도가 클수록 선택될 확률이 크게 만들면 결과가 질적으로 달라질까? 별로 달라질 것 같지 않다는 생각이 드는데, 정말 그렇다면 이웃수가 많은 노드가 선택될 확률이 높아지는 바라바시 모형과 '랜덤 대 최적화'라는 구도로 대별될 정도까지는 아니게 된다. 그런 맥락에서 바라바시의 논평도 정작 중요할 수 있는 이런 부분은 대충 넘어가면서 '랜덤 대 최적화'라는 구도만을 강조하고 있다.
끝.
