10. Louvain Algorithm 적용 및 로그인 구현

이번 활동 요약

---

지난 번에 유니온 파인드의 사용으로 발생한 문제점을 해결하고자 새로운 알고리즘을 도입했다

이전에는 커뮤니티를 탐지하기 위해서 Union-Find 알고리즘을 사용했다.
처음엔 획기적인 생각이라고 여겼지만, 데이터가 많아지다보니 문제가 발생했다.
데이터가 많아지다보니 임의의 두 데이터 간에 어떻게든 타고 타고 연결이 되어 있었고, 그러다보니 Union-Find로 집합을 찾았을 때는 모든 데이터가 하나의 집합에 소속된 것으로 인식된다는 문제 가 있었다

 

Modularity

---

네트워크 내의 커뮤니티가 얼마나 모듈화 되어 있는가 를 정량적으로 나타내기 위한 값

• 지난 미팅때 조교님이 Modularity 알고리즘을 한번 알아보라고 추천해주셨다
• Modulairty는 커뮤니티 내부에 펼쳐져 있는 링크들이 무작위적인 연결들과 비교했을 때 얼마나 더 강한지  정량화하는 값이다
• Modularity Q를 구하는 식은 위와 같다
• 요약하자면, 커뮤니티 내에 얼마나 많은 연결성이 있는지를 나타내는 값이다
  • 그렇기 때문에 커뮤니티가 이미 설정되어 있을 때 구할 수 있는 값이다
• 무작위적인 연결의 상황과 비교를 했을 때, 이 차이가 클수록 원래의 커뮤니티가 강한 연결성을 갖는다는 의미로 해석할 수 있다

 

Louvain Algorithm

---

기존의 Modularity 기반 알고리즘들의 단점을 극복하기 위해서 제시된 대안

• 기존의 Modularity 기반 알고리즘들은 Modularity를 계산하기 위해서 너무 많은 시간이 소요된다는 문제가 있었다
• 이 계산을 최적화한 Greedy 알고리즘은 인식하는 커뮤니티의 크기가 너무 커진다는 문제를 갖고 있다
  • 그렇기 때문에 기존에 우리가 갖던 문제를 해결할 수 없을 것이라 생각했다
• 이러한 문제들을 해결하기 위해서 Louvain Algorithm이 고안되었다
  • 이름은 논문의 저자가 벨기에의 Louvain 대학 출신이라서 그렇게 지었다고 한다

 

Method

---

Louvain Algorithm의 진행 과정

• Louvain Algorithm은 두가지 Phase의 반복 으로 구성된다

 

Phase 1

• 처음에는 각각의 Single Node가 하나의 커뮤니티라고 생각하고 시작한다
• 하나의 Node를 원래의 Community에서 빼어내어 인접한 Community에 재배치 하였을 때의 Modularity의 변화를 측정한다
• 측정값을 기준으로, Modularity가 가장 큰 폭으로 상승하는 Community에 Node를 배속시킨다
  • Modularity가 크게 변했다는 것은 다른 Community에 배속시켰을 때 더 모듈성이 커졌다는 의미이다
• 이 과정을 어떠한 변화도 일어나지 않을 때까지 수행한다

 

Phase 2

• Phase 2에서는 Phase 1에서 인식한 커뮤니티를 하나의 Super Single Node로 생각한다
• 이때 Community 내부 Link의 Weight는 자기 회기 상태(Self Loop)의 Link로, Community간에 연결되어 있던 Node간의 Link Weight는 합쳐서 하나의 Link로 생성한다
  • 위의 예시에서 민트색(?) 노드들이 합쳐져서 하나의 Super Single Node가 되었고, Self Loop가 생성되었다
  • 이때 (11, 13), (13, 11) 이렇게 연결이 되어 있던 것을 하나로 합쳤기 때문에 2의 Weight를 갖는다
• 이 새롭게 변형한 Network는 다시 Phase 1의 Algorithm을 통해서 병합해 나간다
  • Phase 1을 마치면 다시 Phase 2로 돌입한다
• Phase 2 이후, Phase 1에서 더 이상의 변화가 일어나지 않을 때 Louvain Algorithm은 동작을 정지한다

 

적용 과정

---

Louvain Algorithm을 우리의 프로젝트에 적용해보자

louvain

• Louvain Algorithm을 비교적 쉽게 적용할 수 있도록 해주는 라이브러리를 사용하였다
• 직접 구현하기는 무리가 있다고 판단

 

  let community = louvain.jLouvain().nodes(nodes).edges(edges);
  let result = community();

  /*
   * 객체의 데이터를 이용해서 Key와 해당 Key의 Value에 따라서 다른 색상(Hex)을 부여한다
   * Key는 Node의 ID, Value는 해당 Node의 Community ID
   */

  let colors = {};
  let coloredNodes = {};
  Object.keys(result).map((sourceId) => {
    const communityId = result[sourceId];

    if (colors[communityId] === undefined) {
      colors[communityId] =
        "#" + Math.floor(Math.random() * 16777215).toString(16);
    }

    coloredNodes[sourceId] = colors[communityId];
  });

• 위와 같이 구현을 해서 지정된 커뮤니티에 따라서 다른 색상값을 부여했다
• 색상을 랜덤하게 지정해서 결과가 안 예쁘게 나올 때도 있다
  • 이 부분은 나중에 보완할 예정

 

적용 결과

---

우리의 데이터에 Louvain Algorithm을 적용한 결과는 다음과 같다

• 크기가 비교적 작은 커뮤니티에 대해서는 잘 적용되는 것을 볼 수 있으나,
• 크기가 큰 커뮤니티에서는 내부에 또 다시 여러개의 커뮤니티가 생성되어 색상만으로 커뮤니티를 식별하기 힘든 문제가 발생하였다

 

로그인 기능 구현

---

사용자마다 네트워크를 커스텀하고, 저장할 수 있게 하기 위해서 우리는 로그인 기능을 구현하였다

• 하지만 로그인 기능이 메인 서비스는 아니기 때문에 간단하게 요약만
• JWT 토큰을 사용해서, 인증을 구현하였다
• 이때 토큰 값은 응답을 보낼 때 Set-Cookie를 통해서 쿠키값으로 넣어주었다
  • httpOnly, Secure, SameSite 와 같은 옵션을 통해 보안을 강화하였다
  • httpOnly 속성은 서버에서만 부여할 수 있기 때문에, 프론트에서 직접 쿠키에 저장하기 보다 Set-Cookie를 통해 넣어주었다 
• 요청에 AT없이 RT만 들어있는 경우에는 서버에서 자동 갱신

 

피드백

---

미팅 이후 피드백

• 거대한 커뮤니티 내부에서 또 다른 커뮤니티가 생성되는 현상은 단계적 레이아웃 을 고려해보면 좋을 것 같다
  • 줌을 하기 전에는 이전에 사용했던 Union-Find와 같은 알고리즘을 사용하고
  • 줌을 해서 자세하게 보게 되면, Louvain Algorithm을 적용한 결과를 보여주도록 하면 좋을 수 있을 것 같다
  • 또는 Switch 옵션을 통해서 적용할 알고리즘을 선택할 수 있게 해주는 것도 하나의 방법이 되겠다
• 단계적 레이아웃이 아니더라도, 커뮤니티 형성은 잘 되었기 때문에 네트워크를 시각화하는 다른 레이아웃 을 찾아보는 것도 좋을 것 같다
  • 조교님도 이 부분에 대해서 함께 고민을 해주시기로 하셨다
• 적용하는 알고리즘이 변경되면 계속해서 다시 알고리즘을 적용해야 하기 때문에, 이걸 서버에서 하는 방향으로 구현을 할 예정이다
  • 서버에서 알고리즘을 돌려서 결과를 프론트로 보내주는 방향으로

 

 

Reference

---

[네트워크이론] Network Modularity (네트워크의 모듈성)

[네트워크이론] Louvain algorithm for community detection

4. Community Structure in Networks

louvain

react-cookie

Set a cookie to HttpOnly via Javascript