3. Community Detection

지난 활동 요약

---

지난 활동을 바탕으로 이번에는 어떤 작업을 할지 정해보았다

지난 번에 Cytoscape에는 어떤 레이아웃들이 존재하는지 파악하고, 각 레이아웃들의 성능을 가볍게 측정해보았다.

그 결과 fcose 레이아웃이 우리의 주제와 가장 적합하다고 생각했고, 성능도 나쁘지 않았다.

=> fcose 레이아웃을 기본으로 사용하고, 다른 레이아웃들은 유저가 선택시 보여줄 수 있도록 하는 방향으로 결정을 내렸다.

이번 활동 요약

---

이번에 해야 할 작업을 크게 2가지로 정했다

1. 각 커뮤니티 별로 다른 색 으로 나타내고,

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

 

Degree에 따라 크기 조절하기

---

Degree가 큰 노드는 크기를 크게 표현해서 인식하기 쉽게 하기 위함

비교적 쉬워보이는 크기를 조절하는 기능부터 도입했다.

쉬워보였던 이유는 Cytoscape.js 에서 기본적으로 제공하는 기능 중에 degree를 측정해주는 기능이 있기 때문이다.

export const styleSheet: StyleType[] = [
  {
    selector: "node",
    style: {
      backgroundColor: (ele): string => ele._private.data.color,
      width: (ele) => {
        const degree = ele.degree();
        const scalingFactor = degree >= 30 ? 10 : 20; // 스케일링 팩터 조정
        const minSize = 20; // 최소 크기
        const maxSize = 80; // 최대 크기

        // Degree에 비례하여 크기를 동적으로 계산
        const size = degree * scalingFactor;

        // 최소 및 최대 크기 적용
        return Math.max(minSize, Math.min(size, maxSize)) as number;
      },
      height: (ele) => {
        const degree = ele.degree();
        const scalingFactor = degree >= 30 ? 10 : 20;
        const minSize = 20;
        const maxSize = 80;

        const size = degree * scalingFactor;

        return Math.max(minSize, Math.min(size, maxSize));
      },
      // Adjust the scaling factor as needed

      label: "data(label)",
      ...
     }

그래프의 스타일을 설정할 수 있는 styleSheet에서 width, height 부분을 수정해주었다.

이전에는 width, height를 상수값으로 고정했었지만, 이제는 degree값을 이용해서 동적으로 설정한다.

단순히 degree에 비례해서 사이즈가 커지도록 하면 degree가 압도적으로 큰 노드가 존재하면 나머지 노드들이 너무 작아지기 때문에 이를 방지하기 위해서 최대 최소 사이즈를 지정했다.

그 결과 이렇게 degree에 따라 크기가 변하는 노드를 만들 수 있었다.

 

커뮤니티별로 노드 색상 다르게 하기

---

커뮤니티를 Detection해서 각 커뮤니티마다 다른 색상을 부여한다

문제는 커뮤니티를 detection해서 노드의 색상을 다르게 지정하는 것이었다.

사전에 커뮤니티를 미리 알 수 있다면 그 커뮤니티에 따라 다르게 색상을 지정하면 되겠지만, 들어오는 데이터에는 Node와 Edge 정보만 존재할 뿐 커뮤니티에 대한 정보는 없었다.

먼저 Cytosacpe에서 기본적으로 커뮤니티를 탐지해주는 기능을 제공하는지를 살펴보았지만, 내부적으로 커뮤니티를 탐지한다고 하더라도 그걸 이용해서 내가 색상을 적용할 수 있는 방법은 찾지 못했다.

챗지피티에게도 물어봤지만, 미리 알고있는 커뮤니티 정보에 따라 다른 색상을 지정하는 방법만을 알려줄 뿐, 커뮤니티를 먼저 detection하고 그 커뮤니티에 따라 다른 색상을 지정하는 방법은 알려주지 않았다.

https://stackoverflow.com/questions/54821322/how-to-set-different-colors-for-each-group-with-cytoscape-js

How to set different colors for each group with cytoscape.js

스택 오버플로우에서 나와 같은 작업을 하기를 원하는 사람을 찾았지만, 이 사람은 부모 노드와 같은 색상을 칠하는 방법을 선택했다.

그런데 우리의 데이터는 양방향 간선이기 때문에 부모 노드라는 개념이 존재하지 않았다.
그렇지만 이 글을 보고 영감을 얻을 수 있었다.

어떻게 하면 각 노드가 같은 커뮤티니에 속해있는지 구분할 수 있을까?

고민끝에 유니온 파인드 알고리즘 이 떠올랐다.

같은 집합에 소속된 노드라면 당연하게 같은 커뮤니티에 속한 노드일 것이다.

//노드 색상 목록
{
  ...
  const colors: string[] = [
    "#ff6961",
    "#77dd77",
    "#e79eff",
    "#84b6f4",
    "#b0f2c2",
    "#ffda9e",
  ];

  let colorIdx = 0;

  const parent: { [key: string]: Node } = {};

  const Find = (nowNode: Node): Node => {
    const parentNode = parent[nowNode.node];
    if (nowNode.node === parentNode.node) return parentNode;
    else return (parent[nowNode.node] = Find(parentNode));
  };

  const Union = (nodeA: Node, nodeB: Node): void => {
    const parentA = parent[nodeA.node];
    const parentB = parent[nodeB.node];

    parent[parentA.node] = parentB;
  };

  lines.forEach((line) => {
    const parts = line.split("\t");

    const sourceId = `${parts[0]}`;
    const targetId = `${parts[1]}`;

    const sourceNode = {
      node: sourceId,
      color:
        parent[sourceId] === undefined
          ? colors[colorIdx++ % colors.length]
          : parent[sourceId].color,
    };

    const targetNode = {
      node: targetId,
      color:
        parent[targetId] === undefined
          ? colors[colorIdx++ % colors.length]
          : parent[targetId].color,
    };

    //만약 부모 노드가 없다면 자기 자신으로 세팅
    if (parent[sourceNode.node] === undefined) {
      parent[sourceId] = sourceNode;
    }
    if (parent[targetNode.node] === undefined) {
      parent[targetId] = targetNode;
    }

    //같은 클러스터가 아니라면 Union
    if (Find(sourceNode).node !== Find(targetNode).node) {
      Union(sourceNode, targetNode);
    }
    ...
  }

  data.nodes.map((nowNode) => {
    const coloredNode = {
      ...nowNode.data,
      color: Find({ node: nowNode.data.id as string, color: "" }).color,
    };
    nowNode.data = coloredNode;
  });

물론 양방향 간선이지만, 한쪽이 부모가 된다고 생각하고 진행했다.

=> 어짜피 같은 집합에 속하는지만 알아내면 되기 때문

 

그렇게 해서 최종적으로 최상위 부모노드의 색상을 따르도록 색상을 설정했다.

노드의 수가 많아도 수천개일 것이라 생각했고,
경로 압축을 했을 때 Find의 시간 복잡도는 상수시간이기 때문에 렌더링 속도에 큰 영향을 미치지 않을 것이라 생각했다.

그 결과 이렇게 커뮤니티에 따라 다른 색상을 띠도록 할 수 있었다.
조금 더 구분이 잘되는 색상들로 지정하면 더 선명하게 클러스터링이 가능할 것 같다.

 

유니온 파인드 알고리즘을 이런 곳에서 사용하게 될 줄은 몰랐다.

이런 방법이 떠올랐다는 것이 뿌듯했고, 실제 적용이 되었다는 것도 신기했다.

이번 프로젝트를 통해 왜 알고리즘을 그렇게 강조하고, 중요하게 생각하는지 조금이나마 알게 되었다.

 

다음 목표

---

1. 기존에 존재하던 웹 페이지를 어떻게 잘 엮어서 migration 할 것인지 고민

2. 어떤 식으로 디자인 을 해야 우리가 구현하는 기능을 잘 사용할 수 있을지 고민