[실생활 속의 수학 #4] 왜 내가 팔로잉하는 사람들은 나보다 평균적으로 팔로워 수가 많아보일까요?

mathsolver (53)in #kr • 6 years ago (edited)

[1]

팔로워 수에 숨겨진 수학 - Friendship 패러독스

1. SNS를 수학적으로 어떻게 표현할까?

SNS를 수학적으로는 크게 두 가지로 나눌 수 있다.

1-1. 내가 팔로우하는 사람도 자동적으로 나를 팔로우 하는 경우

대표적인 예로 페이스북이 있다. 페이스북에서의 친구 신청은 상대방이 수락하는 경우에만 받아들여지며 이때 자동적으로 그 사람도 나를 친구로 받아들이기 때문에 A라는 사람이 B를 팔로우하면, B도 A를 팔로우 한다. 따라서 굳이 팔로워, 팔로우를 구분할 필요없이 "친구" 관계라고 받아들여도 무방하다. 이는 다음과 같은 무방향성 그래프 모델로 나타낼 수 있다.

SNS 사용자들을 꼭짓점으로 놓고, 만약 두 사람이 서로 친구관계이면 둘을 하나의 변으로 잇는 것이다. 예를 들어서 다음과 같은 그래프에서는

[2]

1번 사람은 2번, 5번과 친구 관계
2번 사람은 1번, 5번과 친구 관계
3번 사람은 2번, 4번과 친구 관계
4번 사람은 3번, 5번, 6번과 친구 관계
5번 사람은 1번, 2번, 4번과 친구 관계
6번 사람은 4번과 친구 관계

이다.

1-2. 팔로우와 팔로워가 구분 되는 경우

대표적인 예로 이곳, STEEMIT (스팀잇)이 있다. 스팀잇에서는 내가 상대방을 팔로우 한다고 해서, 상대방이 자동적으로 나를 팔로우 하지는 않는다. 따라서 이 경우에는 팔로우, 팔로워를 구분해야 하며 이는 다음과 같은 방향성 그래프 모델로 나타낼 수 있다.

SNS를 사용자들을 꼭짓점으로 놓고, 만약 A가 B를 팔로우 하면, A에서 B로 가는 화살표를 그리는 것이다. 만약 B도 A를 팔로우 하면, B에서 A로 가는 화살표를 하나 더 그린다 (또는 덧대어 그려도 상관없다). 예를 들어서 다음과 같은 그래프 에서는

[3]

1번 사람은 2번과 3번을 팔로우
2번 사람은 1번과 3번을 팔로워로 두고 있다 (혹은 다시 말해 1번과 3번은 2번을 팔로우)
3번 사람은 1번과 4번을 팔로워로 두고 있고, 2번과 4번을 팔로우
4번 사람은 3번을 팔로워로 두고 있고, 3번을 팔로우

일단 이번 포스팅에서는 가장 간단하게 1-1의 경우를 분석해 보도록 하겠다.

2. 나의 친구 수는 왜 내 친구들의 평균적인 친구 수보다 적어보일까?

제목이 헷갈린다 싶으면 다음과 같은 예시를 들어보겠다.

[4]

1번 사람의 경우, SNS상의 친구는 3명이다. (3번, 9번, 10번) 그런데 각각의 친구들의 친구 수를 살펴보면 3번의 경우에는 3명 (1, 7, 8), 9번의 경우에는 3명 (1, 4, 10), 10번의 경우에는 4명 (1, 5, 6, 9)로 평균 $\frac{3 + 3 + 4}{3} = 3.33$ 명의 친구 수로 내 친구 수 보다 크다.
위의 예시가 좀 어거지다 싶으면, 2번 사람을 보자. 2번은 친구가 4번 1명이다 (ㅜㅜ) 그런데 4번의 친구는 2, 6, 8, 9 총 4명으로 4 > 2가 성립한다.

물론 반례도 존재한다. (당연히 모든 사람이 이를 만족할 수 는 없다. 그렇게 되면 모순이 발생한다. 왜일까요...?)

10번의 경우, 친구 수 는 4명이지만, 각각의 친구들의 친구수는 3, 3, 2 ,2 로 평균이 오히려 자신의 친구 수 보다 작다.

따라서 우리는 문제상황을 다음과 같이 수정할 필요가 있다.

평균적으로 SNS 상의 대부분의 사람들은 친구수가 친구들의 평균적인 친구 수보다 적어 보일까?

편의상 문제상황을 만족하는 사람들의 집단을 관심 집단 이라 부르자. (여기서 관심은 부정적 의미가 절대 아님을 밝힙니다. 단순히 우리가 분석하고자 하는 집단이기에 관심이 가는 집단이어서 이렇게 지었습니다 )

3. 수학적인 분석을 위해서 알아야 할 것들

먼저 다음과 같이 약속한다.

SNS 상에는 총 $n$ 명의 사람들이 있으며, 이들을 편의상 1, 2, ..., $n$ 으로 나타낸다.
만약 $i$ 와 $j$ 가 친구라면 $a_{ij} = 1$ , 그렇지 않다면 $a_{ij} = 0$ 을 부여하여, $n \times n$ 행렬

$\mathbf{A} = (a_{ij})$

를 만든다. 당연히 자기 자신은 자기 자신와 친구를 맺을 수 는 없으므로 ( $a_{ii} = 0$ ) , section 1-1에서 본 대로 친구관계는 대칭적이므로 $a_{ij} = a_{ji}$ 가 성립한다.

$i$ 의 총 친구 수 는 따라서

$\sum_{j=1}^{n} a_{ij}$

로 나타낼 수 있다. 이 값을 $d_i$ 로 놓자. 그런 다음 $n \times 1$ 행렬

$\mathbf{d} = \begin{bmatrix}d_1 \\ d_2\\ ...\\ d_{n-1}\\ d_n \end{bmatrix}$

를 정의한다.

4. 계산

이제 문제상황을 수학문제로 변환시켜야한다. 먼저, 문제상황에서

4-1

SNS상 사람들의 평균적인 친구수 는

$\frac{d_1 + d_2 + ... + d_n}{n} = \frac{1}{n}\sum_{i=1}^{n} d_i$

로 쉽게 구해진다.

4-2

이제, 친구들의 평균적인 친구수를 구해야 하는데, 얘는 쫌 헷갈린다. 먼저 $i$ 의 친구들은 $a_{ij} = 1$ 를 만족하는 $j$ 들 이다. 이런 특성을 만족하는 $j$ 의 총 친구 수 는 정의에 의해 $d_j$ 이다. 따라서, $i$ 의 친구의 친구 수 는 총

$\sum_{j=1}^{n} a_{ij} d_j$

이다. 당연히, $i=1,2,..., n$ 모두에게 적용시켜보면, 모든 친구들의 친구 수의 합은

$\left( \sum_{j=1}^{n} a_{1j} d_j \right ) + \left( \sum_{j=1}^n a_{2j}d_j \right ) + ... + \left( \sum_{j=1}^n a_{nj}d_j \right ) = \sum_{i=1}^{n} \sum_{j=1}^{n}a_{ij} d_j$

이다. 이제 이것의 평균을 구하자. 여기서 주의할 것은 이 값을 무엇으로 나눠야 할지 이다. 대부분의 사람들은 그냥 전체 사람 수 $n$ 으로 나누는데, 이는 당연히 틀린 평균이다. 우리가 원하는 것은 친구들의 친구 수 의 평균이므로, 전체는 사람들의 총 친구 수 가 되어야 한다. 따라서

$\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} d_j}{d_{1} + ... + d_n} = \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} d_j}{\sum_{k=1}^{n} d_{k}}$

가 우리가 원하던 값이다. 따라서 문제상황은

$\frac{1}{n} \sum_{i=1}^{n} d_i \leq \frac{\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} d_j}{d_{1} + ... + d_n} = \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} d_j}{\sum_{k=1}^{n} d_{k}}$

를 푸는 것과 같다.

여기서 잠깐, (2)번 식은 너무 복잡해 보인다. 머리가 아파오지만, 분자를 도식화 시켜보자. [5]

$a_{11}d_1$	$a_{12}d_2$	...	$a_{1,n-1}d_{n-1}$	$a_{1n}d_n$	$=\sum_{j=1}^{n} a_{1j} d_j$
$a_{21}d_1$	$a_{22}d_2$	...	$a_{2,n-1}d_{n-1}$	$a_{2n}d_n$	$=\sum_{j=1}^{n} a_{2j} d_j$
...	...	...	..	...	..
$a_{n-1,1}d_1$	$a_{n-1,2}d_2$	...	$a_{n-1,n-1}d_{n-1}$	$a_{n-1,n}d_n$	$=\sum_{j=1}^{n} a_{n-1,j} d_j$
$a_{n1}d_1$	$a_{n2}d_2$	...	$a_{n,n-1}d_{n-1}$	$a_{nn}d_n$	$=\sum_{j=1}^{n} a_{nj} d_j$
$=\left( \sum_{i=1}^{n} a_{i1} \right )d_1$	$=\left( \sum_{i=1}^{n} a_{i2} \right )d_2$	...	$=\left( \sum_{i=1}^{n} a_{i,n-1} \right )d_{n-1}$	$=\left( \sum_{i=1}^{n} a_{in} \right )d_n$	$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} d_j$

우리는 (2)번에서 잘 보면, 가로 방향으로 항들을 더했다. 이번에는 세로 방향으로 더해보자 (이는 항이 유한개 이므로, 더하는 순서를 바꾸어도 상관 없기에 유효하다). $a_{ij} = a_{ji}$ 성질을 적극 활용하면

$\begin{align*} &\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} d_j \\ &= \left( \sum_{i=1}^{n} a_{i1} \right )d_1 +\left( \sum_{i=1}^{n} a_{i2} \right )d_2 + ...+ \left( \sum_{i=1}^{n} a_{in} \right )d_n \\ &=\left( \sum_{i=1}^{n} a_{1i} \right )d_1 +\left( \sum_{i=1}^{n} a_{2i} \right )d_2 + ...+ \left( \sum_{i=1}^{n} a_{ni} \right )d_n \\ &= d_1^2 + d_2^2 + ... + d_n^2 = \sum_{i=1}^{n} d_i^2 \end{align*}$

로 놀랍게도 간단한 식으로 바뀐다. (사실 생각해보면...) 따라서 우리가 풀고자 하는 부등식은

$\frac{1}{n} \sum_{i=1}^{n} d_i \leq \frac{\sum_{i=1}^{n} d_{i}^2}{\sum_{i=1}^{n} d_i} \iff \left( \sum_{i=1}^{n} d_i \right )^2 \leq n \sum_{i=1}^{n} d_i^2$

로 바뀐다. 어디서 많이 본 부등식인데... 기억을 떠올려보면 코시-슈바르츠 부등식 이 생각날 것이다.

$n = \sum_{i=1}^{n} 1^2$

이므로

$\left( \sum_{i=1}^{n} d_i \right )^2 \leq \left( \sum_{i=1}^{n}1^2 \right ) \left( \sum_{i=1}^{n} d_i^2 \right)$
이 되어 코시 슈바르츠 부등식에 의해 우리의 문제상황에 대한 답은 YES! 이다.

5. SNS 생태계와의 관계

SNS 생태계를 어떻게 정의할 지는 사람마다 다르겠지만, 임의의 두 SNS 이용자를 잇는 친구관계가 반드시 존재하는 생태계를 건전한 생태계로 정의한다면 (즉, 정보단절은 일어나지 않음) 관심 집단의 크기는 사실 SNS 생태계와 큰 관련은 없다. 다음 예시를 보자.

0, 11, 17을 제외한 15명 모두 관심 집단이지만 정보 단절은 일어나지 않을 뿐더러 양방향 소통이 안되는 사람들 또한 존재하지 않는다. 각 파벌 간의 정보교류는 0, 11, 17 간에 이루어지므로 정보 독점이 문제가 되지 않냐고 반문 하는 사람들을 위해 다음 예시를 준비해봤다.

2, 7을 제외한 모든 사람이 관심 집단에 속하지만, 그렇다고 2와 7이 정보를 독점하고 있다고 보기에는 어렵다. (정보 교류가 2와 7을 제외하고도 가능하다). 또한 관심 집단에 속하는 사람이라고 해서 SNS상에서 정보 교류에 소외 됐다고 보기도 어렵다.

12는 관심집단이지만, 12없이는 정보교류가 일어날 수 없다. ㅋㅋ 결국 말하고자 하는 바는 관심 집단의 크기 만으로는 SNS의 생태계, 정보 교류에 관해 단언할 수 없다는 것이다.

5. 그래서 결론은 뭔가요?

우리가 보인 것은 친구 수의 평균은 친구의 친구 수의 평균 보다 작다 는 것이다. 어디까지나 평균적 인 현상임에 주의해야한다. SNS 관계망의 실제 조직도에 따라 관심 집단의 크기는 굉장히 달라진다.
위 부등식의 등호가 성립할 필요충분조건은 (코시-슈바르츠 부등식의 등호성립조건 참조)