5. 정점, 간선 추가 및 삭제

이번 활동 요약

---

이번주에는 Cytoscape.js에서 Measure에 대한 기능을 제공하는지 알아보고, 정점과 간선을 추가하고 삭제할 수 있는 기능을 일부 구현했다.

Community Detection은 어느정도 되었으니, 이제 노드의 Degree, Path의 길이 등 Network에 대한 정보를 사용자에게 제공하기 위해서 Network를 측정할 수 있는 기능들을 제공하는지 찾아보았다.
기존에는 파이썬에서 해당 기능들을 제공하기 때문에 파이썬에 이미 구현이 되어 있지만, 프론트단에서 계산을 해서 바로 보여주게 되면 아무래도 더 빠르게 전달할 수 있기 때문에 Cytoscape.js에서 그런 기능들을 제공하는지 찾아보았다.

 

Network Analyzer

---

Cytoscape에서는 Network에 대한 통계 정보를 내주는 Network Analyzer라는 기능을 제공한다.

여기서 제공하는 정보에는 우리가 필요로하는 정보들이 대부분 들어있었다.
그래서 이걸 사용하면 되겠거니 생각했지만, 왜인지 Cytoscape 앱에서는 제공을 하지만, Cytoscape.js에서는 제공하지 않는 것 같았다.
이정도면 제공하지 않는 것이라 생각이 들 정도로 서치를 해보긴 했지만 확신은 할 수 없으니, 일단은 기존대로 파이썬 코드를 사용하고 나중에 찾게되면 교체를 하기로 했다.

 

새로운 기능 구현

---

지난번에는 옵션에 대한 레이아웃만 생성하고, 기능은 넣지 않았지만 이번에는 실제 기능을 사용할 수있도록 구현을 했다.

이번에는 크게 2가지의 기능을 구현했다.

1. 새로운 정점, 간선 생성
: 새로운 정점, 간선을 생성하고 실시간으로 확인할 수 있다.

새로운 간선이 추가되는 경우, 해당 간선으로 인해 두 커뮤니티가 하나로 합쳐지게 되면 하나의 색상으로 칠해지도록 하려고 했지만 이번에는 실패했다.

 

2. 정점 삭제
: 특정 키워드를 포함하는 정점을 삭제하고, 해당 정점과 연결된 간선들도 모두 삭제한다.

 

피드백

---

지금까지의 구현을 바탕으로 교수님이 피드백을 주셨다.

1. 간선도 삭제를 할 수 있으면 좋겠다.
특정 정점을 커뮤니티에서 분리하고 싶은 경우가 있을 수 있기 때문에 노드 뿐 아니라 간선도 삭제 가 가능하면 좋겠다고 하셨다.

2. 정점, 간선을 삭제할 때 입력 뿐 아니라, 클릭으로 삭제할 수 있으면 좋겠다.
현재 구현된 기능은 정점에 붙은 라벨을 입력하면 해당 정점을 찾아서 삭제하도록 되어 있는데, 삭제하고자 하는 노드를 클릭해서 삭제 할 수 있다면 더 편리할 것 같다.

이건 클릭이벤트가 발생한 정점의 ID 값만 알아낼 수 있다면 충분히 할 수 있을 것 같다.

3. 정점을 삭제할 때, 간선으로 연결된 이웃한 노드들도 같이 지워지는데 이걸 선택할 수 있으면 좋겠다.
지금은 특정 정점이 삭제되면, 해당 정점에 연결된 간선과 정점을 모두 삭제하고 있다.
그런데 간선까지는 제거해도 반대편에 있는 정점은 살려둘 수도 있게 했으면 좋겠다고 하셨다.

 

논의 사항

---

진행하면서 궁금했던 내용이나 논의가 필요한 내용들

1. 기존 옵션에 대한 이해
기존에 있던 페이지를 현재 구현중인 페이지에서 온전히 기능할 수 있도록 하기 위해서는, 기존에 있던 옵션들이 정확히 어떤 기능들을 하는지 이해가 필요하다고 생각했다.

2. 서버 구축
그래프에 사용되는 데이터를 제공하는 서버를 둬야 하는데, 연구실에 있는 서버 컴퓨터에 우리의 서버를 어떤 식으로 구축할 것인지 논의가 필요했다.
성능이 좋은 서버 컴퓨터가 있기 때문에 굳이 비용이 발생하는 클라우드를 사용하지 않아도 될 것 같았다.
우리가 서버와 주고받아야 하는 데이터가 그리 많지 않기 때문에 더더욱 그랬다.

3. Community Detection 알고리즘 개선
현재 Union-Find 알고리즘을 사용해서 같은 집합내에 있는 노드들을 탐지하고 해당 노드들을 동일한 색상으로 칠하도록 구현을 해두었다.
문제는 노드를 추가하거나 노드, 엣지를 삭제할 때 커뮤니티가 바뀔 수도 있다는 점이다.

위의 경우에서 2, 4번 사이에 새로운 간선을 생성하게 되면 기존의 두 커뮤니티가 하나로 합쳐지게 된다.
그러면 모든 노드를 초록 또는 주황으로 색칠을 해야 하는데 2, 4번을 Union 하게 되면 조상은 모두 같아지므로 같은 커뮤니티에 넣을 수는 있지만, 각 노드가 가지고 있는 색상 정보는 통일되지 않는다.

결국 모든 노드를 돌면서 다시 색상을 칠해주어야 하는 문제가 발생한다.
물론 그래프에 필요한 데이터의 수가 그렇게 많지 않을 것이기 때문에 충분히 동작을 할 수 있지만, 매번 불필요한 연산을 많이 하는 것 같아서 개선이 필요해 보였다.

마침 교수님이 알고리즘을 전문적으로 하시기 때문에 여쭤볼 수 있었다.

교수님은 각 커뮤니티에 들어있는 노드들을 linked-list 형태로 매달아둔 다음에, Union이 발생하면 한쪽 커뮤니티에 있는 노드만 돌면서 색상값을 바꿔주고 linked-list를 붙여주기만 하면 어떠냐고 하셨다.

추가적인 정보를 저장해야 한다는 오버헤드는 있었지만, 그렇게 크지는 않고 매번 모든 노드에 대해 Union-Find를 진행하는 것보다는 훨씬 효율적이라고 생각했다.
프론트에서 이런 알고리즘을 구현해본 적이 없어서 구현할 수 있을지가 의문이었지만 도전해보기로 했다.

Union-Find는 이름 그대로 합치는 알고리즘이지 해체에 대한 알고리즘이 아니기 때문에 간선이 삭제되어 커뮤니티가 분리되는 경우에는 어쩔 수 없을 것 같다고 하셨다.

 

추후 진행 방향

---

피드백과 논의사항을 바탕으로 다음에 진행해야 할 작업들을 정리해보았다.

1. Community Detection에 사용되는 Louvain 알고리즘 찾아보기
만약 Louvain 알고리즘이 Union-Find 보다 동적인 Community Detection에 유리하다면 해당 알고리즘을 사용하는 것이 더 좋을 수도 있다.

2. 서버 구축하기
연구실 서버 컴퓨터에 서버를 구축하고, 원격으로 접속해서 작업을 이어나가면 될 것 같다.

3. 기존에 있던 옵션들 조금씩 적용해나가기