[지식그래프] #6. 지식그래프와 커뮤니티 탐지

지난 글에 이어 이번에는 커뮤니티 탐지에 대해서 다루어보고자 한다. 사실 #5. 지식그래프와 네트워크 분석 과 이번 글은 네트워크 분석에 가까운 내용이긴 하다. 지난 글에서는 네트워크 내의 중심성 계산을 통해 어떠한 노드가 중요한 역할을 하는지 찾았다. 이런 분석은 작은 규모의 네트워크에서 시행하기에 적합하다. 이보다 규모다 좀 더 큰 네트워크에서는 커뮤니티 감지를 통해 노드 그룹간의 관계를 찾고 분석을 수행할 수 있다.

자료를 찾아 살펴보다 보면 "클러스터", "커뮤니티", "클러스터링"을 혼용하는 경우도 찾아 볼 수 있다. 따라서 용어에 대한 정의부터 먼저 시작하면, 컴퓨터 과학과 네트워크 과학 분야에서 사용하는 용어의 의미가 약간 다르다. 컴퓨터 과학에서는 "커뮤니티"를 "클러스터"라고 하고 커뮤니티 감지를 "클러스터링"이라고 한다.

반면에 네트워크 과학에서는 연결 전이성 측정을 "클러스터링"이라고 한다. 이때 연결 전이성(Transitivity)는 a->b 이고 b->c이면, a->c가 되는 성질을 말한다. 이런 전이성을 통해 얼마나 노드들이 뭉쳐 있는지를 측정하는데 이를 결집계수라고 한다.

그리고 네트워크 과학에서 (상호 연관되어) 뭉쳐진 노드 그룹을 "커뮤니티"라고 한다. 

 

커뮤니티 탐지는 크게 두 가지 유형이 있다. 응집을 통해 커뮤니티를 찾는 방법과 전체 네트워크에서 어떤 조건에 따라 분할하여 커뮤니티를 찾는 방법이 있다. 이 두가지 유형을 기반으로 다양한 방식의 알고리즘이 존재한다.

아래의 링크는 다양한 커뮤니티 탐지 알고리즘을 비교할 수 있도록 구성한 페이지이다.

사용하는 데이터는 지난 글에서 중심성 분석을 위해 사용한 데이터를 그대로 사용했으며, 커뮤니티 알고리즘만 변경하여 적용한 내용이다.

 

https://joyhong85.github.io/network/community.html

Centrality