title: “SNA Centrality Practice”
author: “Jeongsoo, Park”
date: “Friday, July 21, 2014”
네트워크를 펼쳐놓고, 이제 무엇을 할까요? 조금 다른 질문으로, 네트워크를 왜 볼까요? 왜 네트워크 관점으로 볼까요?
어떤 집단이나 군집을 개개로 보는 것이 아니라 관계(링크)를 고려하여 보는 것입니다. 그 관계를 통해서 군집의 특징을 확인할 수도 있고, 각 개별자들이 군집 안에서 어떻게 자리매김하고 있는지를 확인할 수도 있습니다.
회사 조직을 아래처럼 양적인 수치로 특징지을 수 있습니다.
| 회사명 | 직원 수 | 연 매출 |
|---|---|---|
| Amazon | 117,300 | $ 74.45 b |
| 52,069 | $ 59.82 b | |
| 6,818 | $ 7.87 b | |
| Apple | 80,000 | $ 170.91 b |
또는, 아래처럼 조직 구성원들의 연결구조를 바탕으로 특징지을 수도 있습니다.
이렇게 연결구조를 관찰하여, 전체 구조가 어떤가를 살펴볼 수도 있고, 그 구조를 이루고 있는 개개의 요소들의 특징을 살펴볼 수도 있겠습니다.
오늘 시간에는 centrality라는 수치를 통해 노드가 네트워크에서 어떤 위치를 차지하고 있는지를 살펴보겠습니다.
Centrality는, 연결 구조를 바탕으로 어떤 노드가 중요한 노드이고 덜 중요한 노드인지를 구분할 수 있도록 각 노드에 중요도 점수를 부여하는 지표입니다. 단, 어떤 노드가 중요한 노드인지는 여러 관점과 필요에 따라 달라질 수 있습니다. 여기서는 중요한 노드를 정하는 몇 가지 기준, 대표적으로 4가지 centrality 지표들을 소개합니다.
가장 간단한 centrality 지표는 degree를 이용한 degree centrality (이하 DC)입니다.
각 노드의 degree를 근거로 노드가 네트워크에서 차지하는 중요도를 결정합니다. Degree는, 각 노드가 관계맺고 있는 링크의 수입니다. 간단히 말해, ‘친구가 많은 사람이 중요한 사람이다’라는 것입니다.
> library(igraph) > v <- c(1,2, 1,3, 1,4, 1,5, 2,3, 3,4) > g <- graph(v, directed=FALSE) > V(g)$name <- c("A", "B", "C", "D", "E") > V(g)$label <- c("A", "B", "C", "D", "E") > plot(g)
위와 같은 그래프가 있을 때, degree는 다음과 같습니다.
> V(g)$degree <- degree(g) > get.data.frame(g, what="vertices")
## name label degree ## A A A 4 ## B B B 2 ## C C C 3 ## D D D 2 ## E E E 1
그래프와 함께 보면 아래와 같습니다.
> V(g)$label <- V(g)$degree > V(g)$size <- V(g)$degree * 2 + 20 > plot(g)
조금 더 나눠서 살펴보면, 네트워크가 방향이 없을 때는 degree는 하나이지만, 방향이 있을 때는 in-degree와 out-degree 두 종류로 구분할 수 있습니다. 각 노드로 들어오는 링크의 갯수만 세는 경우가 in-degree, 나가는 링크의 갯수만 세는 경우가 out-degree 입니다. 또, 방향이 없는 네트워크에서처럼 링크의 방향을 구분하지 않고 degree로 셀 수도 있습니다.
DC는 이해하기 쉬운 지표입니다. 우리도 모르는채 종종 사용하는 지표이기도 하죠.
하지만 네트워크가 커질수록, 국지적인 영향력만을 나타내는 지표가 된다는 한계점이 있습니다.
네트워크의 규모가 상당히 크게 되면, 척도 없는(scale-free) 네트워크가 되는 경우가 있습니다. 어떤 네트워크가 ‘척도 없는 네트워크’인지 여부를 판단할 때, Degree 값의 분포 (degree distribution)가 power law를 따르는지를 가지고 판단합니다.
또 다른 종류의 centrality 지표로 Betweenness centrality 지표 (이하 BC)가 있습니다.
BC는 메세지 전달의 통로 역할을 해주는 사람이 중요한 사람이라고 봅니다.
> btw <- betweenness(g) > V(g)$bc <- btw > V(g)$label <- btw > V(g)$size <- btw * 2 + 20 > get.data.frame(g, what="vertices")
## name label degree size bc ## A A 3.5 4 27 3.5 ## B B 0 2 20 0.0 ## C C 0.5 3 21 0.5 ## D D 0 2 20 0.0 ## E E 0 1 20 0.0
> plot(g)
잠시 BC의 특징이 조금 더 잘 나타나는 네트워크로 살펴봅시다.
> v_bc <- c(1,2, 1,3, 1,4, 1,5, 2,3, 3,4, 5,6, 6,7, 6,8, 7,8, 6,9, 8,9) > g_bc <- graph(v_bc, directed=FALSE) > V(g_bc)$label <- c("A", "B", "C", "D", "E", "F", "G", "H", "I") > plot(g_bc)
> deg <- degree(g_bc) > V(g_bc)$label <- deg > V(g_bc)$size <- deg * 2 + 20 > plot(g_bc)
> btw <- betweenness(g_bc) > V(g_bc)$label <- btw > V(g_bc)$size <- btw * 2 + 20 > plot(g_bc)
위 네트워크를 보면, 가운데 노드들이 양쪽의 두 군집을 이어주는 가교 역할을 해주고 있습니다. 그런데 DC 값은 그 노드들에 대해 특별히 의미를 두지 않습니다. 반면, BC 값은 가교 역할을 해주는 노드들을 매우 강조합니다.
BC 값이 높은 노드들은: [1]
> V(g)$label <- V(g)$name > plot(g)
A 노드의 BC 값의 계산 과정을 따라가봅시다. 우선, 그래프에서 모든 조합 가능한 두 개의 노드에 대해서 최단경로를 구합니다. 단, 시작/끝 노드에 A 노드는 포함되지 않도록 합니다. $C_{(i, j), i \neq j, i \neq 1, j \neq 1}$
그리고, 각 시작/끝 노드 쌍에 대해서 $\sigma_{st}(v) / \sigma_{st}$ 값을 구합니다.
$$
x_i = \sum_{st} {n^i _{st}}
$$
| 시작 | 끝 | 최단경로 | Sigma |
|---|---|---|---|
| B | D | B - [A] - D B - C - D |
0.5 |
| B | E | B - [A] - E | 1 |
| C | E | C - [A] - E | 1 |
| D | E | D - [A] - E | 1 |
모든 $\sigma$ 값을 더합니다.
> 0.5 + 1 + 1 + 1
## [1] 3.5
BC 값은, 구하는 과정에서 볼 수 있듯이, 모든 노드 쌍에 대해서 거리 행렬을 구해야 하기 때문에 계산량이 많아서 큰 네트워크를 계산하는데는 매우 오랜 시간이 걸리고 많은 메모리 공간을 필요로 하기 때문에 큰 네트워크에 대해서는 잘 사용하지 않습니다.
Closeness Centrality (이하 CC)는, 다른 노드와의 거리가 짧을수록 정보 전달이 효율적이라는 가정을 가지고, 다른 노드와의 거리가 가장 짧은 노드를 중요한 노드라고 봅니다. 다른 노드와의 거리가 가장 짧은 노드라면 거리 측면에서 네트워크의 중앙(middle)에 자리잡는 경향이 클 것입니다. 따라서 네트워크 여기 저기서 새로운 정보/소식이 생겨날 때, 다른 노드들에 비해서 빠르게 입수할 가능성이 큽니다.
> cc <- closeness(g) > V(g)$cc <- cc > get.data.frame(g, what='vertices')
## name label degree size bc cc ## A A A 4 27 3.5 0.2500 ## B B B 2 20 0.0 0.1667 ## C C C 3 21 0.5 0.2000 ## D D D 2 20 0.0 0.1667 ## E E E 1 20 0.0 0.1429
> V(g)$size <- cc * 100 + 5 > V(g)$label <- cc > plot(g)
CC는 다음과 같이 정의합니다.
$$
\sigma_c {(x)} = {1 \over {\sum_{i=1, i \neq x}^{n} d_G {(x,i)}}}
$$
C 노드의 CC를 구하는 과정을 살펴봅시다.
| 시작 | 끝 | 최단거리 |
|---|---|---|
| C | A | 1 |
| C | B | 1 |
| C | D | 1 |
| C | E | 2 |
> 1 / (1+1+1+2)
## [1] 0.2
CC의 재미있는 특징이 한 가지 있는데, 네트워크가 커질수록 노드들의 CC 값의 편차가 매우 작다는 것입니다. 네트워크가 커질수록 허브 등의 영향으로 작은 세상이 될 가능성이 있는데, 작은 세상 네트워크는 평균 경로 거리가 매우 작고, 노드들간의 거리 편차가 작습니다. 매우 거대한 네트워크인 실제 사회에 대한 밀그램의 실험에서도 평균 도달거리가 6.5였던 것을 생각하면 이해가 되는 부분입니다. 그렇기 때문에 종종 노드의 중요도를 판단하는 지수로서는 변별력 있게 사용하기가 어려운 경우가 있습니다. [2]
CC 역시 모든 노드 쌍에 대해 거리 행렬을 구해야 하기 때문에 계산에 시간과 메모리가 많이 필요합니다. 하지만 (i, j)에 대한 모든 가능한 최단 경로를 구해야 하는 BC에 비해 CC는 (i, j)에 대한 최단 경로 거리만을 구하기 때문에 계산량은 약간 덜합니다.
EC는 친구가 많은 사람도 중요한 사람이고, 중요한 친구를 둔 사람도 중요한 사람이라고 봅니다.
Degree centrality가 자신의 이웃 수만으로 노드의 중요도를 결정했다면, eigenvector centrality (EC)는 그 이웃 각각의 중요도를 함께 고려합니다. 유력한 이웃을 둔 노드는 그에 따라 점수를 덩달아 높여줍니다. EC는 영향력이 낮은 이웃을 여러명 아는 사람도 점수가 높지만, 유력한 이웃을 몇명 아는 사람도 점수가 높아질 수 있습니다.
> ec <- evcent(g, scale=FALSE) > V(g)$ec <- ec$vector > get.data.frame(g, what="vertices")
## name label degree size bc cc ec ## A A 0.25 4 30.00 3.5 0.2500 0.5825 ## B B 0.166666666666667 2 21.67 0.0 0.1667 0.4119 ## C C 0.2 3 25.00 0.5 0.2000 0.5237 ## D D 0.166666666666667 2 21.67 0.0 0.1667 0.4119 ## E E 0.142857142857143 1 19.29 0.0 0.1429 0.2169
> V(g)$label <- round(ec$vector, 2) > V(g)$size <- ec$vector * 10 + 5 > plot(g)
EC의 정의는 다음과 같습니다.
$$
\sigma_E (x) = {1 \over \lambda_{max} (A)} \cdot \sum_{j=1}^{n} a_{jx} \cdot v_j
$$
네트워크 g에 대한 EC 계산 과정을 살펴봅시다.
본래 EC는 $A x = k x$ 를 만족하는 k와 x를 구하는 것입니다. k를 eigenvalue라고 하고, x를 eigenvector라고 합니다. eigenvalue / eigenvector를 구하는 여러 가지 방법이 있는데, 여기서는 그 중에서 Power iteration이라는 방법으로 EC를 구하는 과정을 살펴보겠습니다. [3]
우선 네트워크를 행렬 형태로 만듭니다. 그리고 eigenvector centrality의 초기값을 v에 넣어줍니다.
> A <- get.adjacency(g) > v <- c(1,1,1,1,1)
그리고 v에 대해 아래 과정을 반복해줍니다. 그러면 v가 점점 수렴해가면서, 계속 같은 값이 나오게 되는데, 그 값을 eigenvector 값이자 eigenvector centrality 값으로 결정합니다.
> ev <- function(A, v) { + raw_x <- as.vector(A%*%v) + norm <- sqrt(sum(raw_x * raw_x)) + norm_x <- raw_x / norm + delta <- round(sum(abs(v-norm_x)), 4) + print(norm_x) + return(norm_x) + }
v의 수렴을 그래프로 확인하기 위해 몇 개의 패키지를 추가로 설치해줍시다.
> install.packages('reshape2') > install.packages('ggplot2')
> library(reshape) > library(ggplot2) > > v <- c(1,1,1,1,1) > h <- v > v <- ev(A, v); h <- rbind(h, v)
## [1] 0.6860 0.3430 0.5145 0.3430 0.1715
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5143 0.4500 0.5143 0.4500 0.2571
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.624 0.384 0.528 0.384 0.192
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5547 0.4295 0.5189 0.4295 0.2326
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.6000 0.4000 0.5266 0.4000 0.2067
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5710 0.4196 0.5214 0.4196 0.2235
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5899 0.4068 0.5252 0.4068 0.2127
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5777 0.4152 0.5226 0.4152 0.2197
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5856 0.4097 0.5244 0.4097 0.2151
> v <- ev(A, v); h <- rbind(h, v)
## [1] 0.5805 0.4133 0.5232 0.4133 0.2181
> rownames(h) <- c("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10") > colnames(h) <- c("Node1", "Node2", "Node3", "Node4", "Node5") > > h.long <- melt(h, id.vars=c("Iteration", "Node")) > ggplot(data=h.long, aes(x=X1, y=value, group=X2)) + geom_line(aes(color=X2))
반복을 충분히 하지 못해 수렴이 덜 되어서 실제 EC 결과값인 0.5825, 0.4119, 0.5237, 0.4119, 0.2169와는 약간 차이가 있지만, 점차 비슷한 값으로 접근해가는 것을 볼 수 있습니다.
기본적으로 EC의 계산 과정은, $A \cdot v$ 의 반복이라고 볼 수 있습니다. 그런데 재미있는 점은, DC와의 관계입니다.
> v <- c(1,1,1,1,1) > A%*%v
## 5 x 1 Matrix of class "dgeMatrix" ## [,1] ## A 4 ## B 2 ## C 3 ## D 2 ## E 1
> degree(g)
## A B C D E ## 4 2 3 2 1
첫번째 $A \cdot v$ 의 결과가 DC 값과 같은 것을 볼 수 있습니다. 그리고 이 결과에 다시 A 행렬, 즉 연결구조를 적용합니다. (실제 계산 과정에서는 각 vector가 계산되면 정규화(normalize)를 거칩니다.)
> A%*%(A%*%v)
## 5 x 1 Matrix of class "dgeMatrix" ## [,1] ## A 8 ## B 7 ## C 8 ## D 7 ## E 4
> A%*%(A%*%(A%*%v))
## 5 x 1 Matrix of class "dgeMatrix" ## [,1] ## A 26 ## B 16 ## C 22 ## D 16 ## E 8
이렇게 초기값이 1로 주어졌던 eigenvector centrality 값은 계산을 거듭할수록 연결구조가 노드 가중치로 반영된 값으로 변화해갑니다.
EC 계산은 몇 가지 특징을 가지고 있습니다.
EC는 BC나 CC에 비해 상대적으로 계산량이 적어서 거대 네트워크에 대해 적용하기가 용이합니다.
EC가 directed 네트워크에 대해 가지고 있는 특성을 보완하기 위한 EC의 변형으로 Katz centrality가 있습니다.
Katz centrality의 식을 보면, EC의 식과 매우 유사합니다.
Katz centrality
$$
\sigma_E (x) = \alpha \sum_{j=1}^{n} a_{jx} (v_j + \beta)
$$
Eigenvector centrality
$$
\sigma_E (x) = {1 \over \lambda_{max} (A)} \sum_{j=1}^{n} a_{jx} v_j
$$
Katz centrality는 EC를 일반화시킨 것으로, EC는 $\alpha = {1 \over \lambda_{max} (A) }, \beta = 0$ 인 Katz 식이라고 할 수 있습니다.
$\beta$ 부분이 들어감으로써 in-degree가 없는 노드도 기본적인 값을 가지게 됩니다. 그래서 계산 대상에 포함될 수 있습니다. $\beta$ 에는 노든 노드에 같은 값을 넣을 수도 있지만, 노드의 속성을 넣어서 연결구조를 바탕으로 한 centrality값을 보정할 수도 있습니다.
Katz centrality의 변형으로 PageRank가 있습니다.
$$
\sigma_{PageRank} (x) = \alpha \cdot \sum_{j=1}^{n} a_{jx} {v_j \over k^{out}_j} + \beta_j
$$
PageRank은 Google에서 웹 페이지의 가중치를 부여할 때 사용한 알고리즘입니다. (지금의 알고리즘은 저 기본식보다 훨씬 복잡하다고 알려져 있습니다.) 위의 식은 original PageRank 알고리즘을 약간 일반화한 것이고, 본래 식에서는 $\beta_j = 1 - \alpha$ 로 되어 있고, $\alpha$ 의 기본 값은 0.85입니다.
Katz 알고리즘과 다른 점은, $1 \over k^{out}_j$ 부분이 들어간 점입니다. 보통 웹사이트는 in/out degree가 높은데, 영향력 점수가 높은 하나의 웹사이트가 out-link로 연결하는 모든 웹사이트들이 덩달아서 매우 높은 값을 가지게 되는 상황을 방지하기 위해, link별로 영향력을 분산시키는 것입니다.
igraph는 Katz centrality를 계산할 수 있는 기능은 제공하지 않고, PageRank를 계산할 수 있는 기능만을 제공하고 있습니다.
> pr <- page.rank(g) > V(g)$pr <- pr$vector > get.data.frame(g, what="vertices")
## name label degree size bc cc ec pr ## A A 0.58 4 10.825 3.5 0.2500 0.5825 0.32484 ## B B 0.41 2 9.119 0.0 0.1667 0.4119 0.16740 ## C C 0.52 3 10.237 0.5 0.2000 0.5237 0.24132 ## D D 0.41 2 9.119 0.0 0.1667 0.4119 0.16740 ## E E 0.22 1 7.169 0.0 0.1429 0.2169 0.09903
> V(g)$label <- round(pr$vector, 2) > V(g)$size <- pr$vector * 10 + 5 > plot(g)
간혹 UCInet이나 Pajek, NetMiner 등의 계산 값과 igraph 계산 값이 다를 수 있습니다. 앞의 소프트웨어들도 서로 값이 다를 수도 있습니다.
오늘 실습에서 사용했던 주요 지표들 - DC, BC, CC, EC - 은, 이해의 편의를 위해 normalize를 하지 않은 값을 사용했습니다. 다른 소프트웨어와 값이 다른 경우, 첫번째로 normalize를 하는지, 어떻게 하는지 여부를 확인해보시기 바랍니다. 그 외에도 수식의 작은 변형이 있을 수도 있습니다.
Centrality 지표 종류마다 나타내는 특징이 약간씩 다릅니다. 아래의 표는 각 지표의 높고 낮음에 따른 노드의 특징을 분류합니다.
| Low Degree | Low Closeness | Low Betweenness | |
|---|---|---|---|
| High Degree | 어떤 군집 속에 들어있으면서, 그 군집은 네트워크의 나머지 부분과 멀리 떨어져 있는 경우 | 그 노드의 링크들이 중복되어 있는 경우 (친구끼리도 친구) - 커뮤니케이션이 그 노드를 건너뜀 | |
| High Closeness | 그 노드가 중요한 노드와 긴밀히 연결되어 있는 경우 | 아마도 네트워크에 경로들이 여러개 존재한 것. 해당 노드 곁에는 사람들이 많지만, 다른 사람들도 형편이 비슷할 것임 | |
| High Betweenness | 그 노드의 얼마 되지 않는 링크가 네트워크 흐름에 치명적인 경우 | 매우 드문 경우. 아마도 소수의 몇몇이 나머지 대다수에게 연결되어 있는 링크를 그 노드가 중간에서 독점하고 있는 경우일듯. |
James Moody의 slide[4]에서 인용.
> library(igraphdata) > data(UKfaculty)
> V(UKfaculty)$size <- 5 > V(UKfaculty)$label <- NA > E(UKfaculty)$arrow.size <- 0.3 > E(UKfaculty)$color <- "#33333333" > > plot(UKfaculty)
위 그래프에서 centrality가 가장 높은 노드 3개는 무엇이 되어야 할까요?
DC가 선택한 노드는 아래와 같습니다.
> V(UKfaculty)$dc <- degree(UKfaculty) > k_dc_top_three <- head(sort(degree(UKfaculty), decreasing=TRUE), n=3) > V(UKfaculty)$color <- ifelse(V(UKfaculty)$dc >= k_dc_top_three[3], "red", "white") > plot(UKfaculty)
BC가 선택한 노드는 아래와 같습니다.
> V(UKfaculty)$bc <- betweenness(UKfaculty) > k_bc_top_three <- head(sort(betweenness(UKfaculty), decreasing=TRUE), n=3) > V(UKfaculty)$color <- ifelse(V(UKfaculty)$bc >= k_bc_top_three[3], "red", "white") > plot(UKfaculty)
CC가 선택한 노드는 아래와 같습니다.
> V(UKfaculty)$cc <- closeness(UKfaculty) > k_cc_top_three <- head(sort(closeness(UKfaculty), decreasing=TRUE), n=3) > V(UKfaculty)$color <- ifelse(V(UKfaculty)$cc >= k_cc_top_three[3], "red", "white") > plot(UKfaculty)
EC가 선택한 노드는 아래와 같습니다.
> V(UKfaculty)$ec <- evcent(UKfaculty)$vector > k_ec_top_three <- head(sort(evcent(UKfaculty)$vector, decreasing=TRUE), n=3) > V(UKfaculty)$color <- ifelse(V(UKfaculty)$ec >= k_ec_top_three[3], "red", "white") > plot(UKfaculty)
Jure Leskovec 교수의 홈페이지에서 거대 네트워크 데이터셋 모음을 제공합니다. 그 중 하나의 데이터로 실습을 해보겠습니다. 다운로드나 계산에 걸리는 시간이 너무 오래 걸리면 수업 진행이 어려우니 적당히 작은 데이터로 실습을 하겠습니다. 각자가 홈페이지에 있는 다른 데이터들에 대해서도 연습을 해보시길 바랍니다.
아래 명령을 사용하여 파일을 다운로드 받습니다.
> download.file('http://snap.stanford.edu/data/facebook_combined.txt.gz', destfile='facebook_combined.txt.gz')
다운로드 받은 파일을 아래처럼 DataFrame으로 불러들인 후에 igraph 네트워크로 불러들입니다.
> edgelist <- read.table(gzfile('facebook_combined.txt.gz')) > large_network <- graph.data.frame(edgelist, directed=TRUE)
간단히 네트워크 현황을 보면,
> summary.igraph(large_network)
## IGRAPH DN-- 4039 88234 -- ## attr: name (v/c)
> graph.density(large_network)
## [1] 0.00541
> diameter(large_network)
## [1] 17
> average.path.length(large_network)
## [1] 4.338
> clusters(large_network, mode="weak")$no
## [1] 1
노드가 4039개, 링크가 88234개입니다. 컴포넌트는 1개로, 네트워크 전체가 한 덩어리로 이루어져 있습니다.
그리고 degree 값 분포를 보면 다음과 같습니다.
> deg <- degree(large_network) > df <- as.data.frame(table(deg)) > plot(df)
y축에 log를 씌워서 보겠습니다.
> plot(df, log='y')
네트워크 맵을 그려봅시다.
거대 네트워크에 대해서는 전체 네트워크 맵을 그리기 어려운 경우가 많습니다. 그리기도 어려울 뿐더러 그린다고 해도 맵에서 어떤 해석을 하기 어렵기도 합니다. 하지만 커뮤니티 구조 같은 것이 맵에서 직관적으로 보이는 경우도 있습니다.
> V(large_network)$size <- 2 > V(large_network)$label <- NA > E(large_network)$arrow.size <- 0.2 > E(large_network)$color <- "#33333333" > plot(large_network, layout=layout.fruchterman.reingold)
이 경우는 네트워크 맵에 커뮤니티 구조가 잘 반영되어 드러납니다.
이제 centrality measure들을 살펴봅시다.
> dc <- degree(large_network) > bc <- betweenness(large_network) > cc <- closeness(large_network) > ec <- evcent(large_network, scale=FALSE)$vector
> plot(as.data.frame(table(round(dc, 4))))
> plot(as.data.frame(table(round(bc, 4)), log='y'))
> plot(as.data.frame(table(round(cc, 4)), log='y'))
> plot(as.data.frame(table(round(ec, 4)), log='y'))
위 그래프에서 centrality가 가장 높은 노드 3개는 무엇이 되어야 할까요?
DC가 선택한 노드는 아래와 같습니다.
> V(large_network)$dc <- degree(large_network) > k_dc_top_ten <- head(sort(degree(large_network), decreasing=TRUE), n=10) > V(large_network)$color <- ifelse(V(large_network)$dc >= k_dc_top_ten[10], "red", NA) > V(large_network)$size <- ifelse(V(large_network)$dc >= k_dc_top_ten[10], 2, 0) > V(large_network)$vertex.shape <- ifelse(V(large_network)$dc >= k_dc_top_ten[10], NA, "circle") > plot(large_network, vertex.label=NA, vertex.frame.color=NA, edge.arrow.size=0, layout=layout.fruchterman.reingold)
BC가 선택한 노드는 아래와 같습니다.
> V(large_network)$bc <- betweenness(large_network) > k_bc_top_ten <- head(sort(betweenness(large_network), decreasing=TRUE), n=10) > V(large_network)$color <- ifelse(V(large_network)$bc >= k_bc_top_ten[10], "red", NA) > V(large_network)$size <- ifelse(V(large_network)$bc >= k_bc_top_ten[10], 2, 0) > plot(large_network, vertex.label=NA, vertex.frame.color=NA, edge.arrow.size=0, layout=layout.fruchterman.reingold)
CC가 선택한 노드는 아래와 같습니다.
> V(large_network)$cc <- closeness(large_network) > k_cc_top_ten <- head(sort(closeness(large_network), decreasing=TRUE), n=10) > V(large_network)$color <- ifelse(V(large_network)$cc >= k_cc_top_ten[10], "red", NA) > V(large_network)$size <- ifelse(V(large_network)$cc >= k_cc_top_ten[10], 2, 0) > plot(large_network, vertex.label=NA, vertex.frame.color=NA, edge.arrow.size=0, layout=layout.fruchterman.reingold)
EC가 선택한 노드는 아래와 같습니다.
> V(large_network)$ec <- evcent(large_network)$vector > k_ec_top_ten <- head(sort(evcent(large_network)$vector, decreasing=TRUE), n=10) > V(large_network)$color <- ifelse(V(large_network)$ec >= k_ec_top_ten[10], "red", NA) > V(large_network)$size <- ifelse(V(large_network)$ec >= k_ec_top_ten[10], 2, 0) > plot(large_network, vertex.label=NA, vertex.frame.color=NA, edge.arrow.size=0, layout=layout.fruchterman.reingold)
PR이 선택한 노드는 아래와 같습니다.
> V(large_network)$pr <- page.rank(large_network)$vector > k_pr_top_ten <- head(sort(page.rank(large_network)$vector, decreasing=TRUE), n=10) > V(large_network)$color <- ifelse(V(large_network)$pr >= k_pr_top_ten[10], "red", NA) > V(large_network)$size <- ifelse(V(large_network)$pr >= k_pr_top_ten[10], 2, 0) > plot(large_network, vertex.label=NA, vertex.frame.color=NA, edge.arrow.size=0, layout=layout.fruchterman.reingold)
개별 노드들의 centralitiy 수치는 네트워크상에서 노드들의 역할과 특징을 나타내기도 하지만, 네트워크 전체의 특성을 나타내는데 활용할 수도 있습니다.
Centralization, 중앙성은, 노드들의 중심성을 바탕으로, 해당 네트워크가 얼마나 중심화되어 있는지 판단하는 지표입니다. 중앙화가 많이 된 네트워크는, 중심성이 높은 몇 개의 노드만 제거해도 네트워크가 붕괴할 가능성이 높습니다. [5]
중앙성을 계산하는 식은 다음과 같습니다.
$$
C_x = {\sum_{i=1}^{N} C_x (p_\ast) - C_x (p_i) \over max \sum_{i=1}^{N} C_x (p_\ast) - C_x (p_i)}
$$
> centralization.betweenness(g)
## $res ## [1] 3.5 0.0 0.5 0.0 0.0 ## ## $centralization ## [1] 0.5625 ## ## $theoretical_max ## [1] 24
> centralization.closeness(g)
## $res ## [1] 1.0000 0.6667 0.8000 0.6667 0.5714 ## ## $centralization ## [1] 0.7556 ## ## $theoretical_max ## [1] 1.714
> centralization.degree(g)
## $res ## [1] 4 2 3 2 1 ## ## $centralization ## [1] 0.4 ## ## $theoretical_max ## [1] 20
> centralization.evcent(g)$centralization
## [1] 0.4382