본 포스팅은 단기강좌 인터넷 속의 수학의 강의 들을 요약하는 포스트입니다.
Introduction
흔히 이 세상의 모든 사람들은 나와 6다리 만 건너면 이어져있다고들 말한다. (밀그램의 편지실험) 심지어 나와 상관없어보이는 버락 오바마 대통령도 사회적 거리가 생각보다 가까울 수 있다는 것이다. Facebook의 조사결과에 따르면 Facebook 상에서 연결된 다리의 평균값은 4.74 정도라고 한다. 근데, 진짜 정말로 모든 사람들과 6 steps로 연결이 가능할까? 이 글에서는 이런 현상에 대해서 설명하고, 실제 사람과 사람 간의 네트워크가 어떤 식으로 구성되고, 그것을 수학적으로 어떻게 모델링하고 있는지를 다루게 될 것이다.
최근 10년 사이 네트워크는 사람들의 생활에 정말 정말 큰 영향을 미치고 있다. 특히 소셜 네트워크 혹은 SNS라고 불리는 새로운 형태의 서비스의 등장으로 인해 사람들과 사람들 사이의 긴밀한 연결이 더 가능해졌다. 이런 네트워크가 파생된 것은 사실 생각보다 역사가 짧은데, 실제 정보를 전달할 때는 전기신호로 보내야하고, 그 신호를 보내는 channel이 굉장히 noisy한데, 과연 이런 nosiy channel로 realistic한 시간 안으로 정보를 온전하게 전달할 수 있을까? 당연히 정보가 손실되면 retransmission을 시도해서 상대편이 정보를 다시 받을 수 있도록 할 수 있지만, 그 반복해서 보내는 retransmission이 실제 의미있는 숫자 이내로 성공할 수 있겠냐는 문제에 대해 아무도 답을 할 수가 없었기 때문에 연구가 지지부진한 상태였다. 그러나 지금으로부터 약 60여년 전 클로이 섀넌이라는 기라성같은 연구자가 noisy한 channel에서 error-free communication이 가능하다는 것을 증명해냈고, 그 이후로 통신학의 급격한 발전이 이루어졌다. 우리가 쓰는 인터넷은 군대 및 연구기관의 ‘알파넷’이라는 통신 기술이 그 전신인데, 이 기술은 전쟁으로 인해 한 기관이 파괴되어도 다른 곳에서 정보를 전송할 수 있도록 분산시킬 용도로 개발되었다고 한다. 지금 우리가 사용하는 스위칭, 패킷 등의 기술도 이때 개발 되었다. 우리가 진짜 ‘인터넷’ 이라고 부르는 월드 와이드 웹은 유럽의 입자 가속기 연구서 (CERN)에서 데이터 교환의 용이성을 위해 처음 등장하게 되었다. 그리고 수 많은 사람들의 노력으로 우리가 현재 쓰는 모습의 인터넷 네트워크가 탄생한 것이다.
Network Problems - Graph Theory
앞서 네트워크의 역사에 대해 간략하게 설명했는데, 그렇다면 실제 이런 네트워크를 잘 구성하기 위해서 우리가 풀어야하는 몇 가지 문제점들이 존재한다. 특히 네트워크에 요구되는 사항들을 충족시키려면 네트워크를 잘 이해하는 것이 필요하고 이런 것을 위해 네트워크 과학이라는 분야까지 생겼을 정도로 문제가 생각보다 광대하다. 몇 가지를 꼽아보자면, 좋은 네트워크는 (1) 효율적인 소통을 해야하고, (2) 외부의 공격에 견고하게 방어를 할 수 있어야하고, (3) 복잡성이 낮고 간결해야 한다. 그렇다면 이런 사항들을 충족시키기 위한 몇 가지 문제들을 살펴보자. 최초의 네트워크 문제는 쾨니히스베르크의 다리라고 불리는 문제이다. 누가 처음 만들었는지는 모르고 언제부터 존재했는지는 모르지만, 1735년 오일러가 이를 수학적으로 증명해낸 문제이다. 이 문제에서 부터 사실 네트워크 이론이 나왔다고 해도 과언이 아니다. 문제는 간단하다. 아래의 그림을 보면서 자세히 설명해보자.
오래전에 프로이센이라는 국가의 쾨니히스베르크라는 자그마한 도시가 하나 있었다. 이 도시의 지식인들이 그냥 도시를 산책하다가 심심했던 모양인지 생각해낸 문제이다. 쾨니히스베르크에는 프레겔 강이 흐르고 있고, 이 강에는 두 개의 큰 섬이 있다. 그리고 이 섬들과 도시의 나머지 부분을 연결하는 7개의 다리가 있다. 이때 7개의 다리들을 한 번만 건너면서 처음 시작한 위치로 돌아오는 길이 있는가 하는 것이 문제이다. (출처: 위키피디아) 이 문제가 꽤 오랜 기간 동안 풀리지 않은채로 존재하다가 오일러가 이를 엄청나게 간단한 방법을 통해 해결을 해버렸다.
다리와 섬을 위의 그림처럼 ‘그래프’로 표현하게 되면 문제가 엄청나게 쉬워진다. 이 그래프가 한붓그리기가 가능하기 위해서는 엣지가 홀수 개인 노드가 1개만 있어야하는데 이 그림에서 볼 수 있듯 그보다 그런 노드가 많음을 알 수 있다. 오일러의 이 풀이로 인해 ‘그래프 이론’이라는 새로운 분야가 창조되었고, 이는 우리가 풀고싶은 네트워크 문제를 해결하기 위해 필요한 가장 기본적이고 필수적인 분야 중 하나라고 할 수 있을 것이다.
Network Problems - 6 degree of separation
또 다른 실험을 하나 살펴보자. 1967년, 미국의 스탠리 밀그램은 아래와 같은 간단한 실험을 제작했다.
- 네브래스카 주 오마하라는 작은 도시에 사는 주민 296명에게 메사추세츠 주 보스턴의 은행가로 가는 편지를 전달시키는 것이 이 실험의 목적이다.
- 전달은 반드시 전달자가 직접적으로 친밀한 사람에게만 (first-name basis) 가능하다. 즉, 최종 수신인은 정해져있는 상황에서, 최종 수신인을 모르는 경우에 그 사람을 가장 잘 알만한 자신의 지인들에게 이 편지를 전달하는 것이다.
- 매번 편지가 전달될 때마다 편지에 보내는 사람의 이름과 서명을 첨부하고, 또한 하버드로 엽서를 따로 보내 traking을 용이하게 하였다.
이 실험은 결국 미국이라는 network에서 지리적, 사회적으로 가장 고립되었을 것이라고 예상되는 두 node로 이동하기 위해서 평균적으로 얼마나 많은 step이 요구되는가를 측정하기 위한 실험이다. 결과는 어땠을까? 10? 20? 100? 아래 그래프가 그 결과이다.
당연한 얘기지만 가로축은 얼마나 많은 사람을 거쳤는가를 의미하고, 세로축은 해당 거리에 해당하는 사람이 얼마나 많은가를 의미한다. 이 실험은 총 217개의 편지 중에서 64개의 편지만 최종적으로 도달하게 되었고 (성공확률 약 30%) 평균 거리는 약 5.2이며 중간값은 6이었다. 때문에 이 실험결과를 일컬어 모든 사람들이 6step으로 이어져있다고 해석해 6단계 분리이론이라고도 부르기도 한다. 이 실험이 완벽하지 않고 logic whole이 존재한다고 주장하는 일부 비판적인 시선이 있는 것은 사실이지만, 이 실험은 충분히 의미가 있고, 무엇보다 실제로 이를 실험적으로 증명하는 것을 시도한 첫 번째 실험이라는 점에서 의미가 있다.
이와 비슷한 다른 예시가 있다. 수학에서 에르도쉬 숫자라는 것이 존재하는데, 이 사람은 엄청나게 많은 공동연구를 진행한 사람이고, 그래서 업적이 뛰어난 사람일수록 이 사람과 공저자를 한 경험이 많다고 한다. 그래서 그 아이디어를 차용해 그 사람이 얼마나 학계에서 권위가 있는지를 측정하는 지표로 쓰이는 것이 이 숫자인데, 에르도쉬 본인은 이 숫자가 0이다. 그리고 에르도쉬와 공저를 한 경험이 있는 연구자의 숫자는 1이다. 만약 내가 직접적으로 에르도쉬와 공저를 하지 않았더라도, 에르도쉬 넘버가 1인 사람과 공저를 한 경우에 내 에르도쉬 넘버는 2가 된다. 즉, 내가 얼마나 에르도쉬라는 사람과 가까운 관계인지를 측정하는 수단인 것이다. 참고로 나는 조만간 에르도쉬 넘버가 3이 될텐데, 내 지도교수님의 에르도쉬 넘버가 2이기 때문이다.
비슷한 숫자로 케빈베이컨 숫자라는 것이 있는데, 이번에는 논문 공저자라는 다소 strict한 rule이 아니라 영화 배우 케빈베이컨과 같이 영화를 출연한 사람에게 (엑스트라도 포함) 같은 방식으로 숫자를 매기는 것이다. 꽤 재미있는 것은, 미국의 그 어떤 영화배우도 이 배우와 거리가 6이하라고 한다. 인터넷 웹사이트도 있다. 사실 케빈 베이컨이 가장 뛰어난 배우이거나 많은 작품을 출연했기 때문이 아니라 그 어떤 배우를 대상으로 하여도 비슷한 결과가 나온다고 한다. (이 사이트에 의하면 평균을 취했을 때 가장 평균 거리가 짧은 배우는 Harvey Keitel이라고 한다)
Mathmetical Approach - Regular Network
자 이게 과연 정말 뜨악스럽고 놀랄만한 일일까? 정말 간단한 수학적 모델로 한 번 검증을 시도해보자. 가정을 하나 해보자. 만약 ‘모든 사람’이 아는 사람이 딱 10명 씩 있다고 가정해보자. 뭐 어느 정도는 납득해볼만한 가정이지 않은가? (나중에 얘기하겠지만 틀린 얘기다.) 그렇다면 한 단계 더 건너면 10 * 10 = 100, 또 한 단계를 건너면 10 * 10 * 10 = 100, 그리고 만약 내가 6 step 만큼 건너갔을 때 아는 사람의 숫자는 10^7, 즉 1000만 명의 사람과 연결이 되어있는 것이다. 이것을 보고 정규 네트워크 (regular network) 라고 부르며, 이렇게 문제를 가정하고 생각하면 생각보다 문제가 간단해진다. 이 방법이 에르도쉬가 문제를 풀이한 방법이다. network 내부에서 node와 node가 연결되는 것은 확률의 문제이고, 만약 모든 사람들이 이 확률을 비슷하게 가지고 있다고 가정하면, 위와 같은 정규 네트워크가 나오게 되는 것이다. (구체적으로는 node가 연결되는 숫자가 정규분포로 나오기 때문에 정규 네트워크라고 한다.) 이 네트워크의 모양은 아래와 같다.
근데 정말 세상은 이렇게 구성이 되어있다고 말할 수 있을까? 실제 세상은 과연 정말 정규 네트워크일까? 당연한 얘기지만 그렇지 않다.
Mathmetical Approach - Real Network
일단 정규 네트워크는 가정 자체가 글러먹었다. 모든 사람이 평균적으로 같은 숫자의 친구를 가지고 있다? 안타깝게도 사람마다 친구의 숫자가 천차만별이고, 구체적으로 말하자면 사람마다 가지고 있는 node를 형성할 probability나 node가 형성될 기회의 숫자가 차이가 나기 때문에 차이가 발생하게 된다. 특히 실제 모형의 확률은 정규 분포가 아니라 Power-law distribution이라는 것이 실제 연구를 통해서 밝혀졌으며, 이 분포를 따르게 되면 친구의 숫자가 최대 수백에서 수천배까지도 나게 된다. 따라서 이런 네트워크에서는 connection이 한 지점으로 몰리는 Hub가 존재하는데, 이 사실은 모든 node가 같은 connection을 가진다는 정규 네트워크의 가설과는 매우 다르다.
Power-law distribution은 위의 그림에서 자세히 확인이 가능하다. 또한 이런 분포로 만들어진 네트워크의 모양은 아래 그림과 같다. Hub가 존재한다는 사실을 다시 한 번 생각해보고 그림을 보면 이해가 잘 될 것이다.
이제 이런 경우에 대해서 node당 평균 10개의 connection이 있다고 다시 가정해보자. 비록 평균 connection이 10개가 있더라도, 정규 네트워크와는 다르게, power-law 네트워크는 한 node가 그 connection을 독식할 수도 있다. 즉, 이전에는 10개의 connection을 가진 1000개의 node가 있었다고 해보면, 지금은 그 중 하나의 connection이 모두 한 node에 쏠려 한 node가 1000개의 connection을 가지고 있는 셈이다.
이런 특이한 모양 (topology라고 한다) 때문에 생기는 특성 중 하나로는 확산의 형태가 다르다는 점이다. 정규 네트워크는 네트워크에서 어떤 무언가가 전파되는 데에 (간단하게 전염병이라고 생각해보자) 모두가 같은 connection을 가지고 있으므로 시간이 오래 걸리거나 일정 threshold를 넘지 못하면 전체 네트워크가 전염되지 않지만, Power-law Network에서는 그 threshold가 비교적 매우 작고, 몇 개의 hub만 감염이 되어도 모든 node가 influence될 수 있는 가능성이 엄청나게 커지는 것이다. 이 특성을 특정 hub를 격리하거나 백신을 투여해 전염병의 효율적 예방을 하는 데에 쓸 수도 있고, 마케팅의 측면에서 소비자 행동양식 변화 혹은 물건 구매 등으로 주변에 영향력이 큰 몇 명의 핵심 사용자들에게 무료로 물건을 나누어주거나 후기를 작성하게하는 등의 마케팅도 가능할 것이다.
이렇듯 실제 네트워크에서 발생하는 특성들을 사용하면 재미있는 결과가 나오게 된다. 과연 어떤 특성들이 있으며, 수학적으로 어떻게 증명하거나 접근해야하는지, 그리고 마지막으로 이런 특성들을 어떻게 사용할 것인지에 대해서는 다음 포스팅에서 자세히 다루도록 하겠다.