네트워크 데이터 분석 - Communities

목차

이번 포스트에서는 네트워크의 특징중 하나인 커뮤니티 구조 (community structure)에 대해 다뤄보겠습니다.

1. What is it?

현실 네트워크의 노드들은 무작위로 연결되어 있지 않습니다. 지난 포스트에서 다뤘듯이 노드들은 주로 같은 특징을 갖는 노드와 연결되는 특징 (assortativity)  이 있습니다.

네트워크 데이터 분석 - 현실 네트워크의 특징들

같은 특징을 갖는 노드끼리 연결 되면 자연스럽게 노드들의 클러스터 (cluster) 또는 그룹이 생성됩니다. 이러한 구조를 community structure 라고 합니다. Community는 다양한 방식으로 정의 될 수 있는데, 가장 대표적인 정의는 tight하게 연결된 subnetwork 라는 것입니다. 그리고 커뮤니티 밖으로 연결된 edge의 수가 상대적으로 적어야 합니다.

3개의 커뮤니티

가장 쉽게 볼 수 있는 커뮤니티 구조는 X(트위터)나 페이스북에 있는 정치 성향이 강한 계정들입니다. 보통 정치 성향이 같은 계정끼리 팔로우 관계를 맺으며, 다른 정치 성향을 가지고 있는 계정과는 팔로우 관계를 거의 맺지 않죠. 이외에도 웹페이지를 보면 같은 주제를 가진 페이지들이 하이퍼링크로 연결되어서 커뮤니티를 형성하는 것을 볼 수 있습니다.

네트워크 분석에 있어서 커뮤니티 구조를 파악하는 것이 중요한 이유는 네트워크의 구조를 볼 수 있고, 같은 특징을 가진 노드들을 특정할 수 있기 때문입니다. 또한 클러스터 안에서의 노드의 위치에 따라 노드를 분류할 수도 있습니다. 예를 들어, 다른 커뮤니티와 연결된 노드와 그렇지 않은 노드를 분류할 수 있겠죠.

2. Related definitions

이제 커뮤니티 구조와 관련된 몇 가지 개념과 정의들에 대해 다뤄보겠습니다.

2 - 1. Variables

• Internal degree of a node: 같은 커뮤니티에 속하는 이웃 (neighbor)의 수
• External degree of a node: 커뮤니티 밖에 속하는 이웃 (neighbor)의 수
• Internal link density: 커뮤니티 안에 들어있는 edge의 수와 커뮤니티 내에서 최대로 존재할 수 있는 edge의 수의 비율로 다음과 같습니다.
  $$\delta_{C}^{int} = \frac{L_{C}}{L_{C}^{max}} = \frac{L_{C}}{\binom{N_{C}}{2}} = \frac{2L_{C}}{N_{C}(N_{C} - 1)}$$
  여기서 $N_{C}$는 커뮤니티 $C$에 속하는 노드의 수이며, $L_{C}$는 커뮤니티 $C$에 속하는 edge의 수, 그리고 $L_{C}^{max}$는 커뮤니티 내에서 최대로 존재할 수 있는 edge의 수 입니다.

2 - 2. Cohesion and separation

다음은 커뮤니티가 만족해야할 속성들입니다.

• Cohesion: 커뮤니티 내부를 연결하는 edge가 많아서 노들이 조밀해야 함
• Separation: 커뮤니티들 사이는 적은 수의 edge들로 연결 되어야 함

따라서 커뮤니티란 high cohesion과 high separation을 만족해야 합니다.

2 - 3. Community의 정의들

커뮤니티를 정의 하는 가장 간단한 방법은 커뮤니티 내부의 edge의 수가 커뮤니티 외부를 연결하는 edge의 수를 비교하는 것입니다. 그러면 다음과 같은 두 가지의 커뮤니티를 정의할 수 있습니다.

• Strong community: Subnetwork의 각 노드의 internal degree가 external degree 보다 큼.
• Weak community: Subnetwork의 각 노드의 internal degree의 합이 각 노드의 external degree의 합보다 큼.

각 노드의 internal degree가 external degree보다 크면 internal degree의 합이 external degree보다 크기 때문에, 자연스럽게 strong community는 weak community이기도 합니다. 하지만 그 반대는 성립하지 않습니다.

위의 정의들에서는 subnetwork (community) 와 그 외 네트워크의 다른 부분을 비교한다는 문제점이 있습니다. 이보다는 subnetwork끼리 서로 비교 하는 것이 더 자연스러운 정의가 될 수 있습니다. 이를 덜 엄격한 (less stringent) 정의라고 하는데, 다음과 같습니다.

• Strong community: Subnetwork의 각 노드의 internal degree가 다른 커뮤니티에 있는 이웃의 수보다 큼.
• Weak community: Subnetwork의 각 노드의 internal degree의 합이 다른 커뮤니티에 있는 이웃의 합보다 큼.

3. 현실 communities의 특징

• 현실에 있는 네트워크의 community들은 겹치는 경우 (overlap) 가 많습니다. 이렇게 네트워크를 서로 겹치는 형태의 community로 나누는 것을 cover 라고 합니다. 네트워크에서 만들어질 수 있는 cover의 경우의 수는 partition (community가 겹치지 않게 나누는 것) 보다 월등히 많기 때문에 분석이 어렵습니다.

Cover. 파란 노드들이 overlap 된다

• Community 사이에는 위계 구조가 존재할 수 있습니다. 예를 들어, 학교의 한 반이 커뮤니티가 되며, 반들이 모여 학년 이라는 커뮤니티가 생성됩니다. 모든 위계의 커뮤니티가 의미를 갖기 때문에 좋은 clustering 알고리즘은 이러한 모든 형태의 커뮤니티를 찾아낼 수 있어야 합니다.