Skypainter
목차
지난 포스트에서는 community structure가 무엇인지, 그리고 관련 정의들과 특징에 대해 다뤘다면, 이번 포스트에서는 community structure와 관련된 문제인 network partitioning과 hierchical clustering에 대해 다뤄보겠습니다.
Community structure에 대해 알고 싶다면 아래의 링크를 참고해 주세요.
네트워크 데이터 분석 - Communities
목차 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스이번 포스트에서는 네트워크의 특징중 하나인 커뮤니티 구조 (community structure)에 대해 다뤄보겠습니다.1. What is it?현실 네트워크의 노드들
sanghn.tistory.com
1. Network partitioning
1 - 1. Problem
Network partitioning의 목적은 주어진 그룹들의 크기에 맞게 노드들을 나누되 서로 다른 그룹을 연결 하는 edge의 수를 최소화 하는 것입니다. 이때 서로 다른 그룹을 연결하는 edge의 수를 cut size 라고 합니다.
1 - 2. Network bisection
Network partition의 특수한 경우로, 노드들을 2개의 같은 크기의 그룹으로 나누는 문제입니다. 물론, 여기서도 두 그룹을 연결하는 edge의 수는 최소화 되어야 합니다.
1 - 3. Kernighan - Lin algorithm
Kernighan- Lin algorithm은 network bisection에 사용 되는 대표적인 알고리즘으로, 절차는 다음과 같습니다.
목표: 노드들을 크기가 각각 $N_{A}$, $N_{B}$인 두 그룹 $A$, $B$로 나누되, cut size를 최소화 하기. Network bisection의 경우, $N_{A} = N_{B}$.
- 그룹 $A$와 $B$에 랜덤하게 노드를 할당한다.
- $i \in A$ 하고 $j \in B$인 노드 쌍에 대하여 현재의 cut size와 두 노드의 그룹을 스왑 했을 때의 cut size의 차이를 계산한다.
- 가장 크게 cut size를 감소시키는 노드쌍 $i$, $j$를 선택하고 그룹을 스왑한다. 이제 이 노드쌍은 고정 되며, 이번 iteration이 진행되는 동안 배제된다.
- 더 이상 고정 되지 않은 노드쌍을 스왑할 때 cut size가 감소되지 않을 때까지 2~3을 반복한다. 이는 새로운 bipartition을 생성하며, 이를 시작점으로 다음 iteration을 진행한다.
위의 알고리즘은 cut size가 연속적인 iteration 동안 같을 때 종료됩니다.
Kernighan- Lin algorithm은2개 이상의 클러스터의 cut size를 최소화할 때도 적용될 수 있습니다. 이 경우, cluster 쌍들 (pairs)의 노드들을 스왑하면서 알고리즘이 진행됩니다.
Kernighan- Lin algorithm의 문제점은 초기의 partition에 따라 결과가 많이 달라진다는 점입니다. 첫 partition의 cut size가 클수록 최종 결과가 좋지 않은 경향이 있으며, 알고리즘의 종료까지 소요되는 시간도 길어집니다. 이는 여러 개의 초기 partition을 랜덤하게 생성하여 그중 가장 cut size가 작은 partition을 선택함으로써 어느 정도 문제를 해결할 수 있습니다.
또 다른 문제점은 알고리즘이 greedy하기 때문에 local optima에서 벗어나지 못 할 가능성이 크다는 것입니다. 때때로 cut size를 높이는 swap을 허용함으로써 이 문제를 약화시킬 수는 있습니다.
이러한 이유로 Kernighan - Lin algorithm은 다른 테크닉을 사용하여 얻은 partition을 개선시키는 데에 많이 사용 됩니다.
1 - 4. 코딩 예시
Networkx 패키지를 이용해서 Kernighan - Lin algorithm을 사용해봅시다.
이 포스트에서는 networkx에서 제공하는 Zachary's karate club 이라는 굉장히 유명한 데이터를 사용하겠습니다.
이 네트워크는 원래 하나였던 가라테 클럽이 두 사범의 갈등으로 인해 갈라지게 되면서 형성된 네트워크입니다. 노드는 가라테 클럽의 회원들이며, edge는 클럽 밖에서의 교류를 나타냅니다. 데이터에 대한 더 자세한 내용은 위키피디아를 참고해주세요. (https://en.wikipedia.org/wiki/Zachary%27s_karate_club)
저는 보기 쉽게 노드들을 그룹에 따라 두 가지 색상으로 칠했습니다.
import networkx as nx
K = nx.karate_club_graph()
club_color = {
'Mr. Hi': 'orange',
'Officer': 'lightblue',
}
pos = nx.spring_layout(K, seed=7)
node_colors = [club_color[K.nodes[n]['club']] for n in K.nodes]
nx.draw(K, pos, node_color=node_colors, with_labels=True)
nx.community.kernighan_lin_bisection() 매서드를 사용하면, Kernighan-Lin의 알고리즘에 따라 네트워크가 bisect 됩니다. 그 결과로, 각 그룹에 속한 노드들의 집합을 얻을 수 있습니다.
partition = nx.community.kernighan_lin_bisection(K, seed=2024)
print(partition) ## ({0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21},{32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31})이제 Kernighan-Lin의 bisection 결과에 따라 노드를 칠해보겠습니다.
위의 실제 데이터와 비교해 보면 결과가 상당히 잘 나왔습니다. 8번과 9번 노드를 제외하고는 모두 정확히 clustering 되었는데, 이는 bisection으로 인해 두 그룹의 크기가 똑같아야 한다는 제약이 강제된 결과입니다.
kernighan_node_colors = ['orange' if n in partition[0] else 'lightblue' for n in K.nodes]
nx.draw(K, pos, node_color=kernighan_node_colors, with_labels=True)
1 - 5. Network partitioning의 한계
- Netwrok partitioning은 클러스터들을 잘 나누는 것이 목적이므로, 클러스터가 높은 밀도 (density)를 가질 필요가 없습니다. 따라서, network partitioning 으로 얻은 클러스터들은 보통 community가 아닙니다.
- 클러스터의 개수가 input으로 주어져야 하지만, 보통 사전에 이 정보를 알 수 없습니다.
2. Hierarchical clustering
Hierarchical clustering을 하려면 먼저 '거리 (distance)'가 필요합니다. 두 노드 간의 거리가 얼마나 가까운가에 따라 clustering이 이루어지기 때문입니다. 네트워크의 노드들이 어떤 metric space에 embedded 되어 있는 경우라면, 자연스럽게 거리 개념이 따라오지만, 만약 그러한 공간이 존재하지 않는다면 어떻게 해야할까요?
이럴 때는 similarity measure를 사용합니다.
2 - 1. Similarity of node groups
Similarity measure의 아이디어는 두 노드가 많은 이웃을 공유한다면, 두 노드는 비슷할 것이라는 점에서 출발합니다.
$$S_{ij} = \frac{\# \text{ 노드 } i \text{의 이웃 } \cap \text{노드 } j \text{의 이웃}}{\# \text{ 노드 } i \text{의 이웃} \cup \text{ 노드 } j \text{의 이웃}}$$
만약 노드 $i$와 $j$가 어떠한 이웃도 공유하지 않는다면, $S_{ij}=0$ 이고,
만약 노드 $i$와 $j$의 이웃이 일치한다면, $S_{ij}=1$ 일 것입니다.
그렇다면, 두 그룹 $G_{1}$과 $G_{2}$의 similarity는 어떻게 정의할까요?
방법은 여러 개가 존재합니다. 먼저, $G_{1}$에 속한 노드 $i$와 $G_{2}$에 속한 노드 $j$의 similarity $S_{ij}$를 모두 계산하고, 다음의 likage중 하나를 채택합니다.
- Single linkage: $S_{ij}$의 최댓값, $S_{G_{1}G_{2}} = max_{i \in G_{1}, j \in G_{2}} S_{ij}$
- Complete linkage: $S_{ij}$의 최솟값, $S_{G_{1}G_{2}} = min_{i \in G_{1}, j \in G_{2}} S_{ij}$
- Average linkage: $S_{ij}$의 평균, $S_{G_{1}G_{2}} = \frac{1}{\# \{(i,j): i \in G_{1}, j \in G_{2}\}}\sum_{i \in G_{1}, j \in G_{2}} S_{ij}$
Hierarchical clustering은 처음에 각 노드들을 하나의 클러스터로 보고, 각 스텝마다 similarity가 가장 높은 두 클러스터를 합쳐갑니다.
2 - 2. Dendrograms
Hierarchical clustering의 결과는 dendrogam 으로 표현할 수 있습니다.
$N$개의 클러스터로 시작해서 각 스텝마다 클러스터의 개수가 하나씩 줄어드므로, 총 $N$개의 partition이 반환됩니다.
위의 예시로 Dendrogram의 특징을 알아보겠습니다.
- Dendrogram의 가장 아래 부분은 노드들의 label을 나타냅니다.
- 위로 올라가 때마다 2개의 cluster가 하나로 합쳐집니다. 합쳐진 클러스터는 두 수직전을 잇는 수평선으로 표현됩니다.
- 한 클러스터에 속하는 노드들은 그 클러스터를 나타내는 수평선에서부터 아래로 이어진 수직선들을 따라가면 알 수 있습니다.
Partition을 선택하는 방법은 dendrogram에 수평선을 그어서, 그 수평선과 교차 되는 수직선들을 클러스터로 선택하는 것입니다. 예를 들어, 위의 dendrogram에서 검은 점선을 그어서 partition을 선택하면, 라이언 이모티콘이 있는 두 수직선이 cluster로 선택됩니다. 따라서, 검은 점선은 네트워크를 둘로 나누는 partition이 됩니다.
높은 위치에서 자를수록 적은 수의 클러스터로 이루어진 partition을 선택하게 됩니다. 반대로 낮은 위치에서 자를수록 더 세분화된 클러스터로 이루어진 partition을 선택하게 됩니다.
마지막으로, 각 partition의 클러스터는 아래에 위치한 partition들의 클러스터를 포함하기 때문에 위계 (hierarchy)가 만들어집니다. (Hierarchical clustering 이라는 이름의 이유)
2 - 3. 코딩 예시
이제 Zachary's karate club 데이터를 이용해서 hierarchical clustering을 해봅시다.
아래는 실제 Zachary's karate club 네트워크 입니다.
import networkx as nx
K = nx.karate_club_graph()
club_color = {
'Mr. Hi': 'orange',
'Officer': 'lightblue',
}
pos = nx.spring_layout(K, seed=7)
node_colors = [club_color[K.nodes[n]['club']] for n in K.nodes]
nx.draw(K, pos, node_color=node_colors, with_labels=True)
Hierarchical clustering은 scipy를 이용해서 해보겠습니다.
먼저, 각 노드 쌍의 similarity를 계산해주는 함수를 만들어주었습니다.
from itertools import combinations
import numpy as np
from scipy.cluster import hierarchy
import matplotlib.pyplot as plt
def similarity_of_nodes(G):
node_pair = list(combinations(list(G.nodes), 2))
similarities = []
for pair in node_pair:
list_of_neighbor_a = list(G.neighbors(pair[0]))
list_of_neighbor_b = list(G.neighbors(pair[1]))
shared_neighbor = set(list_of_neighbor_a).intersection(list_of_neighbor_b)
union_neighbor = list(set().union(list_of_neighbor_a, list_of_neighbor_b))
similarities.append(len(shared_neighbor) / len(union_neighbor))
return np.array(similarities)Scipy의 hierarchical clustering은 거리를 사용합니다. 즉, 값이 작을수록 두 클러스터가 가까운 것입니다. 반면에, similarity measure는 값이 클수록 두 클러스터가 가까운 것이기 때문에 1을 더해주고 역수를 취해주었습니다. (1을 더해준 것은 0으로 나누는 것을 피하기 위함입니다.)
Linkage는 average를 사용해서 dendrogram을 그려봤습니다.
similarities = 1 / (similarity_of_nodes(K) + 1.0)
Z = hierarchy.linkage(similarities, 'average')
plt.figure()
dn = hierarchy.dendrogram(Z)
plt.show()
그리고 cut_tree() 매서드를 이용해서 2개의 클러스터를 가지는 partition을 선택했습니다.
hierarchical_result = hierarchy.cut_tree(Z, n_clusters=2).flatten()
print(hierarchical_result) # [0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]마지막으로, 선택한 partition에 맞게 노드를 칠해주었습니다.
결과가 상당히 잘 나왔습니다. 실제 네트워크와 다른 노드는 8번 노드뿐입니다.
hierarchical_node_colors = ['orange' if n == 0 else 'lightblue' for n in hierarchical_result]
nx.draw(K, pos, node_color=hierarchical_node_colors, with_labels=True)
하지만 complete linkage를 사용하면 어떻게 될까요?
아래의 코드를 이용하여 complete linkage의 결과대로 노드를 칠해보았습니다.
Z_complete = hierarchy.linkage(similarities, 'complete')
hierarchical_result = hierarchy.cut_tree(Z_complete, n_clusters=2).flatten()
hierarchical_node_colors = ['orange' if n == 0 else 'lightblue' for n in hierarchical_result]
nx.draw(K, pos, node_color=hierarchical_node_colors, with_labels=True)
Average linkage의 결과와 매우 다르다는 것을 확인할 수 있습니다. 또한 실제 네트워크와도 큰 차이를 보여줍니다.
이처럼 어떤 linkage를 사용하느냐에 따라 결과가 굉장히 달라지기 때문에 hierarchical clustering을 사용할 때는 linkage의 선택에 주의해야 합니다.
2 - 4. 한계
- Hierarchical clustering은 노드의 수 만큼의 partition들을 결과로 줍니다. 이 중 어떤 partition을 선택할 지는 우리의 판단에 달려 있으며, 명확한 기준이 없습니다.
- 결과가 similarity measure에 따라 바뀌며, 특히 어떤 linkage를 채택하느냐에 따라 크게 바뀔 수 있습니다.
- 꽤 느리기 때문에 node가 굉장히 많은 네트워크의 경우, 사용이 어렵습니다.