네트워크 데이터 분석 - Community detection: Label propagation

데이터 사이언스

네트워크 데이터 분석 - Community detection: Label propagation

skypainter 2024. 7. 15. 04:27

이번 포스트에서는 커뮤니티 탐지의 마지막 알고리즘인 label propagation에 대해서 다루겠습니다.

1. Procedure

Label propagation은 한 노드의 이웃들은 보통 같은 커뮤니티에 속한다는 아이디어에서 출발합니다. 알고리즘의 절차는 다음과 같습니다.

각 노드를 다른 커뮤니티에 할당합니다. 즉, 각 노드에 다른 label을 부여합니다.
모든 노드를 무작위한 순서로 방문하면서 다음을 수행합니다: 해당 노드의 label을 다수의 이웃들이 갖는 label로 바꿔줍니다. 만약 동률이 있다면, 동률인 label중 하나를 무작위로 선택합니다.
모든 노드가 다수의 이웃들에 할당된 label을 갖게 되면 (stationary state) 과정을 멈춥니다. 그렇지 않으면 2를 반복합니다.
Stationary state에서 같은 label을 갖는 노드들을 하나의 커뮤니티로 정의합니다.

아래의 그림이 알고리즘을 시각화 하여 보여줍니다.

위의 과정에서 보면 알 수 있듯이 적은 수의 반복만으로도 많은 label들이 사라지고, 소수의 label들이 과정 내에서 우세하게 됩니다.

Label propagation의 장점은 네트워크의 크기와 무관하게 상당히 빠른 속도로 수렴한다는 것입니다. 또한 커뮤니티의 수나 크기에 대한 정보를 제공할 필요가 없기 때문에 parameter-free 합니다.

2. 코딩 예시

import networkx as nx
import matplotlib.pyplot as plt

partition = nx.community.asyn_lpa_communities(K, seed=1993)
partition = list(partition)
print(partition)
# [{0, 1, 3, 7, 11, 12, 13, 17, 19, 21}, {2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}, {4, 5, 6, 10, 16}]

labeled_node = [0] * K.number_of_nodes()
label = 0
                 
for c in partition:
    for idx in c:
        labeled_node[idx] = label
    label += 1


fig = plt.figure(figsize=(15, 6))
pos = nx.spring_layout(K, seed=7)
plt.subplot(1, 2, 1)
color_map = {0: 'orange', 1: 'lightblue', 2: 'green'}
lp_node_color = [color_map[i] for i in labeled_node]
nx.draw(K, pos, node_color=lp_node_color, with_labels=True)
plt.title('Predicted communities')

plt.subplot(1, 2, 2)
node_colors = [club_color[K.nodes[n]['club']] for n in K.nodes]
nx.draw(K, with_labels=True, node_color=node_colors, pos=pos)
plt.title('Actual communities')

3. 한계

Label propagation의 결과는 유일하지 않습니다. 이는 노드가 방문되는 순서에 따라 결과가 달라지기 때문입니다.
마찬가지로, 과정 중에 발생하는 많은 동률도 불안정한 결과를 가져옵니다.
이러한 한계들이 있음에도, label propagation으로 만들어진 partition들은 비슷한 경향이 있습니다. 이 partition들을 합쳐서 더 적합한 partiton을 만들어낼 수 있습니다.

4. Method evaluation

지금까지 다양한 community detection의 알고리즘을 알아봤습니다. 그렇다면, 이 알고리즘들이 얼마나 잘 작동하는지 평가 하는 방법은 무엇일까요?

4 - 1. Benchmarks

가장 먼저 떠오르는 평가 방법은 벤치마크를 이용하는 것입니다. 벤치마크로는 가상의 네트워크나 그룹에 대한 정보가 있는 실제 네트워크를 이용할 수 있습니다. 벤치마크에 알고리즘을 적용한 후 그 결과를 비교하여 알고리즘을 평가할 수 있습니다.

가장 많이 사용되는 데이터는 지금까지 제가 사용해 온 Zachary의 가라테 클럽 데이터입니다.

4 - 2. Negative test

잘 작동하는 커뮤니티 탐지 알고리즘은 실제 커뮤니티를 잘 탐지하는 것뿐만 아니라, 커뮤니티가 존재하지 않는 네트워크에서는 의미 없는 커뮤니티만을 탐지해야 합니다. 의미 없는 커뮤니티란 네트워크 전체를 하나의 커뮤니티로 보거나 각 노드를 각각의 커뮤니티로 보는 경우입니다. 만약 알고리즘이 랜덤 네트워크에서 유의미한 커뮤니티를 탐지한다면, 이 알고리즘은 신뢰할 수 없습니다. 따라서 벤치마크뿐만 아니라 랜덤 네트워크에서도 알고리즘을 테스트해봐야 하며, 이를 negative test라고 합니다.

아래의 코드는 Erdős–Rényi 그래프(랜덤 그래프)를 생성하고, label propagation으로 커뮤니티를 탐지합니다.
그림을 보면 알 수 있듯이, 탐지한 커뮤니티는 전체 네트워크입니다.

import networkx as nx

G = nx.erdos_renyi_graph(34, 0.2, seed=1993)
partition = nx.community.asyn_lpa_communities(G, seed=1993)
partition = list(partition)

labeled_node = [0] * G.number_of_nodes()
label = 0
                 
for c in partition:
    for idx in c:
        labeled_node[idx] = label
    label += 1

color_map = {0: 'orange', 1: 'lightblue', 2: 'green'}    
node_colors = [color_map[i] for i in labeled_node]
pos = nx.spring_layout(G, seed=7)
nx.draw(G, pos, with_labels=True, node_color=node_colors)

4 - 3. Partition similarity

또 다른 방법은 우리가 찾은 partition이 실제 partition과 얼마나 다른 지를 수치화 하는 측도를 이용하는 것입니다.

(1) Fraction of correctly detected nodes

가장 먼저 떠오르는 측도는 정확하게 분류된 노드의 비율일 것입니다. 정확하게 분류된 노드란, 해당 노드와 노드가 속한 커뮤니티의 절반 이상이 벤치마크에서 같은 커뮤니티에 속할 때 입니다. 주의할 점은 이 정의에 따르면, 탐지된 커뮤니티가 두 개 이상의 실제 커뮤니티가 합쳐진 경우, 이 커뮤니티의 모든 노드는 잘못 분류된 것으로 간주된다는 것입니다. 이처럼 정확하게 분류된 노드의 정의가 임의적이기 때문에 문제가 될 수 있습니다.

(2) Normalized mutual information (NMI)

또 다른 측도는 정보 이론의 상호 정보(mutual information)을 이용합니다. 상호 정보는 변수 $와 $가 얼마나 서로 관련이 있는지를 나타냅니다. 두 변수가 독립적이면 상호 정보는 0이 되고, 하나의 변수를 알면 다른 변수에 대한 정보를 얻을 수 있는 경우 상호 정보는 높아집니다.

Partition의 경우, 두 partition $X$와 $Y$가 비슷하다면, $X$를 $Y$로 바꾸는 데에는 적은 정보가 필요합니다. 더 많은 정보가 필요할수록 두 partition의 차이가 큽니다. 상호 정보는 이렇게 한 partition이 다른 partition으로 바뀌는 데에 필요한 정보의 양을 수치화 합니다.

이제 NMI를 정의 하기 위한 변수들을 도입하겠습니다.
먼저, 두 partition $X$와 $Y$가 있다고 할 때, 랜덤하게 선택한 노드가 partition $X$의 클러스터 $x$에 들어갈 확률은 $P(x) = \frac{N_{x}}{N}$ 입니다. ($N_{x}$ = 클러스터 $x$의 크기)
그리고 랜덤하게 선택한 노드가 partition $X$의 클러스터 $x$와 partition $Y$의 클러스터 $y$에 동시에 속할 확률은 $P(x,y) = \frac{N_{xy}}{N}$. 여기서 $N_{xy}$는 클러스터 $x$와 $y$에 동시에 속하는 노드의 수 입니다.

그러면 다음과 같이 entropy들을 정의할 수 있습니다.

Shannon entropy of $X$: $H(X) = -\sum_{x} P(x)logP(x)$
Conditional entropy of $X$ given $Y$: $H(X|Y) = \sum_{x,y}P(x,y)log[P(y) / P(x,y)]$

마지막으로, NMI는 다음과 같이 정의 됩니다.

$$NMI(X,Y) = \frac{2H(X) - 2H(X|Y)}{H(X) + H(Y)}$$

만약 두 partition이 동일하다면, $NMI=1$ 입니다.
두 개의 독립적인 랜덤 partition 비교 된다면, NMI 값의 기댓값은 0 입니다.
문제점: 실제 partition과 탐지된 partition에 차이가 있음에도, 탐지된 커뮤니티의 개수가 많다면 NMI 값이 더 크게 나올 수도 있습니다.

저작자표시 비영리 (새창열림)