서로 간섭이 덜 되어 보이는 네트워크 링크 그리기

2만개의 노드와 2만6천개 정도의 링크를 구성된 네트워크를 그렸던 작업에 대해 개략적으로 기록해보려 한다.

(데이터는 비공개 보안 데이터였으므로 그림에서 표현했던 텍스트들은 모두 제거했다.)

 

노드들은 1,2,3 계열로 크게 구분되었고, 2,3 계열은 각각 20여개의 그룹으로 구분되었다. 주어진 링크 그대로 그렸더니, 알아볼 수 있는 자연스러운 force 네트워크는 그려지지 않았으며 실타래처럼 뭉쳐져버렸다.

그래서 일단 노드들을 계열과 그룹으로 구분해보기로 했다. 계열은 중심으로부터 떨어진 반지름으로 구분했으며, 하나의 원을 이루는 동일 계열들을 20여개의 그룹으로 분리해서 그룹 각각이 구심점을 갖도록 했다.

 

 

 

네트워크의 정착과 드로잉에 다른 라이브러리를 사용했다

 

 

처음에 노드들을 입력해서 자리를 잡는 과정에서는 아래의 라이브러리를 이용했다.

 

GitHub - vasturiano/force-graph: Force-directed graph rendered on HTML5 canvas

 

이 라이브러리는 아래 코드처럼 d3.js의 force-layout을 기본 엔진으로 활용한다.

GraphThis(document.getElementById('chart-container'))
    .centerAt(center.x, center.y,1000)//window.innerWidth / 2, window.innerHeight / 2, 1000)
    .graphData({ nodes:nodes, links:links })
    .nodeVal((node)=>(node.size))
    .nodeRelSize((node)=>(baseRadius+node.neighbors.length))
    .d3Force("x",d3.forceX((node)=>node.cx))
    .d3Force("y",d3.forceY((node)=>node.cy))
    .d3Force("link", null)
    .d3Force("collide", d3.forceCollide().radius(node=>baseRadius+Math.pow(node.neighbors.length,powLevel)*1.1))
        .cooldownTime(5000)
    .zoom(1)
    .nodeVisibility(false)
    .linkVisibility(false)
    .enableNodeDrag(false)
    .onNodeHover((node) => {
    })
    .onNodeClick((node) => {
    })
    .onZoom(()=> { 
      }
    )
    .onEngineTick(()=>{
      
    })
    .onEngineStop(()=>{
      if (firstExecute) {
        registerEvents();        
        firstExecute = false;
      }
      if (beforeInitialized) {
        makeGroupBorder();
        setCatTextLocation();
        render();
        Graph.pauseAnimation();
        Graph.nodeVisibility(false);
        Graph.graphData({ nodes:[], links:[] })
        beforeInitialized = false;
      }
    })
    .autoPauseRedraw(false);

코드에서 보면 알 수 있지만, 미리 계산된 node.cx, node.cy를 각 그룹의 중심점으로 부여했다.

 

그러면 일정 시간이 지난 후 아래 그림처럼 노드들이 자기 위치를 찾게 된다.

 

 

d3.forceCollide() 부분은 아래 그림처럼 가중치가 다른 노드들을 다른 반지름으로 그린 후, 서로 간섭되지 않게 적절한 버퍼를 만들어주는 내용이다.

 

.onEngineStop() 부분에서는, 5000ms 가 지난 후 위와 같이 점들이 자기 자리를 잡게 되면 엔진을 멈추고 해야할 일을 서술했다.

우선, 그룹들의 둘레에 일정 버퍼를 두고 convex hull을 그렸다. 그리고 마지막으로 링크들을 그려주었다.

 

vasturiano/force-graph 라이브러리는 canvas위에서 동작하는데 이 사례처럼 2만6천개의 노드와 2만여개의 링크를 그릴 경우에는 속도가 많이 느려졌다. 그래서 이 라이브러리는 노드들의 위치를 안정화 시키는 단계까지만 사용했다. 안정화 결과로 얻은 좌표값들을 deck.gl로 넘긴 후 webgl 기반으로 빠르게 그렸다.

 

 

 

모두 Arc로 연결했더니 연결선들이 서로 간섭했다

 

노드와 노드는 arc로 연결했다. 노드들간의 모든 링크들을 그리면 아래와 같은 그림이 나왔다. 노드들을 그룹으로 구분지었음에도 불구하고 선이 너무 많아서 전체 연결의 형상을 알아보기 어려웠다.

다행히 인터랙티브 시각화였고 전부 다 활성화하지 않아도 되었으므로, 클릭을 통해 선택된 그룹만 주변 그룹과의 연결 관계를 표시할 수 있도록 했다.

 

 

그런데 문제는 별로 나아지지 않았다. 다른 계열들을 연결해주는 선들이 다른 노드 위를 지나버렸으므로 링크들이 어떤 그룹들을 이어주는지 식별하기가 어려웠다.

 

 

 

 

경우에 따라 다른 규칙의 링크를 그렸다

 

그래서 식별성을 높이기 위해 전체 네트워크를 구성하는 링크들을 크게 세 가지로 구분했다.

가장 안쪽에서 원의 중심에 해당하는 그룹을 계열1,

그 다음 바깥을 두르는 그룹들을 계열2,

가장 바깥의 그룹들을 계열3이라고 할 때, 

 

그룹 1의 노드들에서 나오는 링크들이나 같은 그룹 안의 링크들은 sine 함수를 이용한 곡선으로 표현했다.

해당 부분을 그린 코드는 아래와 같다.

벡터의 방향을 잡은 후, 길이가 1인 노말벡터로 만들고, 다시 진행량에 따라 그 노말벡터에 길이 값을 곱하거나, 노말벡터를 90도 돌려서 진행 방향에 직각인 벡터를 구성하고 그 벡터에 sine 함수를 적용시켜서 중간 지점에서 가장 직각방향의 변위가 커지도록 했다.

const ls = link.source;
const lt = link.target;

const sx = ls.x;
const sy = ls.y;
const tx = lt.x;
const ty = lt.y;
const path = [];

const st = { x: tx-sx, y :ty - sy};
const stLength = Math.sqrt(st.x * st.x + st.y*st.y);
const stNormal = { x : st.x / stLength, y: st.y / stLength};
const dh = 0.1;

for (let i=0 ; i<=30 ; i++) {
    const t = i / 30;
    const pos = [sx + stNormal.x * t * stLength, sy + stNormal.y * t * stLength];
    const delta = [-stNormal.y * Math.sin(t*Math.PI) * stLength *dh, 
      stNormal.x * Math.sin(t*Math.PI) * stLength *dh];
    pos[0] += delta[0];
    pos[1] += delta[1];
    path.push(pos);
}

 

 

 

 

 

 

 

 

그룹 2와 그룹 2가 이어지는 경우에는 출발점, 중간점, 도착점의 세 점으로 구성되는 베지에 곡선으로 표현했다.

코드는 아래와 같다.

중간점의 경우 전체 원 모양의 중심점에서 출발점과 도착점의 중점을 향하는 벡터를 구성하여 적절한 지점에 만들었다.

const ls = link.source;
const lt = link.target;

const sx = ls.x;
const sy = ls.y;
const tx = lt.x;
const ty = lt.y;
const path = [];

//가운데 점 구하기
const mx = (sx + tx) / 2;
const my = (sy + ty) / 2;
const st = { x: mx - center.x, y : my - center.y};
const stLength = Math.sqrt(st.x * st.x + st.y*st.y);
const stNormal = { x : st.x / stLength, y: st.y / stLength};
const cx = center.x + stNormal.x * radArr[0];
const cy = center.y + stNormal.y * radArr[0];

for (let i=0 ; i<=30 ; i++) {
    const t = i / 30;
    const t1 = 1-t;
    const t00 = t1 * t1;
    const t01 = 2 * t1 * t;
    const t02 = t * t;
    const pos = [t00* sx + t01 * cx + t02 * tx, t00* sy + t01 * cy + t02 * ty];
    path.push(pos);
}

 

 

 

 

가장 바깥의 그룹 3과 그룹 2가 이어지는 경우에는 두 계열 사이를 타고 돌아서 연결되도록 표현했다.

약간의 고민이 있었는데, 처음에는 베지에 곡선으로 접근했었다가 결국 캣멀롬 곡선으로 바꿨다.

  const rr = ls.typePE==2? [1.1, 1.0, 0.9] : [0.9, 1.0, 1.1]; 
  //p1 구하기
  const p1 = { x: sx - center.x, y : sy - center.y};
  const p1Length = Math.sqrt(p1.x * p1.x + p1.y*p1.y);

  //p2 구하기
  const p2 = { x: tx - center.x, y : ty - center.y};
  const p2Length = Math.sqrt(p2.x * p2.x + p2.y*p2.y);

  const r =(p1Length + p2Length)/2;
  p1.x = center.x + p1.x / p1Length * r;
  p1.y = center.y + p1.y / p1Length * r;

  p2.x = center.x + p2.x / p2Length * r;
  p2.y = center.y + p2.y / p2Length * r;

  const p121 = { x : (p1.x*0.7+p2.x*0.3) -center.x, y : (p1.y*0.7 + p2.y*0.3 )- center.y};
  const p121Length = Math.sqrt(p121.x * p121.x + p121.y*p121.y);
  p121.x = p121.x / p121Length * r *rr[0] + center.x;
  p121.y = p121.y / p121Length * r *rr[0] + center.y;

  const p122 = { x : (p1.x*0.5+p2.x*0.5) -center.x, y : (p1.y *0.5+ p2.y*0.5)- center.y};
  const p122Length = Math.sqrt(p122.x * p122.x + p122.y*p122.y);
  p122.x = p122.x / p122Length * r *rr[1] + center.x;
  p122.y = p122.y / p122Length * r *rr[1] + center.y;

  const p123 = { x : (p1.x*0.3+p2.x*0.7) -center.x, y : (p1.y *0.3+ p2.y*0.7)- center.y};
  const p123Length = Math.sqrt(p123.x * p123.x + p123.y*p123.y);
  p123.x = p123.x / p123Length * r *rr[2] + center.x;
  p123.y = p123.y / p123Length * r *rr[2] + center.y;

두 방식 모두 공통적으로 위의 코드처럼 몇 개의 점들을 발생시켰다.

 

 

위에서 코드로 적은 내용을 도식화 하면 아래 그림처럼 된다.

빨간 점들이 발생시킨 참조점들이다. 그 참조점들이 베지에 곡선을 만드는 점들이 되고 그 결과가 푸른색 선들이 된다.

즉, 출발점과 도착점을 선분으로 잇고, 전체 중심점에서 그 선분을 3:2:2:3으로 분할하는 직선들을 그린다. 다시 그 직선들이 일정한 반지름의 원과 만나는 교차점들에 참조점들을 발생시켰다.

 

 

 

참조점들만 곧바로 이어서 그리면 아래 그림처럼 된다. 원의 중심으로부터의 거리를 조금씩 다르게 변화시켰으므로 약간 들쑥날쑥한 선들이 되었다.

 

 

 

베지에 곡선으로 이렇게 연결 선들을 그렸을 때 위와 같은 연결망은 특별히 문제가 없어 보이지만, 아래 그림처럼 또 다시 선들이 다른 노드들 위로 가로지르는 경우가 나타났다.

 

이러저러하게 참조점들을 조정해보다가 결국은, 베지에 곡선을 폐기하고 Catmull-Rom 곡선으로 그리기로 했다.

캣멀롬은 지정한 점들을 반드시 통과하는 곡선을 그려준다.

 

똑같은 그룹의 연결망을 보면 이제 그림은 아래처럼 달라진다.

 

코드들은 아래와 같다.

let tt;
const loopLen = 10;
const dd0 = ls.typePE == 1? 0.5 : 1.5;
const dd1 = ls.typePE == 1? 1.5 : 0.5;
const ls0 = {x:center.x + (ls.x -center.x) * dd0 , y:center.y + (ls.y -center.y) * dd0};
const lt0 = {x:center.x + (lt.x -center.x) * dd1 , y:center.y + (lt.y -center.y) * dd1};


tt = getTT( ls0, ls, p121, p122);
for (let i=0 ; i<=loopLen ; i++) {
  const t = i / loopLen;
  const ttt = tt.y * (1-t) + tt.z * t;
  const pos_ = catmullromPoint(tt, ttt, ls0, ls, p121, p122);
  const pos  = [pos_.x, pos_.y];
  path.push(pos);
}

tt = getTT( ls, p121, p122, p123);
for (let i=1 ; i<=loopLen ; i++) {
  const t = i / loopLen;
  const ttt = tt.y * (1-t) + tt.z * t;
  const pos_ = catmullromPoint(tt, ttt, ls, p121, p122, p123);
  const pos  = [pos_.x, pos_.y];
  path.push(pos);
}

tt = getTT(p121, p122, p123, lt);
for (let i=1 ; i<=loopLen ; i++) {
  const t = i / loopLen;
  const ttt = tt.y * (1-t) + tt.z * t;
  const pos_ = catmullromPoint(tt, ttt, p121, p122, p123, lt);
  const pos  = [pos_.x, pos_.y];
  path.push(pos);
}

tt = getTT( p122, p123, lt, lt0);
for (let i=1 ; i<=loopLen ; i++) {
  const t = i / loopLen;
  const ttt = tt.y * (1-t) + tt.z * t;
  const pos_ = catmullromPoint(tt, ttt, p122, p123, lt, lt0);
  const pos  = [pos_.x, pos_.y];
  path.push(pos);
}

베지에 곡선에서는 출발점과 도착점 사이에 놓인 7개의 점들을 이용했지만, 캣멀롬의 경우 시행착오를 거쳐 점과 점 사이에는 5개의 점들만 이용했다. 캣멀롬 곡선은 어떤 점과 어떤 점 사이를 그릴 때 각각의 점들 바깥쪽으로 연결된 두 개의 점들이 더 필요하므로, 필요한 점들을 새롭게 두개 더 발생시켜서 결국 다시 7개의 점들을 사용했다.

 

 

아래는 캣멀롬 함수 부분이다. 좀 복잡해보여도 컴퓨터는 금새 계산해준다.

const alpha = 1.0;

function tj(tt, pi, pj) {
	return Math.pow(Math.pow((pj.x-pi.x)*(pj.x-pi.x)+(pj.y-pi.y)*(pj.y-pi.y),0.5),alpha)+tt;
}

function getTT(p0, p1, p2, p3) {
	const t0 = 0;
	const t1 = tj(t0,p0,p1);
	const t2 = tj(t1,p1,p2);
	const t3 = tj(t2,p2,p3);
	return {x:t0, y:t1, z:t2, w:t3};
}

function catmullromPoint(tt, t, p0, p1, p2, p3) {

	const A1 = {x : (tt.y-t)/(tt.y-tt.x)*p0.x + (t-tt.x)/(tt.y-tt.x)*p1.x,
              y : (tt.y-t)/(tt.y-tt.x)*p0.y + (t-tt.x)/(tt.y-tt.x)*p1.y};
	const A2 = { x : (tt.z-t)/(tt.z-tt.y)*p1.x + (t-tt.y)/(tt.z-tt.y)*p2.x,
                y : (tt.z-t)/(tt.z-tt.y)*p1.y + (t-tt.y)/(tt.z-tt.y)*p2.y};
	const A3 = {  x : (tt.w-t)/(tt.w-tt.z)*p2.x + (t-tt.z)/(tt.w-tt.z)*p3.x,
                y : (tt.w-t)/(tt.w-tt.z)*p2.y + (t-tt.z)/(tt.w-tt.z)*p3.y};
	const B1 = {  x : (tt.z-t)/(tt.z-tt.x)*A1.x + (t-tt.x)/(tt.z-tt.x)*A2.x,
                y : (tt.z-t)/(tt.z-tt.x)*A1.y + (t-tt.x)/(tt.z-tt.x)*A2.y};
	const B2 = {  x : (tt.w-t)/(tt.w-tt.y)*A2.x + (t-tt.y)/(tt.w-tt.y)*A3.x,
                y : (tt.w-t)/(tt.w-tt.y)*A2.y + (t-tt.y)/(tt.w-tt.y)*A3.y};
	const C  = {  x: (tt.z-t)/(tt.z-tt.y)*B1.x + (t-tt.y)/(tt.z-tt.y)*B2.x,
                y: (tt.z-t)/(tt.z-tt.y)*B1.y + (t-tt.y)/(tt.z-tt.y)*B2.y};
	return C;
}

 

 

 

그래서 결과는,

 

그래서 만든 결과는 아래와 같다.

중간중에 기존 arc 곡선과 swap 시켜서 비교가 되도록 gif를 만들어보았다.

다른 계열간의 연결망이 동시에 나타나도 서로 겹치지 않게 연결해주므로, 그룹간의 연결관계를 좀 더 잘 알아볼 수 있게 되었다.