2. Layout 탐색 및 성능 측정

지난 논의에서 우리는 일단은 Cytoscape를 사용하는 것으로 확정지었고,
그러기 위해서는 데이터가 많아졌을 때 느려지는 현상에 대한 방안을 떠올려야 했다.

간단하게 2가지의 선택지를 생각할 수 있다.

 

1. 서버에서 그림을 그려서, 이미지 파일만 클라이언트측으로 전송한다.

2. 클라이언트측에서 그림을 그리되, 최적화해서 그리는 방법을 모색한다.

 

1번의 경우 클라이언트측에 부담을 덜어줄 수 있다는 장점이 있지만, 대신 사용자가 노드를 끌어다가 움직인다던가의 상호작용은 불가능할 것이다.

2번의 경우 클라이언트의 브라우저에 부담이 가지만, 상호작용이 가능하다는 것이 장점이다.

 

그런데 조교님의 요구사항으로는 상호작용이 가능해야 했기 때문에 2번 으로 방향성을 잡았다.

 

Layout

---

지난 번 시연에서는 Cytoscape.js에서 기본적으로 제공하는 "breadthfirst (너비우선)" 레이아웃을 적용해서 보여드렸다. 

breadthfirst

• 하지만 breadthfirst의 경우 데이터의 양이 많아지면 개별적인 노드를 알아보기 힘들다는 문제가 발생한다.

 

이번에 우리의 미션은 데이터의 양을 조절 하면서, 제공되는 레이아웃들 중 많은 데이터를 표현하기에 적절한 레이아웃을 탐색하고,
각 레이아웃마다의 렌더링 속도를 측정 하는 것이다.

 

사이즈 변경 & 필터 구현

---

데이터의 사이즈를 변경할 수 있는 버튼과, 특정 키워드를 필터링할 수 있는 기능을 만들었다

• 일단 현재 서버와 연동해서 작업을 하는 게 아니기 때문에, 모든 데이터를 파싱해서 저장해두고 사용한다.
• 그렇기 때문에 데이터 사이즈별로 성능을 측정하기 위해서 버튼을 생성했다.

 

리액트를 원래 사용해봤기 때문에, 버튼을 만드는데는 크게 문제가 없었지만 데이터가 변경되었을 때 그래프만 다시 렌더링하는 등의 Cytoscape 관련 기능을 사용하는 것이 조금 까다로웠다.

react-cytoscapejs

다행히 리액트에서 cytoscape를 사용하기 편하게 해주는 라이브러리가 있어서, 그나마 수월했다.

 

또한 로딩 컴포넌트를 넣고 싶은데 어디서 isLoading state의 값을 true로 바꾸고, false로 바꿔야 할지도 cytoscape 문서를 찾아보며 지정했다.

  const [layout, setLayout] = useState({
    name: "breadthfirst",
    ...
    ready: () => {
      setIsLoading(true);
    },
    stop: () => {
      setIsLoading(false);
    },
  });

레이아웃을 run시킨 다음 ready, stop 시점에 동작할 함수를 지정할 수 있기 때문에 이를 이용해서 로딩을 구현할 수도 있었다.

 

Layout 비교 및 성능 측정

---

Cytoscape.js 에서 기본적으로 제공하는 레이아웃들과, 설치해서 사용할 수 있는 레이아웃을 찾아보았다.

 

1. Circle

: 모든 노드를 원형으로 배치하는 단순한 레이아웃. 노드 간의 관계는 덜 강조되지만, 모든 노드가 동등하게 시각화된다.

 

2. Grid

: 노드를 균일한 격자 패턴으로 배치하는 레이아웃. 시각적 질서가 중요한 경우에 적합하며, 노드 간의 관계보다는 노드 자체에 초점을 맞춘다.

 

3. Breadthfirst 

: 너비 우선 탐색(breadth-first search) 알고리즘을 사용하여 노드를 배치하는 레이아웃.

• 트리나 계층적 구조에 적합하다.
• 부모-자식 관계를 명확하게 표현하는데 적합하다.

 

4. Preset

: 이미 정의된 위치에 따라 노드를 배치한다. 노드의 위치가 미리 지정되어 있는 경우에 사용.

• cytoscape.js에서는 position 속성을 이용해서 사전에 위치를 지정할 수 있다.

 

5. Concentric

: 노드를 동심원 형태로 배치한다. 중심에서부터 멀어질수록 노드들이 원의 레벨을 따라 배치된다.

• 중심에서부터의 거리나 다른 기준에 따라 노드를 그룹화할 수 있다.

 

6. Dagre

: Directed Acyclic Graph(DAG)를 기반으로한 레이아웃. 노드 간의 방향성을 고려하여 계층적으로 배치.

• 방향성이 있는 그래프에 적합

 

7. Cose

: Compound Spring Embedder(CoSE) 알고리즘을 사용하여 레이아웃을 구성합니다.

• CoSE 레이아웃은 ‘Force-Directed layout’을 기반으로한 레이아웃.
• Force directed layout은 그래프 시각화의 기법 중 하나로, 노드끼리는 척력을 엣지로 연결된 노드끼리는 인력을 적용시키는 방법.
• 알고리즘의 적용 결과가 화합물의 형태와 비슷하고, 노드끼리의 인력을 용수철 형태로 적용하기 때문에 Compound Spring Embedder 레이아웃이라 불리는 것으로 예상된다.

 

아래의 영상을 보면, 어떤 식으로 적용되어 가는지 알 수 있다.

 

 

8. Fcose

: Fase CoSE 레이아웃으로, 이름에서 알 수 있듯이 CoSE 레이아웃에서 파생되었다.

• FCoSE는 CoSE보다 빠른 것이 특징인데, 어떻게 가능할까?
  • 데이터 구조와 알고리즘의 개선
    • fcose는 내부적으로 사용하는 데이터 구조와 알고리즘을 최적화하여 더 빠른 성능을 제공한다
    • 힙(heap) 구조를 사용하여 노드 간의 우선순위를 관리하거나, 계산 중에 변경되는 요소들을 효율적으로 업데이트
  •  병렬 처리와 캐시 최적화
    • 현대의 컴퓨팅 환경에서는 병렬 처리와 캐시 최적화가 중요한 요소가 된다.
    • fcose는 이러한 요소들을 고려하여 설계되어, 멀티코어 프로세서의 이점을 취하고 메모리 접근을 최적화한다

 

9. Avsdf

: Average Stress Directed Force Layout. 노드들 사이의 스트레스(즉, 거리의 불균형)를 최소화하면서 노드를 배치한다.

 

10. Klay

: 계층적 구조를 가진 그래프에 사용되며, 노드를 여러 레벨로 나누어 각 레벨을 계층적으로 표시한다.

 

11. Cola

: 제약 조건 기반 레이아웃. 노드 간의 거리, 방향성, 각도 등을 제약 조건으로 설정하여 이러한 제약 조건을 만족하는 레이아웃을 생성한다.

• Cola 역시 Force-Directed layout 을 기반으로 한다.

Cola 레이아웃의 적용 과정

1. 초기 배치 : 노드들은 초기에 무작위로 배치되거나 특정 패턴을 따라 배치된다.
2. 제약 조건 설정 : 노드 간의 관계, 거리, 방향 등에 대한 제약 조건을 설정. 이는 그래프의 위상이나 의미를 반영하는데 중요하다. 3. 힘의 계산 : 각 노드는 다른 노드와의 관계에 따라 서로를 밀어내거나 당기는 힘을 가진다. 이 힘은 제약 조건을 만족하기 위해 계산된다.
4. 평형 상태 도달 : 알고리즘은 노드들이 서로에 대해 힘을 가하며 움직이다가, 제약 조건에 의해 정의된 최적의 위치에 도달할 때까지 계속된다.
5. 반복 조정 : 노드들이 평형 상태에 도달하면, 알고리즘은 종료되거나 사용자가 요구하는 동안 반복.

 

결론

---

지금까지 살펴본 것을 바탕으로 결정

• 그래프의 형태나, 레이아웃을 그려내는 속도를 봤을 때, FCoSE 레이아웃 이 가장 적합한 것 같다.
• 우리의 목표가 감염병에 대응하기 위한 네트워크를 시각화하는 것이기 때문에,
• 엣지가 많이 연결된 노드를 중심으로 모여지는 형태가 가장 적합하다.
• 그리고 그러한 노드가 대응의 중심지가 될 것이다.

 

다음 목표

그렇다면 그러한 중심지를 더 뚜렷하게 확인하기 위해서, 이제 우리가 해야 할 것은

1. 각 커뮤니티 별로 다른 색으로 네트워크를 나타내고,

2. Degree가 큰 노드일수록 노드의 크기를 크게 표현하는 것이다.

 

Reference

---

https://www.youtube.com/watch?v=Juq4Rl_x7Bw