Graph Visualization #

그래프(Graph, Mathmetical Graph)데이터는 저장하는 객체(Node) 및 객체 간의 관계(Edge)를 저장한 데이터로 교통 정보, geometry 정보, 사회 관계망 정보 등과 같은 일반적인 정보부터 분자 정보, 생물 계통 정보, 네트워크 장치 라우터 간의 traffic 관리 등 전문적인 분야까지 널리 사용하고 있다.

그래프 시각화(그래프 가시화, Graph Visualization)는 위와 같은 graph 데이터들을 시각화하는 방법으로, 예전에는 주로 Graph나 간단한 알고리즘의 로직을 설명하는 용도로 사용하거나, 일정량의 데이터를 사용자에게 보여주는 수준이었다. 하지만 컴퓨팅 퍼포먼스가 증가하여 많은 양의 데이터를 저장, 분석하게 되고 최근에는 빅데이터에 대한 이슈가 커지게 되면서, 단순히 많은 양의 데이터를 저장, 분석하는 것뿐만 아니라 많은 양의 데이터를 어떻게 사용자가 볼 수 있을지에 대한 논의도 계속해서 증가하고 있다. 특히 graph 관련 데이터는 N개의 node에 최대 N!개(Directed graph의 경우 N^N)의 edge가 생성될 수 있으며, 이를 어떻게 축약하여 사용자에게 보여주는가에 따라 전체 데이터의 경향에 대해 잘못된 관점을 제시 할 수 있으므로, 이를 어떻게 사용자에게 데이터의 특성을 반영하여 보여 줄 것인가는 중요한 문제 중 하나이다.

Force-Directed Graph(Forced layout) #

그래프 시각화 결과는 어떠한 데이터가 있는가에 따라 생성되는 node, edge 개수가 변경될 수밖에 없다. 그래서 일반적으로 그래프를 시각화 할 때 가장 많이 사용하는 방법(레이아웃)으로 Forced-Directed Graph가 있다. Forced-Directed Graph는 두 전하 간의 전자기력을 계산하는 방식과 유사한 원리를 활용해 각 노드 간의 거리를 지정한다. Forced-Directed Graph에서는 node의 위치가 고정되어 있지 않다. 처음에 node의 위치는 무작위로 뿌려지거나, 몇 가지 간단한 규칙에 따라 임의의 위치에 생성된다. 이후 node의 weight를 이용하여 주변의 node 간에 얼마 이상 떨어져야 하는지 거리를 계산하는데, weight가 클수록 node 간의 간격은 멀어지게 된다. 반대로 edge가 있는 두 노드 간에는 edge의 weight에 따라 값이 더 클수록 두 node 간의 간격이 가까워질 수 있도록 계산한다.

출처 : stack overflow

Forced-Graph는 주변 node들에 의해 위치가 변하게 되므로 각 node의 위치는 고정되어 있지 않다. 또한, 하나의 node에 대해 위와 같은 방식으로 위치를 계산하게 되면 변경된 node 위치가 다른 node에 위치에도 영향을 미치기 때문에 상단의 그림처럼 안정화되기 전까지 그림의 위치를 계속 계산해주어야 한다.

Clustered Graph #

Big Data 시각화 방법의 하나로 그래프 정보를 토대로 clustering 하여 그래프를 생성하는 방법이 있다. Clustered graph는 일차적으로 구성된 그래프 정보를 토대로 연결관계를 계산하여 서로 긴밀하게 연결된 node들끼리 clustering 하는 방법이다. 이러한 그래프는, clustering 된 것끼리 좀 더 가까이 보이도록 하여 인접한 cluster를 한눈에 보이도록 node를 배치하거나, 아예 clustering 된 node들을 하나의 node로 두고 cluster 간의 관계를 표시할 수도 있다.

출처 : ASCR Discovery

출처 : http://veniceatlas.epfl.ch/blog-post-3-clustering-with-nearest-neighbors-applied-to-semi-automatic-transcription/

Multi scale Graph(Multi level Graph) #

위에서 언급한 Clustered Graph를 활용한 고차원적인 시각화 방법으로 Multiscale Graph가 있다. Multiscale Graph의 경우 위 그림에서 clustering을 scale에 따라 압축하여 시각화한다. Scale에 따른 압축은 scale 값이 가장 클 경우(zoom in) 화면에서는 node 및 edge 정보를 화면상에 보여주고, scale이 점점 작을수록(zoom out) weight 값이 작은 node, edge들을 병합하거나 사라지게 하여 각 node의 정보가 아닌 축약된 데이터를 보여주는 방식이다. 이와 같은 방법을 적용하기 위해서는 사전에 데이터를 입력받아 시각화 전에 scale 별로 clustering을 진행하는 전처리 과정이 먼저 수행되어야 한다.

출처 : http://www.martingrandjean.ch/intellectual-cooperation-multi-level-network-analysis/

Geomteric Edge Clustering #

위 방법이 Node를 기반으로 Clustering하였다면, Edge 기반으로 Clustering하는 그래프 시각화 방법도 존재한다. 일반적으로 지리정보를 기반으로 그래프를 구성하는 경우에는 노드의 위치가 고정되어 있으며 노드 간의 연결된 Edge정보는 각 노드에서 이동하는 정보의 양(사람, 물자 등의 이동 정보)을 나타내는 경우가 많다. 이러한 그래프에서는 노드 자체의 정보보다는 각 노드에서 다른 노드로 연결된 Edge가 중요한 의미가 있는데, Node의 위치가 고정이어서 사람이 보기에 다소 복잡하게 표현되므로 Edge를 사람이 효과적으로 알아보게 하기 위한 연구가 많이 진행되고 있다.

출처 : https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/bundling.pdf

위 클러스터링은 Edge의 위치와 방향성이 유사한 Edge들을 찾고 이들을 이를 Mesh 기반으로 묶어 사용자에게 시각화한다. 이 과정에서 다른 방향성을 가지는 Edge들과의 교차점의 위치가 모호해지는 문제가 발생하는데 이를 최소화 하기 위해 Edge들 간의 교차점들을 확인한 후 위치 기반으로 이점들 또한 Clustring 하는 방식을 사용하였다.

Incoming Links #

Related Data Sciences (DataScience 0) #

• Graph

Suggested Pages #

• 0.340 컴퓨터알고리즘
• 0.278 스택
• 0.115 graph-tool
• 0.100 자료구조
• 0.085 Shortest Path Problem
• 0.066 DBMS/Graph DB
• 0.012 파이썬/라이브러리/numpy
• 0.004 DFS
• More suggestions...

Other Posts #

• newer 자료구조
• older pVAC-Seq