군집을 찾는 알고리즘1 - Girvan-Newman algorithm

1. idea 군집을 찾는 대표적인 하향식 알고리즘으로 전체 그래프에서 시작하여 군집들이 서로 분리되도록 link를 순차적으로 제거함 서로 다른 군집을 연결하는 다리 역할을 하는 link를 먼저 제거해나가야 군집들이 분리 될 것이다.   2. betweenness centrality 그래프의 임의의 두 node의 최단 경로 위에 특정 link가 몇번이나 놓이는지 계산    link A-B는 양 옆 4개의 node중 하나를 선택하여 만든 최단 경로에 모두 존재해야하므로 4*4=16가지가 있다. 따라서 그림을 보면 직관적으로 betweenness centrality가 높은 link는 두 군집을 연결하는 다리 역할을 할 가능성이 높다.   3. algorithm 주어진 그래프에서 모든 link의 매개 중심성을..