Jump to main content
US EPA
United States Environmental Protection Agency
Search
Search
Main menu
Environmental Topics
Laws & Regulations
About EPA
Health & Environmental Research Online (HERO)
Contact Us
Print
Feedback
Export to File
Search:
This record has one attached file:
Add More Files
Attach File(s):
Display Name for File*:
Save
Citation
Tags
HERO ID
4822134
Reference Type
Book/Book Chapter
Title
BC Tree-based Proxy Graphs for Visualization of Big Graphs
Author(s)
Hong, SHee; Quan Nguyen; Meidiana, A; Li, J; Eades, P; IEEE
Year
2018
Book Title
IEEE Pacific Visualization Symposium
Page Numbers
11-20
DOI
10.1109/PacificVis.2018.00011
Web of Science Id
WOS:000435281700002
Abstract
Recent work for visualizing big graphs uses a proxy graph approach: the original graph is replaced by a proxy graph, which is much smaller than the original graph. The challenge for the proxy graph approach is to ensure that the proxy graph is a good representation of the original graph. However, previous work to compute proxy graphs using graph sampling techniques often fails to preserve connectivity and important global skeletal structure in the original graph.
This paper introduces two new families of proxy graph methods BCP-W and BCP-E, tightly integrating graph sampling methods with the BC (Block Cut-vertex) tree, which represents the decomposition of a graph into biconnected components. Experimental results using graph sampling quality metrics show that our new BC tree-based proxy graph methods produce significantly better results than existing sampling-based proxy graph methods: 25% improvement by BCP-W and 15% by BCP-E on average.
We also present DBCP, a BC tree-based proxy graph method for distributed environment. Experiments on the Amazon Cloud EC2 demonstrate that DBCP is scalable for big graph data sets; runtime speed-up of 77% for distributed 5-server on average.
Visual comparison using a graph layout method and the proxy quality metrics confirm that our new BC tree-based proxy graph methods are significantly better than existing sampling-based proxy graph method. Our main results lead to guidelines for computing sampling-based proxy graphs for visualization of big graphs.
Keywords
Human-centered computing; Visualization; Visualization techniques
Tags
IRIS
•
1,2-Dibromo-3-chloropropane
Litsearch 2018
WOS
Home
Learn about HERO
Using HERO
Search HERO
Projects in HERO
Risk Assessment
Transparency & Integrity