Title: Enhancing Stratified Graph Sampling Algorithms based on Approximate Degree Distribution,
Abstract: Sampling technique has become one of the recent research focuses in the
graph-related fields. Most of the existing graph sampling algorithms tend to
sample the high degree or low degree nodes in the complex networks because of
the characteristic of scale-free. Scale-free means that degrees of different
nodes are subject to a power law distribution. So, there is a significant
difference in the degrees between the overall sampling nodes. In this paper, we
propose an idea of approximate degree distribution and devise a stratified
strategy using it in the complex networks. We also develop two graph sampling
algorithms combining the node selection method with the stratified strategy.
The experimental results show that our sampling algorithms preserve several
properties of different graphs and behave more accurately than other
algorithms. Further, we prove the proposed algorithms are superior to the
off-the-shelf algorithms in terms of the unbiasedness of the degrees and more
efficient than state-of-the-art FFS and ES-i algorithms.