여섯 개의 다리가 세상을 작게 만드는 방법

가깝다는 것은 위치뿐 아니라 규칙입니다

출발 그래프에는 노드 예순 개와 방향 없는 간선 예순 개가 있습니다. 각 노드는 원 위의 앞뒤 이웃과 연결됩니다. 그림에서 얼마나 길게 보이든 간선 하나의 비용은 한 홉입니다. 이동 시간이나 교통량, 물리적 거리가 이 규칙 안에 숨어 있지는 않습니다. 의도적으로 작게 만든 모델입니다.

두 노드 사이에서는 원을 양쪽 방향으로 돌 수 있고 더 짧은 쪽을 고릅니다. 서로 반대인 노드는 어느 쪽으로 가도 서른 홉이 필요하고 이웃은 한 홉이면 됩니다. 보기 좋은 사례 하나만 고르기는 쉬우므로 서로 다른 노드의 순서 없는 조합 1,770쌍 전체에 대해 최단 경로를 계산했습니다.

다리 끝에서 먼 곳도 혜택을 받습니다

새 간선은 노드 0–30, 5–35, 10–40, 15–45, 20–50, 25–55를 연결합니다. 번호는 가상 원 위의 위치이며 실제 장소가 아닙니다. 간선은 총 예순여섯 개가 됩니다. 기존 연결을 남겨 둔다는 점이 중요합니다. 원래 길을 버리도록 강요하는 것이 아니라 선택지를 추가합니다.

원 위를 따라 다리까지 간 다음 건너서 목적지로 갈 수 있습니다. 그래서 다리는 양 끝 노드에만 도움이 되지 않습니다. 다른 곳에 있는 많은 노드 쌍의 경로도 바꿉니다. 여섯 연결은 사람이 지정했으며 가능한 모든 배치 중 최적이라고 증명한 결과는 아닙니다.

평균 이동이 일곱 홉 줄었습니다

연결을 추가하기 전 1,770쌍의 평균 최단 거리는 약 15.254홉이었습니다. 이후에는 약 8.254홉입니다. 이 그래프에서 차이는 정확히 일곱 홉입니다. 모든 쌍의 최단 거리 중 최댓값인 지름은 서른에서 열다섯으로 줄었습니다. 평균 쌍과 가장 멀리 떨어진 쌍은 서로 다른 요약입니다.

어떤 쌍은 크게 개선되고 어떤 쌍은 적게 바뀌며 이웃 노드는 여전히 한 홉입니다. 평균값이 모두에게 같은 절약을 약속하지는 않습니다. 거리 분포를 함께 보면 어떤 길이가 흔해지거나 드물어졌는지 알 수 있어 변화 전체를 하나의 숫자로 압축하지 않게 됩니다.

예전 길은 사라지지 않았습니다

비용이 고정된 이 비가중 그래프에서는 간선을 추가해도 어떤 쌍의 최단 거리가 늘지 않습니다. 예전 최선의 경로가 그대로 있고 더 나은 경로가 생길 수 있기 때문입니다. 확인 과정은 평균만 보지 않고 모든 쌍의 거리를 전후 비교합니다. 두 그래프의 연결성과 정확히 여섯 간선이 추가됐다는 점도 검사했습니다.

이 보장은 모델에 달려 있습니다. 현실에서는 도로가 열리면 운전자가 선택을 바꾸고 혼잡이 이동 시간을 바꿀 수 있습니다. 통신 연결에는 용량과 지연이 있습니다. 여기서는 어느 것도 모델링하지 않았습니다. 고정 비용의 가능한 경로에 관한 결과이지 모든 새 도로가 현실 시스템을 개선한다는 보장은 아닙니다.

별도 고장 시험은 비용 1인 지름길 여섯 개를 하나씩 차례로 제거합니다. 고리 전체가 남아 있어 노드 60개는 모두 연결됩니다. 평균은 8.2542에서 8.3955홉으로 늘지만 여섯 경우 모두 지름은 15입니다. 같은 결과는 이 배치의 회전 대칭성 때문이지 중복 네트워크의 보편 법칙이 아닙니다. 여기서 다리는 지름길의 시각적 이름입니다. 그래프 이론의 다리는 제거하면 그래프를 끊는 간선을 뜻하며 추가된 간선들은 그 정의에 해당하지 않습니다.

긴 선의 실제 비용은 그림만으로 알 수 없습니다

여섯 다리는 원 전체를 가로질러도 한 홉으로 계산됩니다. 이 가정이 이익의 큰 부분을 만듭니다. 원의 이웃으로 가는 데 일 분, 다리를 건너는 데 이십 분이 든다면 시간 기준 계산은 다른 이야기가 됩니다. 우리는 선의 길이를 수고로 받아들이기 쉬워 네트워크 그림에서 이 선택을 놓칠 수 있습니다.

문서 링크, 소프트웨어 구성 요소, 교통역 사이의 연결을 생각할 때도 같은 구분이 유용합니다. 최단 경로를 묻기 전에 간선이 무엇이고 비용이 무엇을 뜻하는지 정해야 합니다. 클릭 수, 환승 수, 경과 시간은 다른 목표입니다. 가장 보기 좋은 선이 목표까지 정해 주지는 않습니다.

종이에서 짧은 연결이 그래프에서는 비쌀 수 있습니다

확장 실험은 고리 간선 비용을 1로 두고 모든 지름길 비용을 각각 1, 5, 15, 30, 35로 설정한 다섯 시나리오를 만듭니다. 기존 평균 홉에 가격을 곱하지 않고 1,770쌍의 가중 최단 경로를 다시 계산합니다. 평균 비용은 약 8.2542, 10.0847, 13.4746, 15.2542, 15.2542입니다. 그림이 같아도 횡단 비용이 커지면 이점이 줄어듭니다. 간선 수가 적은 길이 더 비쌀 수 있습니다.

비용 30에서는 각 지름길이 반대편 끝점 사이의 고리 30간선 경로와 같습니다. 지름길을 쓰는 길은 비용을 늘리지 않고 그 구간을 고리로 바꿀 수 있습니다. 스크립트는 평균뿐 아니라 모든 쌍이 고리만의 최소 비용으로 돌아옴을 확인합니다. 35로 올려도 대체 고리가 더 싸므로 도움이 되지 않습니다. 경로 모형에서는 새 연결 비용이 기존 경로와 비교해 어떤지라는 손익 경계를 물어볼 수 있습니다. 원을 가르는 인상적인 선이 아니라 간선 가중치가 답을 정합니다.

지름길의 예제이지 모두의 이론은 아닙니다

이 원은 현실 사람들이 몇 명의 지인을 사이에 두고 연결되는지에 관한 증거도, 인터넷 성능 측정도 아닙니다. 실제 네트워크에는 방향성, 중요도 차이, 바뀌는 가용성, 매우 불균등한 연결 수가 있습니다. 작은 세상에 관한 논의는 이런 예제로 시작할 수 있지만 가상의 점 예순 개를 사회 조사로 취급해서는 안 됩니다.

얻을 수 있는 것은 명확한 사고 습관입니다. 전체 네트워크를 세고 비용 가정을 드러내며 평균 개선과 개인별 개선을 구분합니다. 더 큰 주장 없이도 충분히 놀랍습니다. 노드는 움직이지 않았는데 여섯 연결이 수백 쌍 사이의 경로를 바꿨습니다.