  We introduce two new bootstraps for exchangeable random graphs. One, the
"empirical graphon bootstrap", is based purely on resampling, while the other,
the "histogram bootstrap", is a model-based "sieve" bootstrap. We show that
both of them accurately approximate the sampling distributions of motif
densities, i.e., of the normalized counts of the number of times fixed
subgraphs appear in the network. These densities characterize the distribution
of (infinite) exchangeable networks. Our bootstraps therefore give a valid
quantification of uncertainty in inferences about fundamental network
statistics, and so of parameters identifiable from them.
