기르반-뉴먼 알고리즘

Girvan-Newman 알고리즘(Michelle Girvan과 Mark Newman의 이름을 따서 명명)은 복잡한 시스템의 커뮤니티를 탐지하는 데 사용되는 계층적 방법이다.^[1]

에지 간극 및 커뮤니티 구조

Girvan-Newman 알고리즘은 원래 네트워크에서 점진적으로 가장자리를 제거하여 커뮤니티를 탐지한다.나머지 네트워크의 연결된 구성요소는 공동체다.Girvan-Newman 알고리즘은 어떤 가장자리가 커뮤니티에 가장 중심적인지를 알려주는 측정치를 구성하려고 하는 대신, 가장 가능성이 높은 "사이" 커뮤니티에 초점을 맞춘다.

정점 간격은 네트워크에서 매우 중심적인 노드를 나타내는 지표다.모든 노드 $i{\displaystyle }$ ${\displaystyle i$에 대해 정점 간격은 이를 통해 실행되는 노드 쌍 사이의 최단 경로 비율로 정의된다.그것은 네트워크가 알려진 시작점과 끝점 사이의 재화의 이전을 변조하는 모델과 관련이 있는데, 그러한 이전이 이용 가능한 최단 경로를 추구한다는 가정 하에이다.

Girvan-Newman 알고리즘은 에지의 경우까지 이 정의를 확장하여 에지의 "에지 간극"을 에지를 따라 실행되는 노드 쌍 사이의 최단 경로 수로 정의한다.한 쌍의 노드 사이에 둘 이상의 최단 경로가 있는 경우, 모든 경로의 총 중량이 통일과 같도록 각 경로에 동일한 중량이 할당된다.네트워크가 몇 개의 그룹 간 가장자리로만 느슨하게 연결되는 공동체나 그룹을 포함하는 경우, 다른 공동체들 사이의 모든 최단 경로는 이 몇 개의 가장자리 중 하나를 따라 가야 한다.따라서 커뮤니티를 연결하는 가장자리는 높은 에지 간극을 가질 것이다(적어도 그 중 하나).이러한 가장자리를 제거함으로써, 그룹들은 서로 분리되어 네트워크의 기초적인 공동체 구조가 드러난다.

커뮤니티 탐지를 위한 알고리즘의 단계는 아래에 요약되어 있다.

1. 네트워크에 존재하는 모든 에지의 간격이 먼저 계산된다.
2. 간격이 가장 높은 가장자리가 제거된다.
3. 제거에 영향을 받는 모든 가장자리의 간격이 다시 계산된다.
4. 2단계와 3단계를 가장자리가 남아 있지 않을 때까지 반복한다.

다시 계산되는 간격이 제거의 영향을 받는 간극뿐이라는 사실은 컴퓨터의 프로세스 시뮬레이션 실행 시간을 줄일 수 있다.그러나 간격 중심성은 각 단계에서 다시 계산해야 하며 그렇지 않으면 심각한 오류가 발생한다.그 이유는 네트워크가 가장자리 제거 후 설정된 새로운 조건에 적응하기 때문이다.예를 들어, 두 개의 공동체가 둘 이상의 가장자리로 연결되어 있다면, 이러한 가장자리의 간격이 모두 높다는 보장은 없다.방법대로라면 적어도 그 중 한 명은 가질 것으로 알고 있지만 그 이상은 알려진 바가 없다.각 가장자리 제거 후 중간값을 재계산함으로써, 두 공동체 사이에 남아 있는 가장자리 중 적어도 하나는 항상 높은 가치를 가질 것을 보장한다.

Girvan-Newman 알고리즘의 최종 결과는 덴드로그램이다.Girvan-Newman 알고리즘이 실행될 때, 덴드로그램은 위에서 아래로 생성된다(즉, 연이은 링크 제거로 네트워크가 다른 커뮤니티로 분할된다).덴드로그램의 잎은 개별 노드들이다.

참고 항목

• 친밀감
• 계층적 군집화
• 모듈성

참조