Local bootstrap for network data

Abstract In network analysis, one frequently needs to conduct inference for network parameters based on a single observed network. Since the sampling distribution of the statistic is often unknown, one has to rely on the bootstrap. However, because of the complex dependence structure among vertices, existing bootstrap methods often yield unsatisfactory performance, especially for small or moderate sample sizes. Here we propose a new network bootstrap procedure, termed the local bootstrap, for estimating the standard errors of network statistics. The method involves resampling the observed vertices along with their neighbour sets, and then reconstructing the edges between the resampled vertices by drawing from the set of edges connecting their neighbour sets. We justify the proposed method theoretically with desirable asymptotic properties for statistics such as motif density, and demonstrate its excellent numerical performance for small and moderate sample sizes. Our approach encompasses several existing methods, such as the empirical graphon bootstrap, as special cases. We investigate the advantages of the proposed method over existing methods in terms of edge randomness, vertex heterogeneity and neighbour set size, which can help to shed light on the complex issue of network bootstrapping.