[Data Science] 미식축구 경기 네트워크 분석 및 링크 예측

1. 프로젝트 주제 선정

1.1 주제 선정 이유

선정한 데이터는 ‘football’ 데이터셋으로, 대학 내의 미식축구 팀들의 경기에 대한 네트워크를 낸 데이터셋이다. 빅데이터를 이용한 네트워크 분석 및 링크예측은 스포츠 산업에서도 종종 쓰이고 있다. 야구처럼 정확한 타율이 계산되지 않는 미식축구와 같은 스포츠에서는 특히 네트워크 분석 및 링크예측이 중요하게 떠오르고 있다. 상대팀과의 관계를 분석을 통해 선수들의 능력을 평가할 수 있을 것이며, 네트워크 분석을 통해 승패 여부를 보다 쉽게 예측할 수 있을 것이다. 그 선수의 능력을 평가하여 이적료를 결정하고, 그 팀의 가치를 결정해야하는 미식축구에서는 특히 네트워크 분석이 중요하다고 생각된다. 따라서 실제로 수업 내 진행했던 네트워크 분석을 통해 미식축구 팀들의 네트워크 분석을 진행해 보고 싶었고, 더 나아가 링크 예측까지 진행할 수 있는지 및 해당 예측 결과가 의미하는 바는 무엇일지 탐구해 보기 위하여 해당 자료를 분석 데이터셋으로 결정하였다.

 

2. 네트워크 분석

R에서 ‘igraph’, ‘statnet’ 패키지를 이용하여 네트워크 분석을 진행하였다.

본 게시글의 네트워크 분석 과정은 다음과 같다. 데이터 수집, 데이터 구성을 설명한 뒤, 네트워크를 시각화 한다. 이후 네트워크의 degree를 확인하고, 네트워크의 Closeness Centrality (근접 중심성)와 Betweenness Centrality (매개 중심성)을 계산한다. 최종적으로 네트워크 상의 Clique와 Cluster를 확인하고 링크를 예측할 것이다.

 

2.1 데이터 수집

http://www-personal.umich.edu/~mejn/netdata/ 에서 수집한 gml형식의 ‘football’ 데이터셋을 이용하여 분석을 진행하였다.

 

2.2 데이터 구성

데이터는 Undirected Graph로 115개의 node 와, 613개의 Edges 로 구성되어 있다.

 

2.3 네트워크 시각화

football 팀별로의 네트워크를 그래프로 표현하였다. R plot을 이용한 시각화 그림은 [그림 1]로, Gephi를 이용하여 시각화 한 그림은 [그림 2]로 나타냈다.

#필요한 패키지 다운 및 실행
install.packages("igraph")
install.packages("statnet")
library(igraph)
library(statnet.common)

#데이터 읽기 선택지 3_확장자가 gml
g <- read.graph("C:\\Users\\my\\Desktop\\network_data\\football.gml")
plot(g, vertex.label.cex=1)

g plot 살펴본 결과

[그림 1] R plot                                                        [그림 2] Gephi

 

2.4 네트워크 중심성 분석

2.4.1 Degree 계산 및 네트워크 그래프 작성

네트워크의 degree 10개를 [그림 3]으로 나타냈다. 네트워크 안에서 관계의 정도가 높을수록 degree값이 커지는 것을 확인할 수 있으며, 이를 직관적으로 나타내기 위해 노드의 크기를 변화시켰다. 이를 R과 Gephi 두개의 tool을 이용하여 나타내어 보았다. 각각 [그림 4]와 [그림 5]를 통해 확인할 수 있다.

# 노드 연결 수(Degree)
degree<-igraph::degree(g,mode="out")
plot(g)
degree_vcount<-vcount(g)
degree_centralization<-centralization.degree(g)
V(g)$size<-igraph::degree(g)*10 ## 노드 크기 키우기
plot(g, vertex.label.cex=1)
degree

 

[그림 3] 각 label별 계산된 Degree 값

[그림 4] R로 나타낸 Degree값에 따른 네트워크 그래프

[그림 5] Gephi로 나타낸 Degree값에 따른 네트워크 그래프

 

2.4.2. Closeness Centrality (근접 중심성) 계산 및 네트워크 그래프 작성

네트워크의 근접 중심성 분석을 해보았다. 이는 각 노드 간의 거리를 근거로 중심성을 측정하는 방법이다. 직접적으로 연결된 노드만 계산하는 Degree와는 달라, 간접적인 연결 노드까지 계산하는 방법이다. 근접 중심성 분석은 근접 중심성이 높을수록 색을 더 진하게 표시하며, 이는 [그림 6]을 통해 확인할 수 있다.

# 근접 중심성중심성(closeness)
clo <- igraph::closeness(g)
clo.score<-round((clo-min(clo))*length(clo)/max(clo))+1
clo.colors<-rev(heat.colors(max(clo.score)))
# Degree 크기에 따라 노드 크기 변화
V(g)$color<-clo.colors[clo.score]
plot(g, vertex.label.cex=1)

[그림 6] Closeness Centrality 분석에 따른 네트워크 그래프

 

2.4.3 Betweenness Certrality (매개 중심성) 계산 및 네트워크 그래프 작성

네트워크 내에서 한 노드가 담당하는 중간 매개자 역할의 정도가 어느정도 되는지 매개 중심성을 계산한다. 특정 노드가 다른 노드들과의 최다 경로 상에 있을수록 매개 중심성이 크게 나타나고, 이를 시각적으로 알아보기 위해 매개 중심성이 클수록 더 진한색으로 표현하여 [그림 7]과 같이 나타냈다.

# 매개 중심성중심성(betweeness)
btw<-igraph::betweenness(g)
btw.score<-round(btw)+1
btw.colors<-rev(heat.colors(max(btw.score)))
V(g)$color<-btw.colors[btw.score]
plot(g, vertex.label.cex=1)
btw

[그림 7] Betweenness Centrality 분석에 따른 네트워크 그래프

 

2.5 네트워크 클러스터

네트워크 상에서 clique와 클러스터를 확인한다. Clique의 크기를 확인하고, 가장 큰 clique를 선정한다. 선정된 clique를 네트워크 그래프에서 황금색으로 표시할 것이다. 이는 [그림 8]을 통해 확인할 수 있다. 이를 통해 황금색으로 표시된 노드는 다른 노드에 비해서 더욱 관계의 정도가 깊다는 것을 알 수 있을 것이다. 현재 football팀들은 모두 황금색으로 표현되므로, 모든 팀들과 서로 연결되어 있고, 관계가 동일하게 깊음을 알 수 있다.

# density
graph_density<-graph.density(g)
plot(g)

# cluster
clusters<-clusters(g)
clusters(g)$csize
# clique
clique<-cliques(g) ## clique 리스트
clique_length<-sapply(cliques(g), length) ## clique의 숫자를 보여줌
largest_clique<-largest_cliques(g) ## 가장 큰 clique 도출

# 원 그래프에 clique를 황금색으로 표시
vcol <- rep("grey80", vcount(g))
vcol[unlist(largest_cliques(g))] <- "gold"
plot(as.undirected(g), vertex.label=V(g)$name, vertex.label.cex=1, vertex.color=vcol)

[그림 8] Clique

 

3. 링크 예측

실제로 연결된 네트워크를 분석하는 데에서 더 나아가 본 게시글은 하나의 노드가 다른 어떤 노드와 연결될 확률을 예측했다. 즉 존재하지 않는 노드 사이의 관계를 예측하고 판단할 수 있다는 것이다. 방대한 데이터 속에서 살아가는 요즘에는 네트워크 사이의 관계를 도출하는 중요성이 증대되고 있다.

본 게시글에서는 거리 기반의 링크 예측을 수행한다. 먼저 hierarchical random graph model로 계층 형태의 그래프를 먼저 작성하고, 연결되지 않은 edge를 확률로 계산하여 연결될 가능성이 높은 edge를 제시하는 방식이다. 거리가 가까운 노드일수록 하위 층부터 연결되어 있고, 거리가 먼 노드들은 상위 층에서 연결됨을 알 수 있다. 이 결과를 csv파일로 저장하였으며, 저장된 파일의 내용 중 일부를 [그림 9]에 나타냈다.

# Link Prediction
predicted <- predict_edges(g)
V(g)$name
a1 <- predicted$edges
a2 <- predicted$prob
a3 <- cbind(a1, a2)
colnames(a3) = c("from", "to", "prob")
write.csv(a3, "link_prediction.csv")

[그림 9] 링크 에측 결과

링크 예측 결과를 살펴보니, 3번 노드와 12번노드가 연결될 확률은 0.2677, 2번 노드와 3번 노드가 연결될 확률은 0.246118, 3번 노드와 8번 노드가 연결될 확률은 0.219546으로 나타났다. 이는 3번 노드와 12번 노드가 연결될 가능성은 26.7%, 3번 노드와 8번 노드가 연결될 가능성은 21.9% 라고 해석할 수 있다.

 

4. 결론

본 레포트에서는 네트워크 분석 및 링크 예측을 수행하였다. Degree, Closeness Centrality, Betweenness Centrality를 계산하여 네트워크를 분석하고, cluster를 통해 주 clique를 확인해 보았다. 네트워크 분석 및 예측 수행 결과, 실제 데이터 간의 존재하는 네트워크를 다양한 측면에서 분석해 볼 수 있었고, 이를 통해 존재하지 않는 네트워크에 한해서 연결될 수도 있는 가능성을 계산하여 링크를 예측해 볼 수 있었다.

 결과를 보았을 때, 현재 네트워크가 직접적으로 연결되어 있지 않은 3번 노드와 12번 노드 사이의 연결 가능성을 예측할 수 있었다. 예측하기 힘든 미식축구와 같은 스포츠 분야에서 이처럼 네트워크 분석 기법 및 링크 예측을 이용함으로써 새로운 네트워크를 발견하고, 이를 통해 선수의 능력, 승률 등을 예측함으로써 스포츠 산업의 가치를 높일 수 있을 것이다.

 

마치며...!

Clique를 확인해 보았을 때, 모든 football 팀은 서로 연결되어있고, 관계가 동일하게 깊다고 나타난 것이 조금 의심스럽다. 내가 분석을 잘했는지에 대한 의구심이 든다 ㅠ 네트워크 분석 또한, 다양한 회사의 인사팀 혹은 프로젝트를 관리하기 위한 시스템으로 많이 쓰일 것 같다.  실무에서 사용될 때, 내가 스스로 구현할 수 있을 때까지 공부해봐야겠다 다. :)