  Edge sampling is an important topic in network analysis. It provides a
natural way to reduce network size while retaining desired features of the
original network. Sampling methods that only use local information are common
in practice as they do not require access to the entire network and can be
parallelized easily. Despite promising empirical performances, most of these
methods are derived from heuristic considerations and therefore still lack
theoretical justification. To address this issue, we study in this paper a
simple edge sampling scheme that uses network local information. We show that
when local connectivity is sufficiently strong, the sampled network satisfies a
strong spectral property. We quantify the strength of local connectivity by a
global parameter and relate it to more common network statistics such as the
clustering coefficient and network curvature. Based on this result, we also
provide sufficient conditions under which random networks and hypergraphs can
be sampled efficiently.
