Network Bootstrap Using Overlapping Partitions

Music City Center 

Bootstrapping network data efficiently is a challenging task. The existing methods tend to make strong assumptions on both the network structure and the statistics being bootstrapped, and are computationally costly. This paper introduces a general algorithm, SSBoot, for network bootstrap that partitions the network into multiple overlapping subnetworks and then aggregates results from bootstrapping these subnetworks to generate a bootstrap sample of the network statistic of interest. This approach tends to be much faster than competing methods as most of the computations are done on smaller subnetworks. We show that SSBoot is consistent in distribution for a large class of network statistics under minimal assumptions on the network structure, and demonstrate with extensive numerical examples that the bootstrap confidence intervals produced by SSBoot attain good coverage without substantially increasing interval lengths in a fraction of the time needed for running competing methods.

Network analysis

Bootstrapping

Overlapping partitions

Subsampling

Confidence Interval

Network subsampling 

Section on Statistical Computing