gimmesilver's blog

Agbird.egloos.com

포토로그



게임 캐릭터 관계 그래프 시각화 데이터분석

네트워크 분석용 라이브러리 중 하나인 igraph(http://igraph.sourceforge.net/)를 사용해서 게임 캐릭터 간 관계를 시각화한 자료이다.
igraph는 C, R, python 버전을 제공하는데 난 R을 사용하고 있고 다른 팀 동료는 python 버전을 사용하고 있다. 
낮은 버전임에도 불구하고 안정적이고 다양한 기능 및 그래프 알고리즘을 지원하고 있어서 각종 네트워크 지표 뽑을 때 꽤 편하지만 오픈 소스라 문서화는 다소 미흡하다(그래도 오픈 소스치고는 잘 되어 있는 편이다).

아래 그림은 두 종류의 온라인 게임에서 캐릭터들의 관계를 각각 그래프로 표현한 것이다. 그래프를 그리는 방식에는 여러 가지 알고리즘이 있는데 여기서는 fruchterman-reingold 알고리즘을 사용했다. 
fruchterman-reingold 알고리즘은 일종의 힘기반(force-based) 알고리즘으로 노드는 척력, 엣지는 인력이 작용한다고 가정하고 반복 계산을 통해 그래프를 배치하는 방식이다. 
초딩 시절 한번쯤 해봤던 유리 판에 철가루를 뿌려놓고 판 아래에 자석을 갖다댔을 때의 모습과 대충 비슷하다고 생각하면 된다. 
물론 아래 그림 그리는데 저런 복잡한 알고리즘을 굳이 알 필요는 없고 igraph에서 제공하는 여러 가지 레이아웃 방식 중 하나를 결정해주기만 하면 된다.

그래프 그리기는 대개의 경우 많은 메모리와 계산 시간을 필요로 하며 엣지의 수가 많아질 수록 소요 시간이 기하급수적으로 증가한다.
예를 들어 엣지의 수가 수천 개 수준이면 1분 이내에 그림이 나오지만 만 개 정도만 돼도 몇 십분이 걸리며 10만 개 정도 되면 퇴근 무렵 돌려놓고 다음 날 아침에 오면 대충 완성되어 있다.
참고로 아래 그림들 중 첫 번째 그림은 엣지 수가 약 45만 개 정도되는데 회사 노트북에서는 out of memory가 나서 집에 있는 PC로 돌렸더니 대략 일주일 정도 걸렸다...(두 번째 그림은 약 30만 개의 엣지인데 사흘 정도 걸렸다.)

어쨌든 아래와 같은 수준의 그래프 시각화는 사실 그 자체에서 어떤 정보를 얻기 위한 목적보다는 흥미나 낚시질의 목적이 좀 더 강하다. 
다시 말하면 여러분은 낚였다...(ㅈㅅ)

<그림 1> 난 이거보면 아이언맨2에 나오는 신물질이 생각난다.

<그림 2> 이건 조커 내지는 세균맨의 느낌이...

덧글

댓글 입력 영역