Vis5

Visualizing Graphs

지금까지는 Table을 spatial channel에 표현하는 방법을 배웠다. 지금 페이지는 Networks & Tree dataset type을 설명한다.

Network

Network는 nodes and links으로 구성되고 node와 link는 attributes을 독립적으로 가진다.

Network을 표현하는 대표적인 시각화 방법은 Node link diagram, Adjacency matrix, 그리고 Enclosure 방법이 있다.

이 세 방법 중에서 scalability, effectiveness, interactivity를 비교를 잘 해야 한다.

Node Link Diagram

Node는 point mark으로 표현되고 link는 line mark으로 표현된다.

Networks와 Trees에 적용 가능

Vertical Node-Link Layout

• Root가 top에 있음
• Vertical spatial position이 depth을 표현함
• Horizontal position은 의미 없음

Radial Layout

Radial은 center에서부터의 거리가 depth을 표현함

• Naiive한 node-link diagram은 hundred nodes 밖에 표현 못 함
• 더 많은 nodes을 표현하려면 aggregate edges을 사용해야 함

Adjacency Matrix

모든 노드들을 vertical / horizontal edges에 놓고 link들은 intersection에서 mark으로 표현된다.

추가적인 정보는 color을 통해서 encoding 될 수 있다.

Networks와 Trees에 적용 가능

Matrix는 undirected graph에서 symmetric이 된다.

이때 단순히 노드들을 놓는다고 해도 해석이 이쁘게 되지 않는다. 이쁘게 display 되기 위해서 노드가 놓이는 순서가 중요한데 이 순서를 결정하는 방법이 seriation이다.

Seriation을 하기 위해서는 loss function을 정의해야 한다.

Linear arrangement cost: 1들을 대각선에 모이게

Moore Stress: 이웃 cell들간의 차이를 최소화 = 비슷한 애들은 clustering 되도록

Robinson property: 대각선에서부터 value가 monotonic하게 감소

이 loss function으로 ordering 방법을 알아내는 것은 비효율적이다. 효율적인 방법으로는 hierarchical clustering을 사용하는 것이다. Clustering을 수행해서 비슷한 애들끼리 모여지는 순서를 얻어서 이를 adjacency matrix에 적용하는 것이다.

또 다른 방법으로는 spectral ordering이 있다. Graph Laplacian을 계산해서 Fidler vector (eigenvector of the second smallest eigen value)을 얻고 node들을 이 값을 통해 sorting 하는 것이다. Deterministic하지만 cluster의 개수가 많아지면 cluster들이 명확하게 구분되지 않는다

TSP-based Ordering : Minimizing the total tour length = minimizing the distance between adjacent rows. 하지만 연속된 노드 간의 distance을 줄이는 알고리즘으로 효과가 제한적이다.

Integer / Combinatorial Optimization 은 수학적으로 최적의 순서를 결정할 수 있지만 적용 가능한 node 수가 30개 이하이다.

NodeTrix Idiom

Node-link diagram은 global structure 파악에 효과적이고 adjacency matrix는 local structure을 파악하는데 효과적이다. 따라서 이 두 특징을 혼합하는 방법론이 제시되었다.

Globally sparse and locally dense

하나의 cluster에서 내부 노드끼리는 연결이 많기 때문에 adjacency matrix을 사용하고 cluster 간의 관계는 node-link diagram으로 표현하는 것이다.

이때 cluster (community)는 비슷한 애들로 정의되는 것이 아니라 연결된 link의 수로 정의된다.

Enclosure

Tree에만 적용 가능 (Cycle 있으면 작동 x)

Containment mark을 통해 hierarchy 을 표현

굳이 roots와 나머지들을 연결할 필요는 없고 parent child만 연결을 한다면 hierarchy을 표현할 수 있음

Treemap은 nested layout을 사용해서 하나의 layout 안에는 그 child들이 들어있고 각 child도 하나의 layout으로 표현되고 ~~~ 반복

이때 neighborhood의 relationship은 어떻게 표현할 수 있을까

예를 들어 지리적으로 가까운 treemap은 가깝게 두는 방법이 있을 수 있다.

State aware Treemap도 존재한다. 시간의 흐름에 따라 데이터가 변하더라도 크기와 배치가 자연스럽게 달라지도록 한다.

GrouseFlock 은 network + tree의 compound network이며 connection mark들은 original network을 표현하고 containment marks은 cluster hierarchy을 표현한다.

Network Tasks

Graph을 통해서 user들은 보통 무슨 task을 수행할까?

Topology-based tasks 특정 노드와 가까운 set of nodes 찾기 몇개의 nodes가 특정 노드와 가까운지

Attribute-based tasks 특정 attribute value을 가지는 node 찾기

Browsing tasks Path 따라가기

이런 task을 쉽게 수행하기 위해서 Graph Drawing : Graph을 2D layout으로 잘 배치하는 알고리즘 연구를 한다.

Graph Drawing

Graph을 잘 표현했는지에 대한 지표는 너무 많아서 이 모든 지표를 다 충족시키기는 어렵다.

• Edge crossing
• Symmetries display
• Minimize Number of bends
• Maximize smallest angle between two edges on same vertex
• Minimize sum of edge length and maximum length of an edge
• Minimize the area of the drawing

또 Graph drawing 알고리즘들은 time complexity가 높다. 따라서 approximation을 사용한다.

이 중 force directed graph drawing은 physical model을 바탕으로 한 방법으로 노드 사이의 힘을 정의해서 nodes/edges에 가해지는 energy을 최소화하는 layout을 찾는 방법이다.

여기서 정의하는 힘은 크게 attractive force와 repulsive force으로 나뉜다.

Attractive force는 연결된 node간, 중심으로 가는 힘이고

Repulsive force는 node 간에 너무 가깝지 않도록 반발하는 힘이다.

특정 노드에 가해지는 힘의 합을 통해 다음 node의 위치가 정해진다.

Force들의 종류를 세분화하면 다음과 같다.

• Link force: 연결된 node들을 target distance만큼 벌어지도록 끄는 힘이다
  • Link force을 정의하는 힘은 target distance L이랑 힘의 strength k이다.
  • L이 작아지거나 k가 커질수록 cluster가 tight해진다.
• Many body force: 모든 node pair들을 repel하는 힘이다.
  • Node들이 모여서 clumping을 방지한다
  • Barnes-Hut 방법을 사용하면 naive한 방법 ($N^2$) 보다 효율적임 $n \log n$
• Centering / gravity: Layout을 중심으로 모으는 힘이다.
  • Centering은 각 node들의 mean이 cluster의 중심에 있도록 하는 힘으로 layout의 shape은 변하지 않는다.
  • Gravity force은 각 node을 center에 있도록 하는 힘이다.
• Collision force: 노드들이 겹치지 않도록 하는 힘이다.
  • 각 노드가 반지름 r을 가진 원이라고 간주하고 서로 닿지 않게 하는 방법이다.
  • 노드의 크기가 data 정보를 담을 때 중요하다.
• Positioning force: 노드들을 line / circle으로 attract하는 힘이다.
  • 각 노드를 target position으로 당기는 방법이다.
  • $v_x += (x_target - x) \times \text{strength} \times a$
  • forceX, forceY으로 나뉜다

Beeswarm plot에서 특히 positioning force와 collision force가 중요하다.

Force directed layout의 장점은 quality가 좋고 구현도 쉽고 flexible하지만 단점은 deterministic 하지 않고 poor local minima 그리고 hairball 문제가 있다. Scale이 너무 높아지면 graph가 뭉친 머리카락처럼 변하는 것이다.

Scalability 문제를 해결하기 위해서 multilevel scalable force directed placement을 사용한다.

초기 그래프 $G_0$ 에서 시작해서 $G_l$ 으로 갈수록 simplify (Graph Coarsening, Edge Collapsing) 하고 제일 simple graph에 force directed layout을 적용해서 node들의 위치를 결정

그 다음 복잡한 그래프로 하나씩 이동하면서 원래 graph까지 복원하면서 layout 개선

작은 graph에서 전체적인 구조를 먼저 결정하고 세부 구조를 추가하는 방식

Graph drawing에서 edge의 방향은 다음 네 가지로 표현된다

• Arrowheads: 말 그대로 화살표로
• Tapered edges: source에서는 두껍게 target으로 갈수록 얇게
• Curvature: 시계방향으로 휘게
• Color Gradient: source는 밝게 target은 어둡게

Edge가 너무 겹칠 대는 edge bundling 방법을 사용한다.

Deep drawing: 고전적인 graph drawing은 시간이 오래 걸리므로 deep learning을 통해서 이 과정을 가속화한다.