J. Edward Swan II

A Visual and Statistical Benchmark for Graph Sampling Methods

Fangyan Zhang, Song Zhang, Pak Chung Wong, J. Edward Swan II, and T.J. Jankun-Kelly. A Visual and Statistical Benchmark for Graph Sampling Methods. In Exploring Graphs at Scale (EGAS) Workshop, IEEE VIS 2015, Oct 2015.

Download

[PDF] 

Abstract

Effectively visualizing large graphs is challenging. Capturing the statistical properties of these large graphs is also difficult. Sampling algorithms, developed to more feasibly observe and analyze large graphs, are indispensable for this task. Many sampling approaches for graph simplification have been proposed. These methods can be grouped into three categories: node sampling, edge sampling, and traversal-based sampling. It is still an open question, however, which single sampling technique produces the best representative sample. The goal of this paper is to evaluate commonly used sampling methods through a combined visual and statistical comparison. Initial results indicate that the effectiveness of a sampling method is dependent on the type of graph, the size of the graph, and the desired statistical property. The benchmark can be used as a guideline in choosing the proper method for a particular graph sampling task. The resulting benchmark can be incorporated into graph visualization and analysis tools.

BibTeX

@InProceedings{IEEEVIS15-gv, 
  author =      {Fangyan Zhang and Song Zhang and Pak Chung Wong and 
                 J. Edward {Swan~II} and T.J. Jankun-Kelly}, 
  title =       {A Visual and Statistical Benchmark for Graph Sampling Methods}, 
  booktitle =   {Exploring Graphs at Scale (EGAS) Workshop, IEEE VIS 2015}, 
  location =    {Chicago, Illinois, USA}, 
  date =        {October 26}, 
  month =       {Oct}, 
  year =        2015, 
  abstract = { 
Effectively visualizing large graphs is challenging. Capturing the 
statistical properties of these large graphs is also 
difficult. Sampling algorithms, developed to more feasibly observe and 
analyze large graphs, are indispensable for this task. Many sampling 
approaches for graph simplification have been proposed. These methods 
can be grouped into three categories: node sampling, edge sampling, 
and traversal-based sampling. It is still an open question, however, 
which single sampling technique produces the best representative 
sample. The goal of this paper is to evaluate commonly used sampling 
methods through a combined visual and statistical comparison. Initial 
results indicate that the effectiveness of a sampling method is 
dependent on the type of graph, the size of the graph, and the desired 
statistical property. The benchmark can be used as a guideline in 
choosing the proper method for a particular graph sampling task. The 
resulting benchmark can be incorporated into graph visualization and 
analysis tools. 
}, 
}