Characterizing Accuracy and Performance Tradeoffs in Graph Sampling for Graph Property Computations
Tej Chajed · 2014
In this thesis, we present a systematic way to characterize the tradeoffs be-tween accuracy and cost in graph sampling. This characterization is heavily dependent on graph structure. Here we focus on vector graph properties, which consist of a value per node in the graph (e.g., PageRank, degree). We present a new technique for assessing the accuracy of a property based on the algorithm used to compute it. Next, we describe how to interpret several features of accuracy-performance tradeoff curves. Finally, we present our analysis of actual accuracy-cost curves for both real-world and synthetic graphs. Conclusions from the analysis include that the structure of a graph is more important than its scale for the purposes of sampling, and that different structures require different sampling approaches.