Cnm Cluster-based Non-directed Graph Visualization

A network graph includes a node set and an edge set, representing entities and their relationships respectively. The network abstract from real-world always have very large scale, including thousands or even millions of nodes, such as the network of paper citation and World Wide Web. As the rapid increasing of the networks scale, the graph visualization of large-scale network has becoming the hottest area in Information Visualization.A key issue in the graph visualization is how to display the thousands of nodes and their relationships in a limited screen with a nice and efficient manner. Some layout algorithms, performing well in small scale graph, have poor performance in very large scale graph. They always have the defects of long time running, poor layout result and inefficient utilization of display space. This paper major in visualization of non-directed graph, and most work focus on improving the efficiency of visualization.The main works and innovative points of this thesis are as follows:1. Design a new framework conduct the visualization of large-scale undirected graph. It's based on Multi-level technology, producing a series of abstract graph by clustering on original graph, and use force-direct algorithm in the single-level to optimize the layout of the vertex.2. In the phase of graph clustering, this paper adopt and optimize the CNM algorithm. After modifying, the CNM algorithm not only preserve the feature of fast speed in run-time, but also becoming more balance during clustering, and the height of clustering tree drop heavily.3. Put forward a method to link the CNM algorithm and Multi-level technology. By introducing the"virtual node"to the clustering tree of CNM algorithm, the leaf node in the clustering tree have the same height.4. In the phase of layout, this paper adopt the FR algorithm, which is a variant of force-direct algorithm. As the complexity of calculating the repulsive force with FR algorithm is O( | v |2 ), it's difficult to apply this algorithm to large-scale graphs. To solve this problem, this paper improved the quad-tree algorithm to calculate the repulsive force and reduce the some time for calculating the repulsive force. In addition, this paper also proposed some other strategies to optimize the FR algorithm: First, control the iterations number of FR algorithm. We give the high layers more iterations, while less iterations to low layers; second, limit the move of the vertex, avoiding the situation of too many vertex in the screen border; Third, adopt bary-centralizing algorithm to optimize the initial layout, and speeding up the FR algorithm.