Balanced graph와 unbalanced graph

사람과 사람 사이의 관계를 그래프로 나타내보자. 그렇다면 사람은 node로 표현될 것이고, 두 사람이 서로를 알고 있다면 두 node 사이의 edge를 그릴 수 있다. 실제로는 내가 모르는 사람이 나를 알고 있을 수도 있고, 내가 아는 사람이 나를 모를 수도 있지만, 그런 복잡한 경우는 생각하지 않고 서로 간에 알고 있는 경우만을 고려하도록 하자.¹⁾

이때 두 사람은 친구이거나 적일 것이다. 현실적으로는 그냥 아는 사람이고 적인지 친구인지 별생각 없을 수도 있거나, 내가 친구라고 생각하는 사람이 나를 적으로 생각할 수 있지만, 이런 경우 문제가 복잡해지니 생각하지 않도록 하자. 그러면 친구인 사람 사이의 edge에는 +사인을, 적인 사람 사이의 관계에는 -사인을 추가하여 signed undirected graph²⁾로 표현할 수 있다.

사람 사이의 관계를 signed graph로 표현한다면, 이는 아래의 4가지 모습 중 하나일 것이다.

만약 친구일 확률과 적일 확률이 똑같이 1/2로 랜덤하게 그래프를 생성하였다면, 모두가 친구로 생각하거나 모두가 적으로 생각할 확률은 각각 1/8이고, 한 명은 다른 두 명을 적이라고 생각하는데 두 사람은 서로 친구라고 생각하거나, 친구로 생각하는 두 사람이 서로 적일 확률은 각각 3/8으로 나타날 것이다. 하지만 실제 인간관계를 그래프로 그렸을 때는 첫 번째나 세 번째 삼각형이 나올 확률은 기대했던 것보다 높게 나오고, 두 번째나 네 번째 삼각형이 나올 확률은 기대했던 것보다 낮게 나온다. 이 두 삼각형은 다른 삼각형으로 쉽게 변하기 때문이다.

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

이렇게 변하기 쉬운 삼각형을 unbalanced triangle이라고 부르고, 이런 삼각형이 있는 그래프를 unbalanced graph라고 부른다. unbalanced graph의 경우 외부에서 압력을 주지 않아도 쉽게 상태가 변한다.

반대로 3명이 모두 친구이거나 공통의 적을 둔 친구 사이를 가지는 경우는 외부 압력이 없는 한 상태가 변하지 않는다.

이런 삼각형을 balanced triangle이라고 부르고, 이런 삼각형으로만 이루어진 그래프를 balanced graph라고 부른다.

---

1) 그래프 안의 모든 사람이 서로 알고 있는 경우. 즉, 모든 node와 연결된 edge를 가지는 경우를 complete graph라고 부른다. 실제 커뮤니티를 조사하면 대부분 서로 모르는 관계이기 때문에 complete graph가 되는 경우는 드물다. 하지만 문제를 단순화하기 위해 앞으로 나오는 그래프는 전부 complete graph라고 가정하도록 하겠다. incomplete graph의 balance에 대해서는 다른 글에서 설명하도록 하겠다.

2) undirected가 directed보다 많이 쓰이기 때문에, undirected는 간단하게 signed graph라고 하고, signed directed graph를 signed digraph라는 이름으로 부르기도 한다.