title: “SNA Community Practice”
author: “Jeongsoo, Park”
date: “Friday, Aug 1, 2014”
목차
조직이나 사회에는 집단이 존재합니다. 회사라면 공식적인 부서로 구획된 집단이 존재할 것입니다. 이외에도 우리는 객관적인 소속 관계로 이루어진 다양한 집단에 속해 있습니다. 그런데, 그러한 명시적인 집단 외에도, 우리는 연결 구조를 바탕으로 한 암묵적인 집단 또한 가지고 있습니다. 회사에서 공식적인 부서 조직 이외에 암묵적으로 형성되는 라인이라던지, 은근히 이루어지는 왕따 현상 등이 한 예일 것입니다.
교류가 활발하고 밀집된 집단일수록, 그 구성원들이 가지게 되는 특징은 강해지고 비슷해질 것입니다. 그리고 사회적으로 소속 집단의 규범으로부터 더 강한 구속을 받게 됩니다.
오늘은 네트워크 연결구조를 바탕으로 cohesive subgroup을 도출해내는 분석에 대해 설명하도록 하겠습니다.
아래 두 네트워크는, 한 반에 있는 초등학생들의 친구관계를 나타낸 네트워크입니다. 5개의 초등학교에서 총 36개의 학급에 있는 881명의 학생들에게 설문을 통해 수집한 데이터이며, 그 중 2개 학급을 골라냈습니다. 각 학생들은, ‘제일 친한 친구’ 한명, ‘친한 친구’ 세명, ‘친구’ 전부의 이름을 적어달라는 설문을 받았습니다. [1]
이 두 학급이 어떤 하부 조직으로 이루어져 있는지 살펴봅시다. 우선 네트워크 맵을 그려봅시다.
> library(igraph)
## Loading required package: methods
> g3 <- read.graph('3rd_grade.graphml', format='graphml') > V(g3)$size <- 10 > E(g3)$arrow.size <- 0.5 > E(g3)$color <- "#33333333" > layout_g3 <- layout.fruchterman.reingold(g3) > plot(g3, layout=layout_g3)
> g4 <- read.graph('4th_grade.graphml', format='graphml') > V(g4)$size <- 10 > E(g4)$arrow.size <- 0.5 > E(g4)$color <- "#33333333" > layout_g4 <- layout.fruchterman.reingold(g4) > plot(g4, layout=layout_g4)
겉으로 보기에는 구조적인 특징이 잘 드러나지 않습니다. 4학년 학급에서는 약간 두 개의 그룹으로 나뉘어져 있는 것처럼 보이기도 합니다. 혹시 성별에 따라 남자애들끼리, 여자애들끼리 노는지 성별을 표시해서 봅시다.
> V(g3)$color <- ifelse(V(g3)$sex == "male", "green", "orange") > plot(g3, layout=layout_g3)
> V(g4)$color <- ifelse(V(g3)$sex == "male", "green", "orange")
## Warning: number of items to replace is not a multiple of replacement ## length
> plot(g4, layout=layout_g4)
성별에 따라서도 구조적인 특징을 찾아보기 어렵습니다. 뭔가 학생들끼리 놀 때는 유유상종이 작용할 것 같은데, 어떤 속성을 살펴봐야 할까요? 부모님의 경제력? 성격?
이렇듯 노드 개개의 속성을 근거로 해서 군집을 찾아내는 것이 어려운 경우, 네트워크 데이터라면 행위(관계 행위)를 근거로 해서 군집을 찾아낼 수 있습니다.
어떻게 구조적인 특징, 그 중에서도 밀집된 집단을 찾아볼 수 있을까요?
첫번째로 사용할 수 있는 방법은, k-core를 찾는 것입니다.
k-core는, 그룹 안에서 최소 k개의 degree를 가지는 최대의(maximal) 그룹을 말합니다.
아래 노드들은 그룹 안에 포함된 노드들간에 degree가 2 이상입니다. 따라서 이 그룹은 2-core입니다.
> g_2_core <- graph.formula(1-2:3, 2-3) > graph.coreness(g_2_core)
## 1 2 3 ## 2 2 2
> plot(g_2_core)
아래 노드들은 일부는 degree가 3이지만, 일부는 2입니다. 따라서 아직 이 그룹은 2-core입니다.
> g_2_core_2 <- graph.formula(1-2:3:4, 2-3, 3-4) > graph.coreness(g_2_core_2)
## 1 2 3 4 ## 2 2 2 2
> plot(g_2_core_2)
아래 노드들은 degree가 모두 3입니다. 아래 그룹은 3-core입니다.
> g_3_core <- graph.formula(1-2:3:4, 2-3:4, 3-4) > graph.coreness(g_3_core)
## 1 2 3 4 ## 3 3 3 3
> plot(g_3_core)
k-core는 중첩될 수 있습니다.
coreness는 네트워크의 k-core 구조를 계산하여 각 노드들이 속한 최대 core 수를 구하는 것입니다.
> g_coreness <- graph.formula(1-2:3:4, 2-3:4, 3-4, 3-5:6, 5-6, 6-7, 5-7) > plot(g_coreness)
위 그래프의 경우, 2-core 하나와 3-core 하나로 이루어져 있습니다.
여기서 3번 노드는 2-core에도 속하고 3-core에도 속합니다. 이런 경우, 3번 노드의 coreness 값은 그 중 가장 큰 값인 3-core로 결정합니다.
coreness는 일종의 등고선처럼 이해할 수 있습니다.
> draw.heatmap <- function(g, index=graph.coreness, layout=layout.fruchterman.reingold, print_result=TRUE) { + g_ud <- as.undirected(g) + V(g_ud)$size <- 10 + E(g_ud)$arrow.size <- 0.5 + E(g_ud)$color <- "#33333333" + V(g_ud)$v_heatmap <- index(g_ud) + if(print_result) { + print(V(g_ud)$v_heatmap) + } + max_value <- max(V(g_ud)$v_heatmap) + min_value <- min(V(g_ud)$v_heatmap) + color_levels <- heat.colors(max_value - min_value + 1) + V(g_ud)$color <- color_levels[max_value - V(g_ud)$v_heatmap + 1] + plot(g_ud, layout=layout) + + }
아래 3학년 네트워크를 보면, 빨간색으로 나타난 가장 핵심적인 그룹이 있고, 그 외곽에 다음 그룹이, 그 외곽에 다음 그룹이 점차적으로 core 수를 낮춰가며 존재하는 것을 볼 수 있습니다.
> draw.heatmap(g3, layout=layout_g3)
## [1] 8 8 8 7 8 8 8 8 8 8 8 8 8 8 6 8 6 6 8 6 7 6
반면 아래 4학년 네트워크를 보면, 대부분 같은 core에 속해 있는 것을 볼 수 있습니다. 3학년 네트워크에 비해 비교적 두루두루 친한 경향이 있다고 볼 수 있습니다.
> draw.heatmap(g4, layout=layout_g4)
## [1] 7 7 7 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 6 7
coreness 결과의 유용성을 보기 위해 더 큰 네트워크에 대해서 수행해봅시다.
> library(igraphdata) > data(UKfaculty) > V(UKfaculty)$size <- 5 > V(UKfaculty)$label <- NA > E(UKfaculty)$arrow.size <- 0.2 > E(UKfaculty)$color <- "#33333333" > layout_ukfaculty <- layout.fruchterman.reingold(UKfaculty) > draw.heatmap(UKfaculty, layout=layout_ukfaculty)
## [1] 6 11 6 6 11 9 11 6 6 11 2 11 11 6 11 11 6 11 11 10 11 11 11 ## [24] 7 10 10 11 7 11 5 11 7 11 11 11 6 11 7 11 11 8 11 11 5 6 11 ## [47] 7 7 11 11 11 11 6 11 7 6 11 11 6 4 6 11 5 7 8 5 5 11 11 ## [70] 11 8 11 2 6 6 9 11 5 11 8 6
k-core가 degree와 연관이 크기 때문에 degree centrality 결과와 거의 비슷하지 않은지 의구심이 들 수 있습니다. Degree 값으로 그린 결과를 확인해봅시다.
> draw.heatmap(UKfaculty, index=degree, layout=layout_ukfaculty)
## [1] 9 24 7 13 28 12 22 6 12 23 2 13 17 7 22 14 12 19 16 16 25 15 16 ## [24] 7 11 13 25 8 41 6 21 9 17 12 20 7 41 16 14 15 9 19 23 5 9 17 ## [47] 8 10 18 13 16 27 9 24 9 6 16 19 9 4 12 36 6 9 8 5 5 17 27 ## [70] 13 8 13 2 8 9 9 27 5 15 10 7
Degree 결과만으로는 밀집된 하부 집단(cohesive subgroup)을 찾아내기 쉽지 않습니다.
k-core 이외에 또 하부 집단을 구분할 수 있는 방법으로, 커뮤니티 탐지 알고리즘을 사용할 수 있습니다.
> r3 <- label.propagation.community(g3) > r3
## Graph community structure calculated with the label propagation algorithm ## Number of communities: 2 ## Modularity: 0.2181 ## Membership vector: ## [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
> V(g3)$color <- r3$membership + 1 > plot(g3, layout=layout_g3)
> r4 <- label.propagation.community(g4) > r4
## Graph community structure calculated with the label propagation algorithm ## Number of communities: 3 ## Modularity: 0.3835 ## Membership vector: ## [1] 1 2 2 1 2 3 2 1 2 3 3 3 3 1 2 2 3 1 2 3 1 1 2 2
> V(g4)$color <- r4$membership + 1 > plot(g4, layout=layout_g4)
네트워크에서 betweenness centrality가 높은 노드들이 커뮤니티와 관계가 있지 않을까요? 커뮤니티의 경계에 있지 않을까요? betweenness centrality가 높은 5개의 노드를 표시해봤습니다. (노드 원의 테두리를 다른 색으로 표시했습니다.)
> btw_g3 <- betweenness(g3) > btw_top <- head(sort(btw_g3, decreasing=TRUE), 5) > V(g3)$frame.color <- ifelse(btw_g3 >= btw_top[5], "orange", "black") > plot(g3, layout=layout_g3)
betweenness centrality가 높은 노드들은 비교적 커뮤니티의 변두리에 위치하기는 하지만, 커뮤니티를 분할하는데 사용하기에는 부족함이 있습니다.
조금 더 큰 네트워크에 대한 커뮤니티 분석 결과를 살펴봅시다.
> r_ukfaculty <- label.propagation.community(UKfaculty) > r_ukfaculty
## Graph community structure calculated with the label propagation algorithm ## Number of communities: 8 ## Modularity: 0.5264 ## Membership vector: ## [1] 1 2 3 3 4 5 5 2 6 5 2 5 5 7 2 5 3 2 2 7 2 5 5 8 2 7 5 5 2 5 2 8 5 2 2 ## [36] 1 2 2 2 5 2 5 2 1 1 2 5 4 5 2 2 2 3 2 4 7 2 2 3 6 1 2 5 4 5 5 4 5 5 2 ## [71] 5 5 3 3 3 5 5 3 2 7 3
> V(UKfaculty)$color <- r_ukfaculty$membership + 1 > plot(UKfaculty, layout=layout_ukfaculty)
커뮤니티가 잘 구분되었는지를 나타내는 지표로 Modularity가 있습니다. Modularity는 간단히 말하자면, 그룹 안의 링크가 그룹 밖과 연결된 링크보다 더 많다는 정도를 나타내는 지표라고 말할 수 있습니다. 더 간단하게 표현하면 나뉘어진 커뮤니티 구조가 얼마나 modular한지를 나타내는 지표라고 이해하시면 됩니다.
Modularity가 높을 수록 커뮤니티가 잘 구분되었다고 볼 수 있습니다. 네트워크와 커뮤니티 파티션 벡터를 가지고 modularity를 구할 수 있습니다. 주의할 점은, 네트워크만으로는 modularity를 구할 수 없고, 파티션 벡터가 같이 있어야 구할 수 있다는 점입니다.
대부분의 커뮤니티 탐지 알고리즘들은 주어진 네트워크에 대해서 커뮤니티를 이렇게 나눠보고 저렇게 나눠보면서, modularity 수치가 가장 높게 나눠진 상태를 찾아갑니다. [2]
> r3_e <- edge.betweenness.community(g3) > r3_e
## Graph community structure calculated with the edge betweenness algorithm ## Number of communities (best split): 6 ## Modularity (best split): 0.00407 ## Membership vector: ## [1] 1 2 3 1 1 1 4 1 5 1 6 1 1 1 1 1 1 1 1 1 1 1
> V(g3)$color <- r3_e$membership + 1 > plot(g3, layout=layout_g3)
위의 3학년 학급 네트워크를 보면, label propagation 알고리즘으로 나눈 커뮤니티 구조의 modularity는 0.2181인 반면, edge betweenness 알고리즘의 modularity는 0.0041입니다. 눈으로 확인해봐도 label propagation 알고리즘이 더 잘 나눈 것을 알 수 있지만, modularity 값 또한 label propagation 알고리즘의 값이 더 큰 것을 알 수 있습니다.
아래는 igraph에서 지원하는 커뮤니티 알고리즘의 목록입니다.
Undirected only
Undirected and Directed
[237]
[400]
커뮤니티는, 의미를 떠나서 절차적 관점에서 보면, 네트워크를 나누는 것입니다. 하지만 아무렇게나 나눠서는 안되겠죠. 뭔가 기준이 필요합니다.
가장 간단한 기준은, 네트워크를 잘랐을 때 잘려지는 링크가 가장 적게 자르는 것(minimum-cut)입니다. 그러나 이 기준만으로는 커뮤니티 분석을 수행하기에 모자람이 있습니다.
그래서 도입된 지표가 Modularity입니다.
Modularity는 아래와 같이 정의합니다. (Modularity는 통상적으로 Q로 표시합니다.)
$$
Q = {1 \over 2m} \sum_{ij} (A_{ij} - P_{ij})\delta(C_i, C_j)
$$
modularity(이하 Q) 값은 $[-{1 \over 2}, 1)$ 범위 내에서 결정됩니다. 만약 Q값이 양수라면, 그룹 안에 존재하는 링크의 수가 기대한 수보다 높다는 것을 의미합니다. 그룹 안에 존재하는 링크의 수가 기대한 수 이상이라는 것은, 무작위로 네트워크를 생성했을 때보다 그 링크가 많다는 것, 즉, 그 링크가 우연히 생기지는 않았다는 것, 무언가 의미있는 구조적 특성을 지닌다는 것을 뜻합니다.
여기서 ‘무작위로 네트워크를 생성’한다고 했는데, 무작위 네트워크의 종류도 많습니다. 무작위라고 해서 아무렇게나 무작위와 비교해서는 안되고, 원 네트워크의 고유한 일정 특성을 동일하게 지니는 제약을 가진(configuration model) 무작위 네트워크를 사용해야 합니다.
보편적으로 Q값을 구할 때 사용하는 무작위 네트워크는, 원 네트워크의 degree를 보존하는 네트워크를 사용합니다.
$m$ 은 전체 링크의 수입니다. $2m$ 을 사용하는 이유는, $A_{ij}$ 계산을 수행하면 (i,j), (j,i) 쌍 모두에 대해서 계산하기 때문입니다.
$\delta(C_i, C_j)$ 는, 링크 i-j가 존재하면 1, 그렇지 않으면 0을 반환하는 함수입니다.
$P_{ij}$는, i-j 링크가 존재할 확률을 나타냅니다. 아래와 같이 모든 링크의 갯수와 노드 i와 j의 degree 값( $k_i, k_j$ ) 을 활용해 정의합니다.
$$
P_{ij} = {k_i k_j \over 2m}
$$
링크가 존재할 수 있는 모든 가능성 있는 슬롯 ( $2m$ ) 중에, degree를 고려했을 때 이 두 노드가 다시 서로 링크를 맺을 경우의 수 ( $k_i * k_j$ )를 계산한 값입니다. 따라서, 해당 두 노드가 특성을 보존한 랜덤 네트워크 상에서 서로 링크를 가질 확률을 의미합니다.
완성된 최종 식은 아래와 같습니다.
$$
Q = {1 \over 2m} \sum_{ij} (A_{ij} - {k_i k_j \over 2m})\delta(C_i, C_j)
$$