Balanced graph와 unbalanced graph

이미지
사람과 사람 사이의 관계를 그래프로 나타내보자. 그렇다면 사람은 node로 표현될 것이고, 두 사람이 서로를 알고 있다면 두 node 사이의 edge를 그릴 수 있다. 실제로는 내가 모르는 사람이 나를 알고 있을 수도 있고, 내가 아는 사람이 나를 모를 수도 있지만, 그런 복잡한 경우는 생각하지 않고 서로 간에 알고 있는 경우만을 고려하도록 하자.1)
 이때 두 사람은 친구이거나 적일 것이다. 현실적으로는 그냥 아는 사람이고 적인지 친구인지 별생각 없을 수도 있거나, 내가 친구라고 생각하는 사람이 나를 적으로 생각할 수 있지만, 이런 경우 문제가 복잡해지니 생각하지 않도록 하자.
 그러면 친구인 사람 사이의 edge에는 +사인을, 적인 사람 사이의 관계에는 -사인을 추가하여 signed undirected graph2)로 표현할 수 있다.  사람 사이의 관계를 signed graph로 표현한다면, 이는 아래의 4가지 모습 중 하나일 것이다.
 만약 친구일 확률과 적일 확률이 똑같이 1/2로 랜덤하게 그래프를 생성하였다면, 모두가 친구로 생각하거나 모두가 적으로 생각할 확률은 각각 1/8이고, 한 명은 다른 두 명을 적이라고 생각하는데 두 사람은 서로 친구라고 생각하거나, 친구로 생각하는 두 사람이 서로 적일 확률은 각각 3/8으로 나타날 것이다.
 하지만 실제 인간관계를 그래프로 그렸을 때는 첫 번째나 세 번째 삼각형이 나올 확률은 기대했던 것보다 높게 나오고, 두 번째나 네 번째 삼각형이 나올 확률은 기대했던 것보다 낮게 나온다. 이 두 삼각형은 다른 삼각형으로 쉽게 변하기 때문이다.

 내가 친구라고 생각하는 두 사람이 서로를 적으로 생각하는 경우를 보자. 이 경우 나에게 압박이 가해져서 한쪽 관계를 끊거나, 적으로 돌아서기 쉽다. 3명이 서로를 모두 적으로 생각하는 경우도 쉽게 변한다. 이런 경우 공동의 적을 상대하기 위해 적이었던 두 사람이 손을 잡기 쉽다.
 이렇게 변하기 쉬운 삼각형을 unbalanced triangle이라고 부르고, 이런 삼각형이 …