Dynamic and interactive layout algorithm for network clustering

Abstract

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...