BCSA: BC Tree-Based Sampling and Visualization of Big Graphs

Hong, Seok-Hee and Nguyen, Quan and Meidiana, Amyra and Li, Jiaxi (2017) BCSA: BC Tree-Based Sampling and Visualization of Big Graphs. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 621-623(Official URL: https://link.springer.com/content/pdf/bbm%3A978-3-...).

Full text not available from this repository.


Graph sampling techniques have been popular for the analysis and visualization of big complex networks. However, existing sampling methods often fail to preserve connectivity and important global skeletal structure in the original graph. This poster introduces two new families of sampling methods BCSA-W and BCSA-E for big complex graphs, based on the decomposition of a graph into biconnected components, known as the BC (Block Cut-vertex) tree. Experimental results using graph sampling quality metrics show that our new sampling methods produce better results than existing methods: 25% improvement by BCSA-W and 15% by BCSA-E over existing methods on average. We then present DBCSA, BC tree based graph sampling algorithm in distributed environment. Experiments on the Amazon Cloud EC2 demonstrate that DBCSA is scalable for big graph data sets; running time speed up of 77% for distributed 5-server sampling over sequential sampling on average.We also present a new layout method called BCTV, which clearly shows the BC tree decomposition of a graph. Visual comparison using the BCTV layout shows that our new sampling methods can better maintain the global structure of the original graph.

Item Type: Conference Poster
Classifications: G Algorithms and Complexity > G.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1645

Actions (login required)

View Item View Item