[Social Network] Community Detection (커뮤니티 탐지)

네트워크의 구조를 보면 아래와 같다.

그림에서 노드가 밀집해 있는 부분을 Network community라 부른다.

 

💡 Network Community란?

 Sets of nodes with lots of connections inside and few to outside 

밖으로는 적게 안으로는 많은 노드들의 집합

 

이러한 Network Communities들을 자동으로 찾아주는 방법이 있을까?

 

🔍 Community Detection (커뮤니티 탐지)

 

Edge betweenness를 통한 탐지

 

각 엣지(링크)를 통과하는 최단 경로의 수

 

아래 엣지들의 색깔로 Edge betweenness 강도를 알 수 있는데,

커뮤니티 안의 노드들끼리의 Edge betweenness가 낮다는 것을 알 수 있다.

 

Girvan-Newman Algorithm

 

• Edge Betweenness를 계산
• Edge Betweenness가 높은 엣지를 제거한다.
• 위 과정을 엣지가 없어질 때까지 계속 반복

 

Girvan-Newman Algorithm을 통해 적절한 시점에 멈추면 적절한 크기의 커뮤니티를 구할 수 있다.

 

그렇다면 여기서 2가지 풀어야할 문제가 생긴다.

1. How to compute betweenness? Edge betweenness은 어떻게 계산될까?

2. How to select the number of clusters?  Girvan-Newman Algorithm을 멈춰야하는 시점은 언제일까?

 

 

 

🔍  How to compute betweenness?

 

(1) 한 노드를 기준으로 BFS 맵을 그려준다.

(2) 노드에서 노드로의 최단경로의 수를 구해준다.

(3) Edge Betweennees를 구해주는 Algorithm을 적용해 구해주자

 

노드마다 node flow를 설정해 node flow를 위의 노드들로 올려주는 형식이다.

기본적으로 노드마다  node flow를 1씩 갖고 있다.

깊이가 제일 큰 노드부터 시작하여 기준이 되는 노드까지 BFS방식으로 flow up해주자

 

•  K는 1의 node flow를 갖고 있기 때문에 위의 두 노드의 최단 경로의 수가 같기 때문에 0.5씩 flow up 해준다.

•  I와 J는 기본으로 갖고 있는 1과 flow up을 당해 받은 0.5를 더한 1.5의 node flow를 갖게 되고,
•  I의 상위 노드의 최단 경로의 수는 F는 2, G는 1이기 때문에 2:1비율로 flow up을 해줘야 한다.

 

• 위 과정을 루트 노드까지 반복을 해주면 된다.

• 위 과정을 모든 노드에서 실행해줘 flow들을 더 해준다.
• 가장 큰 Edge Betweenness를 제거하는 과정을 계속 반복하면 된다.

 

🔍 How to select the number of clusters?

Modularity Q를 구해자

 

Modularity란?

A measure of how well a network is partitioned into communities

네트워크가 얼마나 잘 communities들로 구분되어 있는 정도를 나타내준다.

 

Q는 그룹들 각각의 S의 엣지 수와 예상 되는 엣지 수의 차이의 합으로 구해지며,

Q가 클수록 잘 구분된 Network임을 알 수 있다.

 

 

보통 Q는 -1과 1사이의 수가 나올 것이다.

하지만 가장 적절한 Network Communities들로 이루어지기 위해서는 Q가 0.3~0.7의 값이 나와야 한다.

 

그리고 어느정도 최적의 Q값이 나오며 그 값을 넘어서 계속 clustering을 해주면 Q의 값은 떨어질 것이다.

자료 출처 : cc224w.stanford.edu

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!