Prof. Sarah Adams
As graphs are generated with greater numbers of vertices and edges, it becomes increasingly important to develop effective ways to visualize them. Current methods can automatically layout reasonably complex graphs, but graphs with small world properties and high edge densities are still extremely challenging.
This paper proposes two approaches to creating graph abstractions; graphs which exhibit the same topological features and express the details of the original graph in an effective visual way. We call the first method k-Clique Minimization. In this method, we use a graph heuristic to quickly find completely connected subgraphs. Each of these subgraphs is replaced in the abstracted graph with a single node, whose size is related to the size of the complete subgraph that has been replaced. To further simplify the graph, we "erode" once, removing pendant vertices, and showing them graphically as a dark halo around remaining vertices.
Our second method, Centrality Erosion, is an iterative process in which nodes with a centrality of zero are removed from the graph, until the remaining nodes all have a centrality value of greater than zero. Nodes are colored and sized based on how many erosion cycles they sustained before being removed.