Subsampling large graphs and invariance in networks

arXiv1710.04217MaRDI QIDQ6292437FDOQ6292437

Publication date: 11 October 2017

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.

This page was built for publication: Subsampling large graphs and invariance in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6292437)