Visual analysis is one of the most effective methods of analyzing large complex networks, and diverse research directions for analyzing and sampling large complex networks are being pursued. One approach is to replace the original graph with a much smaller one while maintaining high quality; this is called the proxy graph approach. However, research has demonstrated that it is a challenge to compute a high-quality proxy graph to represent the original graph. It is also expensive to label the structural properties of the network, especially in terms of time consumption. This thesis introduces new methods for computing proxy graphs based on spectral sparsification approaches for visualizing large complex networks. Two types of spectral sparsification approaches are proposed:
1. We introduce a new method called spectral sampling vertex (SV) for computing proxy graphs. This method reduces the number of vertices in a graph while retaining its structural properties, based on the high effective resistance value. Extensive experimental results using graph sampling quality metrics, visual comparison, and proxy quality metrics confirm that our new method significantly outperforms the Random Vertex sampling method and the Degree Centrality-based sampling method.
2. We introduced two divide and conquer methods for spectral sparsification: BC Tree-based Spectral Sparisification (BC_SS) and BC Tree-based Spectral Vertex Sampling (BC_SV). These two methods are based on the decomposition of a connected graph into biconnected components. Experimental results show that our methods are significantly faster than the pre- vious method while preserving similar sparsification results.