A Simplification Algorithm for Visualizing the Structure of Complex Graphs

Complex graphs, ones containing thousands of nodes of high degree, are difficult to visualize. Displaying all of the nodes and edges of these graphs can create an incomprehensible cluttered output. This paper presents a simplification algorithm that may be applied to a complex graph in order to produce a controlled thinning of the graph. Using importance metrics, the simplification process removes nodes from the graph, leaving the central structure for visualization and evaluation. The simplification algorithm consists of two steps, calculation of the importance metrics and pruning. Several metrics based on various topological graph properties are described. The metrics are then used in a pruning process to simplify the graph. Nodes, along with their corresponding edges, are removed from the graph, while maintaining the graph´s overall connectivity. This simplified graph provides a cleaner, more meaningful visual representation of the graph´s structure; thus aiding the analysis of the graph´s underlying data.