R과 네트워크 분석(2)

R과 네트워크 분석

저번 포스팅에 이어, 이번 글에서는 네트워크 분석 이론 중 노드간 상관관계를 표현하기 좋은 몇 가지에 대해 더 소개하고 D3.js, vis.js기반의 시각화 패키지들에 대해 다뤄보겠습니다.

 

1. Power Law(멱법칙)와 Scale-free network

Scale-free network는 네트워크의 degree 분포가 power law를 따르는 경우를 말하며, 이러한 특성을 가진 네트워크가 현실세계를 반영한 네트워크라는 가정하고 주어진 네트워크가 fitting하는지 증명하는 것이 power law fitting의 주 목적입니다. 말은 굉장히 어렵게 되있지만 degree란 네트워크에서 객체(노드)가 얼마나 관계(엣지)를 가지는지를 말하기 때문에 결국 말하고자 하는 바는 관계를 적당히 가진 사람들이 제일 많으며, 관계가 지나치게 적거나(0에 가까움) 많은 케이스는 잘 없다는 것입니다. 가장 유명한 SNS인 페이스북의 예를 들어보자면, 페이스북 친구가 하나도 없거나 10만,100만이 되는 계정은 극도로 드물지만 5,60명정도 되는 계정은 매우 많을 것입니다.

R의 igraph패키지를 이용해서 이 scale-free network를 간단히 만들고 테스트 해볼 수 있습니다.

static.power.law.game 함수로 생성된 scale-free network

위 네트워크의 degree분포를 degree.distribution 함수로 구하면 다음과 같이 나옴을 확인할 수 있습니다

Power law에 적합하다고 보이는 네트워크의 degree 분포

앞서 언급한대로, degree 분포의 모습이 멱함수와 유사하게 나옴을 알 수 있습니다.

 

2. Transitivity, Clustering coefficient

네트워크에서 transitivity와 clustering coefficient는 용어만 다를 뿐 같은 말로, 한 노드와 그 노드의 두 이웃이 어떤 관계를 가지고 있는지를 수치적으로 표현하는 방법입니다. 계산은 global일 경우 3 * 삼각형 개수 / 3개의 노드가 연결된 모든 경우로 하며, local일 경우 2* 두 이웃끼리 연결된 경우 / (이웃수 * (이웃수-1))로 계산합니다. 아무래도 수식으로 이해하긴 어렵다보니 예제로 표현해보겠습니다.

노드 A,B,C,D로 구성된 네트워크

위와 같은 네트워크가 있다고 할 때, 삼각형의 개수는 보다시피 {a-b-c}로 이루어진 1개입니다. 그렇다면 3개의 노드가 연결된 모든 경우라는건 어떻게 볼까요? 이는 open triplet과 closed triplet을 합친 값으로 표현되며, open triplet은 다음과 같습니다.

열린 삼각형

b-a-d와 c-a-d는 그림에서 보다시피 닫혀진 삼각형 모양이 아니라 한 변이 '열려'있는 형태입니다. closed triplet의 경우 닫힌 삼각형 형태의 연결로, 아래와 같이 표현됩니다.

네트워크의 총 삼각연결 개수

빨간 삼각형(닫힌 삼각연결)이 3개인 이유는, 열린 경우와 다르게  모든 객체가 연결되있으므로 각 꼭지점을 기준으로 놓고 볼때마다 다른 형태의 연결로 취급할 수 있기 때문입니다. 따라서, 이 네트워크의 transitivity는  3*1 / 5 = 0.6임을 알 수 있습니다.

네트워크의 transitivity

이와 별개로 local clustering coefficient는 각 노드마다 두 이웃을 선별하고, 그 이웃끼리 연결된 경우*2를 이웃수 * 이웃수-1로 나누는 것입니다. 예를들어 위 네트워크에서 a노드는 b,c,d를 모두 이웃으로 가지나 b,c,d중 서로 연결된 경우는 b-c 1개뿐이므로 2*1 / 3 * (3-1) = 1/3으로 나오게 됩니다. LCC는 transitivity함수의 type 인풋을 local로 바꿔주면 구할 수 있으며, 주의할 점은 그래프 객체에 저장된 노드 순서대로 나온다는 것입니다. 예를들어 제가 위에서 생성한 small_g 그래프는 노드를 {a, b, d, c}순으로 가지고 있기에 해당 순서대로 transitivity를 산출합니다

local clustering coefficient산출, d의 경우 이웃이 1개이기에 2*0 / 1*0으로 nan이 생김

이러한 transitivity는 노드와 그 이웃간의 관계를 수치화해서 네트워크가 얼마나 조밀하게 묶여있는지, 혹은 노드가 얼마나 네트워크 안에서 영향력을 발휘하고 있는지를 숫자로 표현해줄 수 있는 역할을 합니다.

 

3. R에서의 네트워크 시각화 : networkD3와 visnetwork

지금까지 사용해온 igraph패키지는 매우 유용하고 plot도 쉽게 할 수 있도록 해주지만 데이터가 커지면 굉장히 지저분하며 대시보드 등 기능 확장을 위해 사용하다보면 줌이나 UI추가면에서 불편한 점이 많다는 것을 알 수 있습니다. 그래서 D3.js나 vis.js기반으로 이루어진 시각화 패키지들을 활용해서 시각화하여 이 점을 보완하는 법에 대해서 설명하고자 합니다.

1) networkD3

networkD3는 D3.js기반의 패키지로, 자체적으로 igraph_to_networkD3라는 함수를 제공하여 igraph객체를 plotting할 수 있는 기능을 제공합니다. 하지만 후술할 visnetwork에 비해 다루기가 직관적이지 못하고 번거로워서, 방법만 간단히 소개한 후 넘어가도록 하겠습니다.

먼저 igraph_to_networkD3에 현재 사용중인 igraph객체인 G를 넣으면 아래와 같이 두 개의 데이터프레임이 담긴 리스트를 얻게 됩니다. links는 노드간의 연결관계, 즉 엣지를 나타내며, nodes는 노드들을 나타냅니다. 

igraph_to_networkD3를 통해 나온 리스트

여기서 nodes 객체에 그룹 변수를 더한후, forceNetwork함수에 넣으면 아래와 그래프를 얻을 수 있습니다.

D3 그래프

2) visnetwork

visnetwork패키지는 위의 networkD3와 유사하게 작동합니다. 먼저 노드 정보를 담을 데이터프레임을 만든 후, 연결정보를 담을 엣지 데이터프레임을 만듭니다.

그리고 visNetwork함수의 nodes와 edges인풋에 해당 데이터를 넣으면, 아래와 같은 그래프가 생성됩니다.

visnetwork로 구현된 그래프

그런데 위 그림에는 문제가 하나 있습니다. 바로 그래프 G는 directed graph인데 화살표가 없어 방향성을 볼 수 없다는 것입니다. 이 문제를 해결하려면 edges 데이터에 arrows 변수를 추가하면 됩니다. 방향은 'to'로 설정해주면 from -> to 방향성을 묘사해줄 수 있습니다.

edges데이터프레임에 arrows옵션 추가

화살표가 추가된 그래프

이제 색상을 추가해보겠습니다. 색상은 nodes 데이터프레임에  color 변수로 조정할 수 있으며, 마지막 노드만 파란색, 나머지는 빨간색으로 받도록 하겠습니다.(색상은 색깔 이름 혹은 color code로 변경할 수 있습니다.)

노드 색상 추가

색깔이 추가된 그래프

만들어보시면 알겠지만, visnetwork의 그래프는 interactive하게 작용할 수 있습니다. 이 때 클릭을 통해 노드의 설명이 보이게 하고 싶다면 nodes에 title변수를 추가해서 해결할 수 있습니다.

노드 타이틀 추가, <br/>은 줄바꿈을 의미합니다.

노드 설명이 붙은 그래프, 클릭하면 설명이 나타납니다

 

이 글에서는 표시할 수 없지만, 직접 예제코드로 실험해보시면 그래프를 클릭하면 유동적으로 움직임을 알 수 있습니다. 이는 vis.js패키지가 physics, 즉 마우스로 주는 힘을 반영해서 움직이도록 해놓기 때문인데요, 이를 수정하려면 visIgraphLayout함수의 physics인풋을 FALSE로 설정해야 합니다.

physics off 코드

마지막으로, visOptions함수를 이용하여 여러가지 옵션들을 추가해줄 수 있는데 이 중 highlightNearest는 클릭한 노드와 연결되있는 주변 노드들만 보여주고 나머지는 회색처리해주는 옵션으로, 복잡한 네트워크에서 해당 노드만 집중해서 보고 싶을 때 큰 도움을 줍니다.

highlight옵션 활성화 

a노드 클릭시 그래프, a와 연결된 노드 및 엣지만 확인 가능

 

마치며

SNS의 파급력이 실생활에서 커지고 알고리즘 처리를 위한 계산능력이 향상되는 만큼, 데이터 분석에서 네트워크 분석의 중요성은 커지면 커졌지 줄어들진 않을 것이라고 생각됩니다. 하지만 분석 기법들이 컴퓨터공학적인 느낌이 강하고 heuristic한 알고리즘들이 많은데다가 그 결과도 시각화 하기 어려워서 의외로 잘 알려지지 않은 부문이 네트워크 분석인 것 같습니다. 이 포스팅과 전 포스팅이 이렇게 중요한 네트워크 분석에 접근해 보는데 조금이나마 도움이 되었으면 하는 바입니다.

 

[컨텐츠 코드]