* 2006/07/10
'균형이론'으로 검색을 하니 equilibrium theory가 대부분이다. 물리학 용어대로 하자면 equilibrium은 평형(하긴 그게 그거다)으로 옮기고 balance가 균형인 것도 좋을 것 같다. 아니면 오히려 '조화'라고 옮기는 것은 어떨지. 일단 균형이론(balance theory)이라고 부르자.
우선 와써만과 파우스트(Wasserman and Faust)의 <사회연결망분석(Social Network Analysis)>(1994) 6장 구조적 균형과 이행성(Structural Balance and Transitivity)을 보자. 삼각관계에서 셋 모두 친구라면 균형상태(balanced state)에 있다고 할 수 있다. 또는 셋 중 둘은 친구인데 나머지 하나가 이 둘과 적대적이라면 이 역시 균형상태라고 할 수 있다. 균형상태가 아닌 경우는 A와 B, B와 C는 친구인데 A와 C는 적대적인 경우이다. 또는 셋 모두 서로에 대해 적대적인 경우도 불균형상태(imbalanced state)에 있다고 한다. 이것이 하이더(Fritz Heider)의 인지균형(cognitive balance)에 관한 아이디어이다.
이러한 균형이론을 일반화한 것이 구조적 균형이며 구조적 균형상태에 있는 경우 사람들은 모두 한 그룹에 속하거나 또는 두 그룹으로 나뉠 수 있다. 후자의 경우 각 그룹에 속한 사람들끼리는 모두 친구이며 그룹 사이의 관계는 모두 적대적인 경우다. 어떤 연결망이 있다고 하자. 각 링크에는 (+) 또는 (-)라는 기호가 붙는다. 즉 두 노드가 친구이면 (+)를, 두 노드가 적대적이면 (-)를 부여하는 것이다. 연결망의 링크들로 이루어진 어떤 순환(cycle)을 생각하자. 순환이라 함은 한 노드에서 출발하여 링크를 따라 가다가 다시 자신으로 돌아올 때 그 링크들의 나열을 가리키는 것이다. 이 링크들에 부여된 기호 중 (-)의 개수가 짝수인 경우 이 순환을 (+)라고 부른다. 기호가 (-)인 링크가 홀수개인 순환은 (-)가 된다. 이것은 마치 (-1)*(-1) = +1 인 것과 같으며 이를 대립 이중성 원리(principle of antithetical duality; 내가 우리말로 옮겨봤는데 정확한 번역어는 모름)라고 부른다. 그리고 연결망의 모든 순환이 모두 (+)인 경우 이 연결망은 균형이며 (-)인 순환이 하나라도 있으면 불균형 연결망이다.
해래리(Harary)는 연결망 이론을 이용하여 균형이론에 관한 정리를 제시했다.
Theorem 9.1 (Harary(1954)). A signed graph is balanced if and only if the vertices can be partitioned into two classes so that every edge joining vertices within a class is + and every edge joining vertices between classes is -.앞서 말한대로 구조적 균형을 이루는 연결망의 노드들은 두 그룹으로 나뉘며 각 그룹의 노드는 모두 친구이며 두 그룹 사이의 관계는 모두 적대적이라는 정리다.
- F.S. Roberts, Graph Theory and Its Applications to Problems of Society (1978), pp. 80
물론 이 이론은 각 링크가 방향성을 갖는 경우에도 적용될 수 있다. 또한 어떤 연결망이 '얼마나' 균형잡혀 있는가를 측정하는 값을 정의할 수도 있다. 연결망에 포함되어 있는 가능한 모든 순환의 개수를 TC라고 하고 그 순환들 중 기호가 (+)인 것들의 개수를 PC라고 하면, PC/TC가 균형지수(index for balance)로 정의된다.
완전연결망(complete graph; 모든 노드들이 서로 연결되어 있는 연결망)의 경우 구조적 균형인 시스템은 두 개보다 많은 그룹으로 나뉠 수 없다. 구조적 균형인 연결망이 세 개의 그룹으로 나뉜다고 가정해보자. 각 그룹을 이루는 노드들은 모두 (+)인 링크로 이어져 있을 것이며, 각 그룹 사이의 링크는 모두 (-)일 것이다. 그런데 세 그룹에서 한 노드씩 골라서 이들 사이의 삼각형을 만들어보자. 세 노드 모두 다른 그룹에 있으므로 이 삼각형의 세 링크 모두 (-)일 것이므로 이 삼각형은 균형상태가 아니다. 이는 가정과 모순되므로 가능한 그룹의 수의 최대값은 2이다.
하지만 완전연결망이 아닌 경우에는 연결되어 있지 않은 노드들이 같은 그룹에 속할 수도 있고 아닐 수도 있게 된다. 이로부터 뭉침가능성(clusterability; 역시 정확한 번역어는 모르겠다)이 정의된다. 뭉침가능한 연결망은 구조적 균형상태에서도 두 개보다 많은 개수의 그룹으로 나뉠 수 있다.
다음으로 균형이론을 물리학적인 방법으로 연구한 논문을 소개한다. 보스톤 대학과 로스알라모스 국립연구원의 과학자들이 연구한 것으로 작년 Phys. Rev. E에 출판된 것이다. 제목은 "연결망에서 사회적 균형의 동역학(Dynamics of social balance on networks)"이다1.
이들이 제시한 모형은 2 가지인데 첫번째를 국소적 삼자 동역학(local triad dynamics; LTD)이라 부른다. 시각마다 삼각형 하나를 골라서 그것이 균형이면 내버려두고 불균형이면, 즉 삼각형의 세 링크 중 홀수개(1, 3)가 (-)이면 이들을 균형 삼각형으로 바꾸는 규칙이 적용된다. (-) 링크가 하나인 불균형 삼각형은 p의 확률로 (-) 링크가 0개인 것으로 바뀌고 1-p의 확률로 (-) 링크가 2개인 것으로 바뀐다. (-) 링크가 3개인 불균형 삼각형은 1의 확률로 (-) 링크가 2개인 균형 삼각형으로 바뀐다. 이 규칙을 계속 적용하면 p가 0.5보다 크거나 같을 때 '낙원(paradise)' 상태, 즉 모든 링크가 (+)인 경우로 끝나며, p가 0.5보다 작을 때는 (+) 링크의 밀도가 1이 아닌 일정한 값에 머문다.
두번째 모형은 제한된 삼자 동역학(constrained triad dynamics; CTD)이라 부른다. 여기서는 삼각형을 고르는 대신 링크를 아무거나 골라서 그 링크의 부호를 바꾸는 것이 불균형 삼각형의 수를 늘리지 않으면 바꾸고 늘리는 경우에는 부호를 그대로 두는 규칙을 적용한다. 당연히 이 연결망은 '낙원' 상태로 갈 것이라고 예상할 수 있지만, 실제로는 낙원 상태뿐만 아니라 혼잡 상태(jammed state)로도 귀결된다. 혼잡 상태에서는 불균형 삼각형이 존재하지만 그 링크의 부호를 바꾸는 것이 불균형 삼각형의 수를 늘리기 때문에 부호를 바꿀 수 없어서 결국 그 상태에서 탈출하지 못하는 경우를 가리킨다.
뭐 이런 연구도 있다는 것이다. 그리고 이런 연구를 소개하는 것도 역시 이번주에 발표할 내용과 연관되기 때문이다.
- T. Antal, P.L. Krapivsky, and S. Redner, Phys. Rev. E 72, 036121 (2005) [본문으로]
