좁은 세상(Small world)

1960년대에 미국의 사회심리학자 스탠리 밀그램은 미국 중부 사람들에게 보스턴에 사는 낯선 사람에게 편지를 전해 달라고 부탁했습니다. 조건은 그 사람을 알 것 같은 지인에게만 건네는 것이었습니다. 편지 대부분은 도중에 끊겼지만, 도착한 편지들은 평균 대여섯 사람을 거쳤습니다. 여기서 '여섯 단계 분리'라는 말이 퍼졌습니다. 친구는 대부분 같은 동네, 같은 학교 안에서 사귀는데 세상은 어떻게 이렇게 좁을까요?

1998년 미국 코넬 대학교의 대학원생 덩컨 와츠와 그의 지도교수인 수학자 스티븐 스트로가츠는 간단한 모형으로 답했습니다. 원 위의 n = 100개 점을 양옆으로 가까운 이웃과 이어(한 점당 이웃 k개) 고리 모양의 그래프를 만들고, 각 변을 확률⁠(probability)⁠ p로 끊어 무작위로 고른 다른 점에 다시 잇습니다. 그리고 두 가지를 잽니다. 평균 경로 길이⁠(average path length)⁠ $L$은 무작위로 고른 두 점 사이 최단 경로⁠(shortest path)⁠ 길이의 기댓값⁠(expected value)⁠입니다. 뭉침 계수⁠(clustering coefficient)⁠ $C$는 한 점의 두 친구가 서로도 친구일 확률(이웃 쌍 가운데 이어진 쌍의 비율)을 모든 점에 대해 평균 낸 것입니다.

다시 잇는 확률을 $\log_{10} p =$ , 곧 p = 바꿔 보세요. 이웃 수는 k = 입니다. 다시 뽑기 분홍 변이 다시 이어진 지름길이고, 노란 길은 0번 점과 정반대편 50번 점 사이의 최단 경로(걸음)입니다.

지금 $L =$ (p = 0일 때의 배), $C =$ (처음의 배)입니다. p = 0.03 근처($\log_{10} p \approx -1.5$)를 보세요. 변을 3%만 다시 이었는데 평균적으로 L은 절반 남짓으로 줄고 C는 10%도 줄지 않습니다. 지름길 하나는 수많은 쌍의 거리를 한꺼번에 줄이지만, 뭉침은 그 지름길이 끊은 몇 개의 삼각형만큼만 줄기 때문입니다. 오른쪽 그래프는 와츠와 스트로가츠의 그림을 작게 되풀이한 것으로, 각 p마다 무작위 그래프⁠(random graph)⁠ 여럿의 평균입니다(큰 수의 법칙⁠(law of large numbers)⁠).

왜 이렇게 짧을까요? 무작위로 이어진 연결망에서는 한 걸음이면 k명, 두 걸음이면 대략 $k^2$명, r걸음이면 $k^r$명에게 닿습니다. 닿는 사람이 지수함수⁠(exponential function)⁠처럼 불어나므로, n명 모두에 닿는 데는 $k^r = n$, 곧 $r = \ln n / \ln k$걸음이면 됩니다. 거리가 크기의 로그로만 자라는 것입니다. 80억 명이 한 사람당 100명씩 안다고 하면 $\ln(8\times10^9)/\ln 100 \approx 5$걸음입니다(겹치는 친구를 무시한 아주 거친 어림입니다).

이어지는 곳. 와츠와 스트로가츠는 영화배우들의 공동 출연 관계, 미국 서부의 전력망, 예쁜꼬마선충(몸길이 1mm쯤 되는 벌레로, 신경세포 302개의 연결이 모두 밝혀진 동물)의 신경망⁠(neural network)⁠이 모두 이런 '뭉쳐 있으면서도 좁은' 구조임을 보였습니다. 웹 페이지의 링크망도 몇 번의 클릭으로 멀리 닿는 좁은 세상입니다. 그 링크를 따라 무작위로 걷는 사람이 각 페이지에 머무는 비율이 페이지랭크⁠(PageRank)⁠입니다.