Title: Subsampling large graphs and invariance in networks,
Abstract: Specify a randomized algorithm that, given a very large graph or network,
extracts a random subgraph. What can we learn about the input graph from a
single subsample? We derive laws of large numbers for the sampler output, by
relating randomized subsampling to distributional invariance: Assuming an
invariance holds is tantamount to assuming the sample has been generated by a
specific algorithm. That in turn yields a notion of ergodicity. Sampling
algorithms induce model classes---graphon models, sparse generalizations of
exchangeable graphs, and random multigraphs with exchangeable edges can all be
obtained in this manner, and we specialize our results to a number of examples.
One class of sampling algorithms emerges as special: Roughly speaking, those
defined as limits of random transformations drawn uniformly from certain
sequences of groups. Some known pathologies of network models based on graphons
are explained as a form of selection bias.