그래프 중심성(연결정도·근접·매개) 계산기

묻는 것이 다릅니다. 연결정도는 «이웃이 몇인가»(발이 넓은가), 근접은 «남들까지 얼마나 가까운가»(소식이 빨리 닿는가), 매개는 «남들의 최단경로가 나를 얼마나 지나는가»(길목인가)입니다. 소문을 퍼뜨리려면 연결정도가 큰 점에, 빨리 알려면 근접이 큰 점에, 흐름을 끊으려면 매개가 큰 점을 노립니다.

두 덩어리를 잇는 유일한 통로라면 그렇습니다. 그 점을 지나지 않고는 한쪽에서 다른 쪽으로 갈 수 없으므로 두 덩어리 사이의 모든 최단경로가 그를 지납니다. 조직에서 두 팀을 잇는 한 사람, 망에서 두 지역을 잇는 라우터가 이런 자리이며, 끊기면 그래프가 조각납니다. 이 계산기의 기본 예제가 바로 그 모양입니다.

브랜디스 알고리즘(2001)을 씁니다. 정의대로 모든 점쌍의 최단경로를 열거하면 경로 수가 폭발해 감당이 안 되므로, 출발점마다 BFS로 한 번 훑으며 최단경로 수 σ를 세고 되돌아 나오며 의존도 δ를 누적해 O(VE)에 끝냅니다. 최단경로가 여러 갈래면 각 갈래가 1/(경로 수)씩 몫을 나눠 갖습니다.

닿을 수 없는 점까지의 거리가 무한이라 그냥 더하면 발산합니다. 이 계산기는 두 가지로 다룹니다. «근접» 열은 자기가 닿을 수 있는 범위 안에서 재고 «전체 중 몇 명에게 닿는가»를 곱해 깎은 값(바서만–파우스트 보정)이고, «조화» 열은 거리의 역수를 더한 값이라 닿지 않으면 0을 더해 자연스럽게 정의됩니다. 이어진 그래프에서는 보정한 근접이 흔한 정의와 정확히 같습니다.

모두가 서로 직접 이어져 있어 남을 거쳐 갈 일이 없기 때문입니다. 반대로 별 모양에서는 가운데 점의 매개가 1이 되어 최댓값을 찍습니다. 매개 중심성은 «다른 길이 없는 정도»를 재는 셈이라 그래프가 촘촘할수록 모두 낮아집니다.

페이지랭크는 «중요한 이웃을 둔 점이 중요하다»는 고유벡터 계열이라 발상 자체가 다릅니다. 여기서 다루는 셋은 이웃 수와 최단경로만 보는 반면, 페이지랭크는 이웃의 점수까지 되먹임으로 반영합니다. 같은 그래프에서 전혀 다른 순위가 나올 수 있습니다.

되지 않습니다. 이 계산기는 방향과 가중치가 없는 그래프만 다룹니다. 거리에 가중치가 있으면 BFS 대신 다익스트라로 최단경로를 세야 하고, 방향이 있으면 매개 중심성의 정규화 상수도 달라집니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 적은 변 목록은 이 기기에만 남습니다.