Paradox of Friendship
tl; dr
- 친구의 역설을 수학적으로 풀어보자.
친구의 역설
왜 나의 친구는 나보다 친구가 많은 것처럼 느껴질까? 그냥 그렇게 느끼는 것 뿐일까? 직관적으로 생각하면 이것은 역설이 아닐 수 있다. 나와 친구가 된 사람 중에서 친구를 많이 사귀는 경향이 있는 사람이 포함되어 있다면, 그 사람의 친구는 나보다 많다. 이런 사람의 숫자가 인구에 적당한 숫자로 분포되어 있다면 이것이 친구의 역설을 만들 수 있다. 진짜 그런지 모형을 통해 따져보자.
용어 정의
네트워크 이론에서 쓰는 용어 몇 가지 정리하자.
| 용어 | 정의 | 기호 |
|---|---|---|
| 노드(node), 버텍스(vertex) | 네트워크에 속한 개체 | \(V, v\) |
| 엣지(edge) | 노드와 노드를 연결하는 선 | \(E, e\) |
| 차수(degree) | 엣지의 수 | \(d(v)\) |
\(V\)는 노드의 집합, \(E\)는 엣지의 집합이다. 해당 집합에 속하는 대표 원소는 각각 소문자 \(v, e\)로 표기한다. 특정한 노드 개체 \(v\)의 차수는 \(d(v)\)로 나타낼 수 있다.
‘방향성이 없는’ 그래프는 \(G = (V, E)\)로 정의한다. 방향성이 없다는 것은 친구 관계가 대칭적임을 뜻한다. 즉, A가 B의 친구라면, B도 A의 친구가 된다. 만일 애정 관계라면 ’짝사랑’과 같은 것이 존재할 수 있지만, 일단 친구 관계에서는 그런 관계가 없다고 하자.
‘평균’ 친구 숫자
네트워크 전체의 평균 친구 숫자 \(\mathbb{E} \left( d(v) \right) (\equiv \mu)\)를 구해보자.
\[ \mu = \dfrac{\sum_{v \in V} d(v)}{|V|} = \dfrac{2|E|}{|V|} \]
식의 분모는 자명하다. 네트워크 \(G\)에 존재하는 개체의 크기를 나타난다. \(\sum_{v \in V} d(v) = 2|E|\)가 되는 것 중요하다. \(E\)는 노드와 노드 사이의 관계를 모두 표시한 집합이다. \(e = (v_i, v_j)\)라면 이는 노드 \(i\)와 \(j\)가 서로 친구임을 나타낸다. 전체 친구의 숫자는 \(e\) 하나당 2개가 된다. 따라서 \(E\)의 크기 \(|E|\)의 두 배가 전체 친구의 숫자가 된다.
’친구의 친구’를 측정하기 위한 표집 확률
우리가 관심이 있는 것은 ’친구의 친구’의 평균적인 크기다. 친구의 수를 재기 위해 친구를 어떻게 골라야 할까? 즉, 친구의 평균 수를 재기 위한 친구를 고를 확률을 먼저 정의해야 한다. 먼저 \(E\)에서 \(e\) 하나를 고른다. \(e=(v_i, v_j)\)라고 하자. \(v_i\)가 여러 친구를 갖고 있다면 집합 \(E\)의 여러 원소에서 \(v_i\)가 등장할 것이다. 이 등장 횟수는 \(d(v_i)\)와 같다. 마지막으로 하나의 엣지는 두 개의 노드를 지니고 있으므로 엣지에서 \(v_i\)를 택할 확률이 \(\frac{1}{2}\)이다. 정리하면 친구의 친구를 측정할 대상인 \(v^{f}\)가 네트워크에서 선택될 확률 \(P(v^f)\)는 다음과 같다.
\[ P(v^f)= \dfrac{d(v^f)}{|E|} \dfrac{1}{2} \]
이 확률에 ’친구의 역설’의 비밀이 숨어 있다. 대상 친구가 선택될 확률은 해당 친구의 차수, 즉 그가 지닌 친구의 숫자, \(d(v^f)\)에 비례한다. 즉, 친구가 많은 친구가 대상으로 선택될 확률이 높은 것이다.
평균 ‘친구의 친구’ 숫자
친구의 친구의 숫자, 정확하게는 그 기대값은 다음과 같이 쉽게 계산된다. \[ \mathbb E(d(v^f)) = \sum_{v^f \in V} P(v^f) d(v^f) = \sum_{v^f \in V} \dfrac{d(v^f)}{2|E|} d(v^f) = \dfrac{1}{2|E|} \sum_{v^f \in V} d(v^f)^2 \tag{1}\]
\(v^f\) 역시 네트워크 내의 한 개체이므로 당분간 상첨자를 떼고 보자. \(d(v)\)의 분산을 생각해보자.
\[ {\rm Var}(d(v)) \equiv \sigma^2 = \mathbb{E}((d(v) - \mu)^2) = \mathbb{E}(d(v)^2) - \mu^2 \]
\(v\)를 무작위로 선택했다면, 다음과 같이 정리할 수 있다.
\[ \mathbb{E}(d(v)^2) = \dfrac{\sum_v d(v)^2}{|V|} = \sigma^2 + \mu^2 \tag{2}\]
\[ \mathbb E(d(v^f)) = \dfrac{1}{2|E|} \sum_{v^f \in V} d(v^f)^2 = \dfrac{|V|}{2|E|} \left( \sigma^2 + \mu^2 \right) = \dfrac{\mu^2 + \sigma^2}{\mu} = \mu + \dfrac{\sigma^2}{\mu}. \]
Discussion
만일 네트워크에서 모든 사람의 친구의 숫자가 동일하다면, 위의 식에서 보듯이 내 친구의 숫자와 내 친구의 친구의 숫자는 동일할 것이다. 모든 사람의 친구의 숫자가 동일하다는 것은 분산이 \(0\), 즉 \(\sigma^2 = 0\), 이라는 뜻이다.
그런데 친구 네트워크가 분산이 0이 되는 형태로 균질하지 않다면, 즉 친구 숫자의 분포가 존재하는 이상 \(\sigma^2 > 0\)이 성립할 수 밖에 없다. 친구 숫자가 균등하지 않는 이상 평균적으로 친구의 친구의 숫자는 내 친구의 숫자보다 크게 된다.
재미 삼아서 극단적인 경우를 만들어 보자. \(n\)명의 네트워크에서 1명과 \(n-1\) 명이 바퀴살 구조로 연결되어 있다고 하자. 이때, \(n-1\) 명의 유일한 친구 1명의 평균 친구 숫자는 \(n-1\) 명이다. 이 집단에서 \(n-1\) 명은 자신의 친구 숫자 \(1\) 명보다 친구의 친구의 숫자가 \(n-1\) 명으로 압도적으로 크다. 이 집단에서 무작위로 1명을 뽑을 경우 거의 모든 경우 내 친구의 숫자보다 친구의 친구의 숫자가 크다고 느낄 것이다. 평균 친구 숫자는 아래와 같다.
\[ \mu = \dfrac{(n-1)\cdot1 + (n-1)\cdot1}{n} = \dfrac{2(n-1)}{n} \]
한편, 친구의 친구 숫자의 평균은 다음과 같다.
\[ \mathbb E(d(v^f)) = \dfrac{(n-1)(n-1) + 1\cdot1}{n} = \dfrac{n^2 - 2n +2}{n} \]
\(n \geq 2\)인 경우 \(E(d(v^f)) \geq \mu\)가 성립한다.
Intuitively…
보다 직관적으로 말해보겠다. 인구 혹은 그래프 전체에 대해서 보자. 개인(개별 노드)의 친구 숫자(차수) 혹은 그 분포가 인구 전체의 평균적인 친구의 숫자를 결정한다. 이때 각 개인의 친구 숫자는 평균을 계산할 때 한 번 반영된다. 그런데 ’친구의 친구’의 숫자는 어떨까? 한 개인이 많은 친구를 지니고 있다고 하자. 그는 누군가의 친구로 여러 번 등장할 것이다. 따라서 ’친구의 친구’의 숫자 계산할 때 친구가 많은 사람은 여러 번 등장한다. 친구가 많은 사람, 즉 큰 숫자가 여러 번 더해지게 되므로 친구의 친구의 숫자는 대체로 개인의 평균적인 친구 숫자보다 클 것이다! 이 동영상을 참고하자.