Girvan-Newman 알고리즘 썸네일형 리스트형 [그래프] 5-2. 군집 구조 : 군집 탐색 알고리즘 1. Girvan-Newman 알고리즘 1. 개념 설명 대표적인 하향식(Top-down) 군집 탐색 알고리즘 = 전체 그래프에서 탐색을 시작함. 즉, 군집들이 서로 분리되도록 간선을 순차적으로 제거함 어떤 간선을 제거해야 하나? → 서로 다른 군집을 연결하는 다리(Bridge) 역할의 간선 아래 예시에서 빨간 선을 따라 간선을 제거한다고 생각해보면 → 각각의 군집들이 다른 요소가 되어 떨어져 나옴을 상상할 수 있음 그럼 다리 역할의 간선을 어떻게 찾아낼 수 있을까? 간선의 매개 중심성(Between Centrality)을 사용함. 매개 중심성은 정점간의 최단 경로에 놓이는 횟수를 의미함 정점 i 로부터 j로의 최단 경로를 $\sigma_{i, j}$ 그중 간선 (x, y)를 포함한 것을 $\sigma_{.. 더보기 이전 1 다음
