포스팅 개요
이번 포스팅은 네트워크 분석(network analysis)에서 커뮤니티 탐지(community detection)에 대해서 정리하는 글입니다. 또한, community detection의 알고리즘 중 louvain 알고리즘에 대해서도 간략하게 소개하려고 합니다.
본 포스팅에서 참조한 글과 파이썬(Python)으로 실습한 자료의 데이터 셋은 아래와 같습니다.
- https://www.kaggle.com/stackoverflow/stack-overflow-tag-network
- https://danbi-ncsoft.github.io/works/2018/11/12/network_analysis-1.html
- https://arxiv.org/abs/0803.0476
- https://github.com/taynaud/python-louvain
포스팅 본문
Network Community Detection이란?
먼저 network community detection에 대해서 정리해보려고 합니다. 네트워크 커뮤니티 탐지는 무엇일까요? network community detection은 network 분석에 한 종류입니다. network 분석이라고 하면, network로 연결 된 node와 edge간의 관계를 통해 어떤 insight를 도출하는 과정을 뜻하는데요. 그 방법 중 community detection이 있습니다.
이 커뮤니티 탐지 방법은 연결 밀도가 높은 집단끼리 서로 묶어서 분석하는 방법을 말합니다. network에서는 이렇게 다른 집단 보다 좀 더 밀집하게 모듈성(modularity)가 높은 집단을 community라고 부르고 있다고 합니다.
이 방법은 일종의 클러스터링(clustering)이라고 생각하셔도 좋을 것 같습니다. 전체 집단에서 어떤 커뮤니티가 묶여져 있고, 또 이러한 커뮤니티는 어떠한 특성을 가지고 있는지 분석할 수 있기 때문입니다.
community detection에는 다양한 알고리즘이 존재합니다. 그 중 유명한 알고리즘은 아래와 같습니다.
- Finding community structure in very large networks : https://arxiv.org/abs/cond-mat/0408187
- Fast unfolding of communities in large network ( Louvain 알고리즘 ) : https://arxiv.org/abs/0803.0476
등 이렇게 다양한 community detection이 있는데요. 저는 그 중에서 louvain 알고리즘에 대해 간략하게 정리해보려고 합니다.
Louvain algorithm?
louvain의 방법은 위에서 소개해드린 논문에 소개되어 있습니다. 2008년에 나온 논문이지만, 아직까지도 많이 사용되고 있을 정도로 유명합니다. 논문과 louvain 알고리즘을 간단히 요약하면 아래와 같습니다.
- 보통 network community를 찾는 방법은 modularity 즉, 모듈성을 찾는 방법을 많이 사용한다. 하지만, 이 방법은 계산 시간이 길다는 단점이 존재합니다.
- 기존의 network modularity는 아래와 같습니다.
- 각 기호에 대한 설명은 아래와 같습니다.
- Aij : i와 j의weight of the edge (i, j간의 링크라고 생각해도 좋을 것 같습니다.)
- Ki : 꼭지점 i에 포함된 edges의 weight의 합 (i가 지니는 링크의 개수라고 생각해도 좋을 것 같습니다.)
- Ci : vertex i가 할당되는 커뮤니티
- ó(u, v) : u = v이면 1이고, 아니면 0
- m : 전체 링크 수
- 기존의 모듈성을 구하는 방법은 계산 시간이 오래걸려서 이를 최적화 하는 방법이 필요하다고 합니다.
- 또한, 대규모 커뮤니티는 자연적으로 커뮤니티가 하위 커뮤니티로 나뉘어서 계층적 구조로가 드러난다고 합니다.
- 따라서, 여기서는 더 효과적인 modularity와 계층적 구조를 이용합니다.
- 여기서의 method는 Phase 1, Phase 2로 나뉩니다. (이 Phase 1과 2를 합쳐서 하나의 Pass라고 부릅니다.)
- Phase1
- 한 node를 원래의 community에서 빼내어서 다른 인접한 commuinty에 재배치를 하고 이때 modularity를 측정
- 만약, modularity가 커지는 community가 있으면 해당 노드는 그 community에 속하게 한다.
- modularity 변화량 : 노드 i가 community에 배속된 상태 modularity - i가 배속되지 않은 상태의 modularity
- Phase1
-
-
- 각 수식에 대한 설명은 아래와 같습니다.
- ∑in : C의 내부 링크 weight의 합
- ∑tot: C에서 발생하는 모든 연결의 weight의 합
- ki : node i에서 발생한 link의 weight의 합
- ki,in : C에서 i에서 node로 연결되는 weight의 합
- m : 모든 link의 weight 합
- 따라서 이 모듈성의 변화가 긍정적이면 해당 community로 이동하고, 좋지 않으면 기존 community에 머무른다.
- Phase 1은 더 이상 개선할 수 없을 때까지 반복합니다.
- 각 수식에 대한 설명은 아래와 같습니다.
- Phase2
- Phase1에서 생성된 community를 가지고 새로운 commuinty를 구축합니다.
- 새로운 노드들 사이의 weights of the links는 두 커뮤니티 node들 사이의 link weight의 합으로 계산됩니다.
- 동일한 커뮤니티의 node들 간의 link는 self-loop으로 대체
- 이것이 끝나면 다시 Phase1으로. 그래서 이 Phase 1과 2를 계속 반복하는데, 이 과정을 Pass라고 명명
-
이후의 설명은 계산 시간도 효율적이고, 여러가지 측면에서 좋은 효율이 나왔다고 주장하는 글이어서 넘어가도록 하겠습니다. 궁금하신 분들은 논문을 꼭 읽어보시면 좋을 것 같습니다!
louvain algorithm community detection Python example
자 이제 network community detection 방법인 louvain을 Python으로 실습해봅니다. 이미 어떤 분들이 louvain 방법을 Python 패키지로 만들어주었습니다. 따라서, pip install로 간단하게 설치할 수 있고 적용할 수 있습니다. 관련한 자세한 설명은 개요 부분 github 링크를 첨부했으니 꼭 참고해주세요!
여기서의 실습은 kaggle에 올라온 stack overflow tag network 데이터를 사용했습니다. 그럼 실습으로 보실까요!
데이터 셋은 2개가 있습니다. 하나는 node에 대한 정보가 있으며 다른 하나는 edge에 대한 정보가 있습니다. 여기서 edge에 대한 정보를 사용하게 되면 node의 기본적인 정보는 따라오게 되어 있습니다. 노드 크기나, group은 가지고 오지 못하지만, name은 가지고 올 수 있죠. 이번은 louvain을 적용한 것을 보여드리기 위함이므로 node의 name만 사용합니다.
따라서, edge에 있는 source와 target 정보만 가지고 옵니다. 저렇게 하면 edge는 source와 target간의 연결 정보로 이루어져 있습니다. 또한, 각각에는 weight 값도 존재하므로 weight값도 가져와서 이를 edge에 적용해줍니다.
자! 이제 louvain 방법을 적용해볼까요? louvain code는 github에 가시면 기본 코드가 있습니다. 해당 코드를 적용하고, matplot에 color bar 정도만 추가해서 starck overflow tag들이 어떤 network 구조를 가지고 있고, 어떠한 것들이 louvain 상으로 community detection 이 되었는지 확인해봅니다. community detection이 된 노드들은 같은 색상을 가지고 있습니다.
-- github 기본 코드 --
import community as community_louvain
import matplotlib.cm as cm
import matplotlib.pyplot as plt
import networkx as nx
# load the karate club graph
G = nx.karate_club_graph()
# compute the best partition
partition = community_louvain.best_partition(G)
# draw the graph
pos = nx.spring_layout(G)
# color the nodes according to their partition
cmap = cm.get_cmap('viridis', max(partition.values()) + 1)
nx.draw_networkx_nodes(G, pos, partition.keys(), node_size=40,
cmap=cmap, node_color=list(partition.values()))
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.show()
자! network를 그렸습니다. 이 network는 어떤 관계를 가지고 있는지 봐볼까요? 그 특징은 아래와 같습니다.
네트워크 연결 특징
- vba-excel이 연결되어 있음
- iphone - objective c - swift - ios - xcode가 연결되어 있음
- java - spring - eclipse - rest가 연결되어 있음
- haskell - scala - hadoop - apache spark가 연결되어 있음
- vue js - express - react - bootstrap 등이 연결되어 있음
louvain 연결 특징
- iphone 계열의 iOS 쪽과 Android는 하나의 클러스터임
- Matlab, machine learning, python, r, flask, django는 같은 클러스터임
- powershell, windows, unix, ubuntu, linux, shell, bash, github, git은 같은 클러스터임
- java및 spring 계열은 같은 클러스터임
- go, docker, devops, jenkins 등은 같은 클러스터임
- asp.net, web-api 등은 같은 클러스터임
- angular, typescript, 등은 같은 클러스터임
- ruby, postgresql, redis, elasticsearch는 같은 클러스터임
- bootstrap 계열은 같은 클러스터임
- haskell, scala, hadoop, spark는 같은 클러스터임
그럴듯한 결과가 나왔습니다. 이 데이터 셋이 데이터가 그리 크지 않아서 엄청 명확하게 나눠지지는 않아보입니다.
하지만, 데이터 셋이 충분히 더 크다면 분명히 좋은 효과를 기대할 수 있을겁니다.
마지막으로 weight 값을 넣어서 적용해보겠습니다. 그 전에 weight 값을 weight의 평균 값 정도 되는 수치로 나누어서 넣어주겠습니다. 일종의 normalization이라고 생각하시면 될 것 같습니다. 왜냐하면 weight 값이 다른 weight 보다 큰 값이 있는데, 이러면 graph를 그릴 때 해당 weight만 엄청 크게 나오기 때문입니다.
어디 부분이 weight 값이 클까요?
- qt와 C++
- windows와 linux 그리고 unix
등등 재미있는 결과가 나왔습니다.
마무리
이번 포스팅은 network community detection에 대해서 알아보았습니다. 그 중 louvain 알고리즘까지 알아보았습니다. community detection은 굉장히 흥미로운 분야입니다. 이것을 어떻게 사용하냐에 따라서 사용자들의 흐름, 어떤 것들에 대한 관계성을 알 수 있기 때문입니다.
또한, 단순히 graph를 그리는 것 뿐만 아니라 어떤 community들 끼리 묶이는 것 까지 알 수 있기 때문에 이러한 정보들의 metadata를 살펴보면 어떤 insight를 얻을 수 있을것이라 기대할 수 있습니다.
이번 글은 여기서 마치겠습니다.
감사합니다.
