Modern Data Science with R_Cpt16

16. Network science

16.1. Introduction to network science

16.1.1. Definitions

네트워크 이론의 뿌리는 그래프 이론이라는 수학 분야에 있다.

1. 그래프 G=(V, E)에서 V는 꼭지점(vertices)의 집합이고 E는 노드 간의 가장자리(Edges), 즉 연결의 집합이다.
   
2. 그래프의 연결(E)은 방향이 있을수도, 없을수도 있다. 차이점은 관계가 상호적인지 일방적인지이다.
   
3. 연결선 E에 가중치가 부여될 수 있다. 가중치가 표시되지 않은 경우, 모든 가중치를 1로 설정하는 것과 같다.
   
4. 경로는 두 꼭짓점을 잇는 일련의 연결이다. 경로가 있는 경우 반드시 하나의 최단 경로가 있으며, 엣지 수나 가중치의 합에따라 달라진다.
   
5. 그래프의 지름은 두 꼭지점 사이에서 가장 긴 경로의 길이다.
   
6. 일반적으로 그래프에는 좌표가 없다. 즉, 그리는 올바른 방법은 없지만 몇 가지 알고리즘이 존재한다.
   

• Centrality, 중심성: 어떤 노드를 중앙에 위치시킬 것인가.
  ++ 1. Degree centrality, 차수중심성: 더 많은 연결을 가지는 노드를 더 높은 순위에 두는 것
  ++ 2. Betweenness centrality, 매개중심성: 같은 점 s와 t사이를 지나는 \(최단경로의 수/엣지의 수\)로 판단하는 것
  ++ 3. Eigenvector centrality, 아이겐벡터중심성

16.2. EX: Six degrees of Kristen Stewart

16.2.1. Collecting Hollywood data

IMDb의 배우를 노드로 하여 할리우드 네트워크를 만들어보자. 네트워크가 너무 커질 수 있으므로 100,000 rating 이상의 2012년부터의 장편영화로 제한하고 각 영화의 상위 20개 역할만 고려하기로 한다.

library(mdsr)
db <- src_scidb("imdb")
sql <-
  "SELECT a.person_id as src, b.person_id as dest,
  a.movie_id,
  a.nr_order * b.nr_order as weight,
  t.title, idx.info as ratings
  FROM imdb.cast_info a
  CROSS JOIN imdb.cast_info b USING (movie_id)
  LEFT JOIN imdb.title t ON a.movie_id = t.id
  LEFT JOIN imdb.movie_info_idx idx ON idx.movie_id = a.movie_id
  WHERE t.production_year = 2012 AND t.kind_id = 1
  AND info_type_id = 100 AND idx.info > 125000
  AND a.nr_order <= 20 AND b.nr_order <= 20
  AND a.role_id IN (1,2) AND b.role_id IN (1,2)
  AND a.person_id < b.person_id
  GROUP BY src, dest, movie_id"

E <- DBI::dbGetQuery(db$con, sql) %>%
  mutate(ratings = as.numeric(ratings))

glimpse(E)

Rows: 11,344
Columns: 6
$ src      <int> 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139, 3139,…
$ dest     <int> 131060, 415839, 913049, 1035060, 1395260, 1414112, 1547500, 1548964, 1563748, 21785…
$ movie_id <int> 3979041, 3979041, 3979041, 3979041, 3979041, 3979041, 3979041, 3979041, 3979041, 39…
$ weight   <int64> 153, 255, 204, 272, 340, 68, 17, 306, 102, 136, 85, 51, 170, 323, 221, 238, 119, …
$ title    <chr> "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud", "Mud",…
$ ratings  <dbl> 146464, 146464, 146464, 146464, 146464, 146464, 146464, 146464, 146464, 146464, 146…

코드 내에 가중치 변수를 계산한 것을 볼 수 있는데, 여기서 가중치는 배우가 크레딧에 등장하는 순서를 기준으로 한다.

nrow(E)

[1] 11344

length(unique(E$title))

[1] 61

E %>%
group_by(movie_id) %>%
summarize(title = max(title), N = n(), numRatings = max(ratings)) %>%
arrange(desc(numRatings))

쿼리 결과, 61개 영화간에 11,344개의 연결이 생성되었다. 배트맨: 더 다크나이트 라이즈가 가장 많은 사용자 평가를 받은 것을 확인할 수 있다. 다음으로 각 노드에 대한 정보를 수집해야한다. 이 경우, 배우의 이름과 IMDb식별자만이 필요하다.

actor_ids <- unique(c(E$src, E$dest))
V <- db %>%
  tbl("name") %>%
  filter(id %in% actor_ids) %>%
  select(id, name) %>%
  rename(actor_name = name) %>%
  collect() %>%
  arrange(id)

glimpse(V)

Rows: 1,115
Columns: 2
$ id         <int> 3139, 6388, 6897, 8462, 16644, 17039, 18760, 28535, 33799, 42958, 44858, 45167, …
$ actor_name <chr> "Abbott Jr., Michael", "Abkarian, Simon", "Aboutboul, Alon", "Abtahi, Omid", "Ad…

16.2.2. Building the Hollywood network

R의 네트워크 분석을 위한 패키지는 igraph와 sna다. 예제에서는 igraph를 사용하며, 연결과 방향을 지정하고 꼭지점에 대한 정보를 추가한다.

library(igraph)

g <- graph_from_data_frame(E, directed = FALSE, vertices = V)
summary(g)

IGRAPH fa89a8e UNW- 1115 11344 -- 
+ attr: name (v/c), actor_name (v/c), movie_id (e/n), weight (e/n), title (e/c), ratings
| (e/n)

요약 결과 1,115명의 배우와 11,344개의 연결이 있음을 알 수 있다. 보통 첫번째 꼭지점 속성은 이름이지만, 더 많은 정보를 제공할 수 있는 IMDb레이블을 유지해보고자 한다.

g <- set_vertex_attr(g, "imdbId", value = V(g)$name)
plot(g, edge.color = "lightgray", vertex.size = 2, vertex.label = NA)

이 경우, 한 배우가 여러 영화에 출연했다면 다른 배우들과 더 많은 인연을 맺는 것이 당연하기 때문에 중심에 위치하는 경향이 있다. 이를 degree centrality로 확인할 수 있다.

g <- set_vertex_attr(g, "degree", value = degree(g))

as_data_frame(g, what = "vertices") %>%
  arrange(desc(degree)) %>%
  head()

Cranston, Bryan이 가장 높은 차수중심성을 갖는 결과가 출력되었다.

getMovies <- function(imdbId, E) {
  E %>%
    filter(src == imdbId | dest == imdbId) %>%
    tally(~ title, data = .)
}

getMovies(502126, E)

title
                              Argo                        John Carter 
                                19                                 19 
Madagascar 3: Europe's Most Wanted                       Total Recall 
                                19                                 19 

Cranston은 이 4편의 영화에 모두 출연했다. degree를 플롯을 통해 살펴보자.

ggplot(data = data.frame(degree = degree(g)), aes(x = degree)) +
  geom_density(size = 2)

degree의 분포가 고르지 않은 모습이다. 수정을 위해 igraph의 플롯 대신 ggplot2로 직접 그래프를 그리기 위해 ggnetwork 패키지를 사용해보자.

library(ggnetwork)

g_df <- ggnetwork(g)
hollywood <- ggplot(g_df, aes(x, y, xend = xend, yend = yend)) +
  geom_edges(aes(size = weight), color = "lightgray") +
  geom_nodes(aes(color = degree), alpha = 0.6) +
  scale_size_continuous(range = c(0.001, 0.2)) +
  theme_blank()

hollywood +
  geom_nodetext(aes(label = gsub(", ", ",\n", actor_name)),
                data = subset(g_df, degree > 40))

ggnetwork()함수는 igraph 오브젝트를 데이터프레임으로 변환한다.

16.2.3. Building a Kristen Stewart oracle

차수중심성은 edge의 가중치를 고려하지 않는다. 주연 배우를 통한 경로를 강조하려면 betweenness centrality, 매개중심성을 고려한다.

g <- g %>%
  set_vertex_attr("btw", value = igraph::betweenness(g, normalized = TRUE))

get.data.frame(g, what = "vertices") %>%
  arrange(desc(btw)) %>%
  head()

Cho, John의 매개중심성이 가장 높고, 차수중심성은 Nighy, Bill이 Cho, John과 동시에 가장 높다. John Cho를 중심에 두고 ’Cho_번호’를 고려할 경우, 다른 배우와의 거리를 계산할 수 있다.

jc <- V(g)[actor_name == "Cho, John"]
bn <- V(g)[actor_name == "Nighy, Bill"]

p <- shortest_paths(g, from = bn, to = jc, weights = NA, output = "both")
vertex_attr(g, "actor_name", index = p$vpath[[1]])

[1] "Nighy, Bill" "Cho, John"  

현재 예시의 두 배우는 거리가 1이다. 이러한 최단 거리는 유일한 것은 아니다.

length(all_shortest_paths(g, from = jc, to = bn, weights = NA)$res)

[1] 1

하지만 본 예시에서는 유일한 최단거리로 나타나고 있다. 항상 최단 거리가 유일하진 않다는 것을 알아야한다.

diameter()는 가장 멀리 떨어져있는 두 배우의 거리를 나타낸다.

diameter(g, weights = NA)

[1] 10

eccentricity()는 이심률을 나타낸다.

eccentricity(g, vids = jc)

427111 
     7 

여기서 Cho, John과의 이심률이 7이라는 것은, Cho, John과 거리가 7이상 떨어진 배우가 없다는 것을 의미한다.