다리 역할을 하는 노드
아는 사람이 많지 않아도 두 무리 사이에 서 있는 사람은 중요합니다. 다른 사람들의 최단 경로가 그 노드를 얼마나 자주 지나는지 셉니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 17로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 17매개 중심성
- 1. 관심 주제근접 중심성·평균 거리추가 07 · 새 추가 수업
- 복귀 · DAY 17원래 회차 이어가기
- 근접 중심성·평균 거리 · 16·17회차에서 차수와 매개 중심성을 본 뒤, 프리먼이 정리한 세 번째 중심성인 ‘가까움’을 계산합니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
매개 중심성(betweenness centrality)은 다른 두 노드 사이의 최단 경로 위에 어떤 노드가 얼마나 자주 놓이는지를 셉니다. 프리먼(Freeman, 1977)이 정리한 지표로, 정보·물자·소문이 최단 경로를 따라 흐른다고 볼 때 흐름을 중개하거나 막을 수 있는 위치를 찾아 줍니다.
계산은 쌍 단위로 합니다. 노드 v를 뺀 모든 쌍 (s, t)에 대해, s와 t 사이 최단 경로가 g개이고 그중 v를 지나는 것이 g_v개라면 g_v÷g를 더합니다. 최단 경로가 여러 개면 몫을 나눠 가지는 셈입니다. 무방향 그래프에서 v를 뺀 쌍은 (N−1)(N−2)÷2개이므로 이 값으로 나누면 0~1로 정규화됩니다. 큰 그래프에서는 브란데스(Brandes, 2001)의 방법으로 모든 노드의 값을 한꺼번에 효율적으로 구합니다.
동아리 네트워크에서 하린과 도윤은 차수가 3으로 평범하지만, 두 무리를 잇는 유일한 길목이라 매개 중심성이 12로 가장 높습니다. 무리 끝에 있는 민수와 보라는 어떤 최단 경로의 중간에도 놓이지 않아 0입니다. 이 지표는 조직의 중개자, 교통망의 병목, 끊기면 그래프가 갈라지는 지점을 찾는 데 쓰입니다. 다만 실제 흐름이 늘 최단 경로로만 다닌다는 가정에 기댄 값이라는 점은 기억해야 합니다.
작은 예제로 따라가기
하린을 지나는 쌍은 {민수, 지아, 서준} 중 한 명과 {도윤, 유나, 태오, 보라} 중 한 명을 잇는 3×4=12쌍이고, 이 쌍들의 최단 경로는 모두 하린을 지나므로 하린의 매개 중심성은 12입니다.
지아는 민수에서 하린·도윤·유나·태오·보라로 가는 5쌍에 걸쳐 있는데, 각 쌍의 최단 경로 중 절반만(서준이 아니라 지아를 거치는 쪽) 지아를 지나 5×0.5=2.5입니다.
정규화할 때는 자기 자신을 뺀 7명으로 만들 수 있는 쌍 7×6÷2=21로 나누므로 하린 12÷21≈0.57, 지아 2.5÷21≈0.12, 민수 0입니다.
직접 실험해 보기
하린, 지아, 민수를 차례로 눌러 그 노드를 지나는 최단 경로 쌍 목록과 매개 중심성 값을 확인하고, 경로가 두 갈래라서 0.5씩 나뉘는 쌍을 찾아보세요.
최단 경로가 지나는 노드 찾기
| 이름 | 매개 중심성 | 정규화 ÷21 |
|---|---|---|
| 하린 | 12 | 0.57 |
| 도윤 | 12 | 0.57 |
| 지아 | 2.5 | 0.12 |
| 서준 | 2.5 | 0.12 |
| 유나 | 2.5 | 0.12 |
| 태오 | 2.5 | 0.12 |
| 민수 | 0 | 0.00 |
| 보라 | 0 | 0.00 |
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
다를 뺀 쌍 중 다를 지나는 쌍은 왼쪽 {가, 나}와 오른쪽 {라, 마}에서 하나씩 고른 쌍입니다.
풀이와 비교하기
다를 지나는 쌍은 가–라, 가–마, 나–라, 나–마로 2×2=4쌍이고, 최단 경로가 하나씩뿐이라 매개 중심성은 4입니다. 다를 뺀 쌍은 4×3÷2=6개이므로 정규화 값은 4÷6≈0.67입니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
그래프를 두 조각으로 나누는 다리 엣지의 양 끝 노드는 왜 매개 중심성이 높을까요?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
A Set of Measures of Centrality Based on BetweennessFreeman (1977)A faster algorithm for betweenness centralityBrandes (2001)이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.