The Expected Number of Pairwise Stable Networks

거대한 방 안에 사람들이 가득 차 있다고 상상해 보세요. 방 안의 모든 사람은 잠재적으로 누구와도 악수를 할 수 있습니다. 여기서 "네트워크"란 특정 순간에 실제로 일어난 모든 악수의 집합을 의미합니다.

이제, 방 안의 모든 사람이 각자 비밀스럽고 무작위적인 점수표를 가지고 있다고 상상해 봅시다. 이 점수표는 현재의 악수 패턴에 대해 그 사람이 얼마나 만족하는지를 알려줍니다. 때때로 어떤 사람은 "밥(Bob)과 악수하는 것을 그만두면 더 행복할 텐데"라고 생각할 수도 있습니다. 또 다른 때는 "앨리스(Alice)와 악수를 시작하고 싶고, 앨리스도 동의한다면 더 행복할 텐데"라고 생각할 수도 있습니다.

이 논문은 아주 중요한 질문을 던집니다: 만약 모든 사람의 행복도가 완전히 무작리적이라면, 얼마나 많은 서로 다른 악수 패턴이 "안정적(stable)"인 상태로 남게 될까요?

하나의 패턴이 "안정적"이라는 것은, 아무도 관계를 끊고 싶어 하지 않고, 동시에 어떤 두 사람도 새로운 관계를 시작하고 싶어 하지 않는 상태를 말합니다. 저자들은 이를 **쌍방 안정성(Pairwise Stability)**이라고 부릅니다.

이 논문이 발견한 내용을 쉬운 개념들로 나누어 설명하겠습니다.

1. "빈 방" vs "모쉬 피트(Mosh Pit)"

저자들은 안정성에 관한 재미있는 규칙을 발견했습니다: 악수가 많아질수록, 안정적인 상태를 유지하기가 더 어려워집니다.

춤추는 무대를 생각해 보세요.

• 빈 네트워크 (The Empty Network): 아무도 악수를 하지 않는다면, 안정적인 상태를 유지하기가 매우 쉽습니다. 아무도 관계를 맺고 있지 않기에 끊을 것도 없고, 사람들이 무작위로 행복한 상태라면 두 사람이 새로운 관계를 시작하도록 설득하기도 어렵습니다.
• 완전한 네트워크 (The Complete Network): 모든 사람이 서로 악수를 하고 있다면, 그것은 혼돈 그 자체입니다. 적어도 한 명의 사람이 파트너를 놓아주고 싶어 하거나, 두 사람이 파트너를 바꾸고 싶어 할 가능성이 매우 높습니다.

이 논문은 수학적으로 증명합니다. 즉, 연결(악수)이 추가될수록 전체 집단이 안정적일 확률은 떨어집니다. "빈 방"이 가장 안정적이기 쉽고, "모쉬 피트"가 가장 안정적이기 어렵습니다.

2. "연차 점수 (Seniority Score)"

평균적인 안정적 그룹의 수를 계산하기 위해, 저자들은 **"연차 차수(Seniority Degrees)"**라고 부르는 영리한 점수 체계를 고안했습니다.

사람들이 나이(또는 ID 번호) 순서대로 줄을 서 있다고 상상해 봅시다.

• 만약 당신이 자신보다 나이가 많은 사람과 악수를 하고 있다면, 당신은 1점을 얻습니다.
• 만약 당신이 자신보다 나이가 어린 사람과 악수를 하고 있지 않다면, 당신은 1점을 얻습니다.
• 또한, 단순히 존재한다는 사실만으로도 보너스 점수 1점을 받습니다.

전체 네트워크의 "연차 점수"는 모든 사람의 점수를 곱한 값입니다. 기대되는 안정적 네트워크의 수는 단순히 모든 가능한 네트워크에 대한 이 점수들의 "역수"를 합산한 것과 같습니다.

함정: 인원이 적을 때(예: 7명)는 2억 6,800만 개가 넘는 가능한 악수 패턴이 존재합니다. 모든 패턴에 대해 이 점수를 계산하는 것은 해변의 모래알 하나하나를 손으로 세는 것과 같습니다. 규모가 커지면 이는 불가능합니다.

3. "마법의 경계 (Magic Bounds)"

모래알을 일일이 셀 수 없었기에, 저자들은 정답 주변에 울타리를 쳤습니다. 그들은 하한선(Lower Bound)(우리가 기대할 수 있는 최소한의 안정적 네트워크 수)과 상한선(Upper Bound)(최대한의 안정적 네트워크 수)을 만들었습니다.

그들은 집단의 규모가 거대해짐에 따라, 안정적 네트워크의 수가 믿기 힘들 정도로 빠르게 증가한다는 것을 발견했습니다.

• 성장: 인구가 늘어남에 따라 안정적 네트워크의 수는 무한대로 폭발하며 증가합니다.
• 역설: 안정적 네트워크의 숫자 자체는 엄청나게 크지만, 전체 가능한 네트워크 중 안정적인 네트워크가 차지하는 비율은 아주 미미합니다.

비유: 도서관에 10억 권의 책이 있다고 상상해 보세요. 저자들은 그 안에 수백만 권의 "좋은" 책(안정적 네트워크)이 있다는 것을 발견했습니다. 하지만 도서관 전체에 조 단위의 책이 있기 때문에, "좋은" 책은 여전히 거대한 바다에 떨어진 아주 작은 한 방울에 불과합니다.

4. "해밍 거리 (Hamming Distance)" (파급 효과)

논문은 또한 두 개의 서로 다른 안정적 네트워크가 서로 어떤 관계를 갖는지 살펴보았습니다. 그들은 **해밍 거리(Hamming Distance)**라는 개념을 사용했는데, 이는 단순히 두 그룹 사이에서 서로 다른 악수가 몇 개인지를 세는 방식입니다.

• 거리 1: 두 네트워크가 단 하나의 악수 차이만 난다면, 그 둘은 동시에 안정적일 수 없습니다. 마치 두 사람이 하나의 의자에 서려고 하는 것과 같아서, 한 명만 앉을 수 있습니다.
• 거리 2: 두 네트워크가 두 개의 악수 차이를 보인다면, 서로 약간 "연결"되어 있습니다. 하나가 안정적이라면, 다른 하나도 안정적일 가능성이 약간 높아집니다.
• 거리 3 이상: 두 네트워크가 세 개 이상의 악수 차이를 보인다면, 그들은 완전히 독립적입니다. 한 네트워크가 안정적이라는 사실이 다른 네트워크에 대해 아무런 정보도 주지 않습니다.

집단의 규모가 거대해질수록, 거의 모든 쌍의 네트워크는 멀리 떨어져 있습니다(거리 3 이상). 이는 "노이즈"가 상쇄된다는 것을 의미하며, 수학적 계산이 매우 예측 가능해진다는 뜻입니다.

최종 결론

논문은 인구가 매우 많아질 때 일어나는 두 가지 놀라운 사실로 결론을 맺습니다.

1. 안정성은 풍부하다: 당신은 거의 확실하게 많은 안정적 네트워크를 발견하게 될 것입니다. 이것은 드문 사건이 아닙니다. 수천, 수만 개의 안정적 네트워크가 존재한다는 것은 보장된 사실입니다.
2. 안정성은 희귀하다: 그 숫자가 수백만 개라 할지라도, 그것은 가능한 모든 연결 방식 중에서는 아주 미세한 부분에 불과합니다.

요약하자면: 무작위적인 행복이 지배하는 세상에서도, 사람들이 머물기에 충분히 행복한 배치(arrangement)는 거의 항상 존재합니다. 하지만 "완벽한" 배치를 찾는 것은, 비록 그 건초더미 안에 10억 개의 바늘이 들어있을지라도, 건초더미 속에서 바늘을 찾는 것만큼이나 어려운 일입니다. 이 논문은 그 바늘들을 세는 수학적 방법을 제시하며, 그 바늘들이 어디에나 존재하면서도 동시에 얼마나 희귀한지를 증명합니다.