Clustering refers to the gathering of data into subsets where each subset has certain similarity. This process is usually done by observation from the layout of the scattered data. In this case, the distance measure plays an important role in making distinctions between the subsets or clusters. Graph clustering visualization is the layout of the graph where the nodes sharing certain property are placed in close proximity so that the user can observe the relationships among the data in each cluster and/or between the clusters.
Many kinds of graph clustering layout algorithms have been developed to analyze the relationships within a cluster and among clusters. In this research, we focus on dynamic and interactive layout algorithm for graph clustering by which method the layout changes gradually when a user moves, adds and/or deletes some layout elements. We use an analogy of a physical system where nodes are charged particles and edges are springs connecting the particles. This kind of layout method is referred to as force-directed placement (FDP) method. The topic of this thesis is on the graph clustering based on FDP.
Existing dynamic interactive clustering layout methods based on FDP can show the animated layout changes that can help a user trace changes of the graph and dynamic interactivity which can help a user rearrange layout elements efficiently. The efficient rearrangement of layout for clustering is achieved by pulling the nodes or clusters connected by springs, edges. However, the pervious FDP based clustering methods may place a node which should be placed within a clustering. Moreover, the final layout is not well balanced for inside and outside layouts. For dynamic animation and interactivity, forces of all layout elements should be continuously applied so if there are many outside cluster nodes connected to inside nodes by edges (we named this kind of edges inter edges), these inter edges can pull inside nodes to outside of the cluster. This happens because outside nodes push cluster region and inter edge pull inside nodes. This can cause misplacement of nodes. For example inside nodes pulled out and placed outside of the cluster region.
In this research, to address the problem described above, we develop boundary dummy clustering (BDC) method whose main idea is to introduce a dummy node named boundary dummy into each inter edge which can cause error placement by pulling inside group nodes; and make the boundary dummies move along the boundary of circular cluster region. By this setting, the pulling forces do not pull the inside nodes but the cluster. However, the direction of the pulling forces can be transmitted to the inside nodes by the position of boundary dummies. As a result, BDC can prevent the error placements while providing balanced inside and outside layout.
Additionally, three optional forces using boundary dummies are designed as heuristic methods for improving readability near cluster boundary. To describe, the first optional force is repulsive force between boundary dummies connected to the same intra node so this force can used for improving edge resolution among inter edges of the intra node. The second one is repulsive force between boundary dummies connected to different intra nodes so the edge bundles of each intra node can be separated by this force. The last one is repulsive force among boundary dummies and intra nodes. This force also plays similar role to the second optional force.
일반적으로 클러스터링은 관련된 데이터들을 모아 보여주는 방법을 말한다. 본 논문에서는 같은 속성을 갖는 그래프의 노드들을 정해진 영역에 모아서 보여주는 그래프 클러스터링을 다룬다. 노드와 클러스터 같은 요소들은 레이아웃 알고리즘에 의해 배치되며 여러 특성을 갖는 많은 레이아웃 알고리즘들이 개발되어왔다. 본 논문에서는 레이아웃 요소들의 추가/제거 과정이 점진적으로 변하는 것이 가능하고 그래프의 노드를 전하를 띈 입자로 이들 사이의 엣지르 스프링으로 시뮬레이션 함에 의해 동적 상호작용을 가능하게 하는 force-directed placement (FDP) 방식을 기본적 레이아웃 알고리즘으로 채택 하였다.
기존의 FDP에 기반한 동적이고 상호작용 가능한 그래프 클러스터링 레이아웃 알고리즘은 레이아웃에 새로운 요소가 추가 되거나 클러스터링 과정을 동적으로 보여주며 사용자가 이러한 레이아웃의 요소들과 동적으로 상호작용 하는 것을 비교적 쉬운 방법으로 제공해 준다. 하지만 이러한 방식은 노드와 엣지들을 물리적인 요소들로 시뮬레이션 하기 때문에 일정한 공간 (클러스터) 영역에 조화롭게 배치시키는데 어려움이 있을 수 있다. 그러한 어려움 중의 하나는 클러스터 안에 배치 되야 하는 노드가 클러스터 밖의 노드들과 연결된 엣지들에 의해서 밖으로 당겨짐으로써 노드가 원하지 않는 영역에 배치되는 것이다. 이러한 문제를 해결하기 위해 본 연구에서는 Boundary Dummy Clustering (BDC) 레이아웃 알고리즘을 고안 하였다. 이 레이아웃 알고리즘은 그룹안과 밖을 연결하는 inter edge들에 의해 잘 못된 노드 배치를 막기 위해 inter edge를 분할 하여 중간에 boundary dummy라고 명명된 가상의 노드를 삽입하고 이 노드들 클러스터의 경계를 따라서만 움직이게 함으로써 그룹 안의 노드가 밖으로 당겨지는 힘을 차단한다. 반면에 당기는 힘의 방향이 어느 쪽인지는 그룹 안쪽 노드들에게 전달하게 함으로써 잘못된 노드 배치를 막으며 그룹 안과 그룹 밖의 레이아웃이 조화롭게 구성되게 할 수 있는 알고리즘이다.
또한, 추가적으로 새롭게 추가된 boundary dummy들을 사용하여 선택적으로 적용 할 수 있는 물리적인 힘 관계를 정의 함으로써 클러스터 주위의 레이아웃의 가독성을 높일 수 있는 휴리스틱한 방법을 제안하였다. 이러한 선별적으로 적용 할 수 있는 힘 관계는 3가지가 있으며 이들은 inter edge들의 각도를 개선하고 엣지 교차를 줄이는데 도움을 줄 수 있다.
