  Graph sampling is a technique to pick a subset of vertices and/ or edges from
original graph. It has a wide spectrum of applications, e.g. survey hidden
population in sociology [54], visualize social graph [29], scale down Internet
AS graph [27], graph sparsification [8], etc. In some scenarios, the whole
graph is known and the purpose of sampling is to obtain a smaller graph. In
other scenarios, the graph is unknown and sampling is regarded as a way to
explore the graph. Commonly used techniques are Vertex Sampling, Edge Sampling
and Traversal Based Sampling. We provide a taxonomy of different graph sampling
objectives and graph sampling approaches. The relations between these
approaches are formally argued and a general framework to bridge theoretical
analysis and practical implementation is provided. Although being smaller in
size, sampled graphs may be similar to original graphs in some way. We are
particularly interested in what graph properties are preserved given a sampling
procedure. If some properties are preserved, we can estimate them on the
sampled graphs, which gives a way to construct efficient estimators. If one
algorithm relies on the perserved properties, we can expect that it gives
similar output on original and sampled graphs. This leads to a systematic way
to accelerate a class of graph algorithms. In this survey, we discuss both
classical text-book type properties and some advanced properties. The landscape
is tabularized and we see a lot of missing works in this field. Some
theoretical studies are collected in this survey and simple extensions are
made. Most previous numerical evaluation works come in an ad hoc fashion, i.e.
evaluate different type of graphs, different set of properties, and different
sampling algorithms. A systematical and neutral evaluation is needed to shed
light on further graph sampling studies.
