Randomized graph sampling

Randomized graph sampling (RGS) is an approach for sampling populations associated with or describable as graphs, when the structure of the graph is known and the parameter of interest is the total weight of the graph. RGS is related to, but distinct from, other graph-based approaches such as snowball and network sampling. Graph elements are clustered into walks that reflect the structure of the graph, as well as operational constraints on sampling. The basic estimator in RGS can be constructed as a Horvitz-Thompson estimator. I prove it to be design-unbiased, and also show design-unbiasedness of an estimator of the sample variance when walks are sampled with replacement. Covariates can be employed for variance reduction either through improved assignment of selection probabilities to walks in the design step, or through the use of alternative estimators during analysis. The approach is illustrated with a trail maintenance example, which demonstrates that complicated approaches to assignment of selection probabilities can be counterproductive. I describe conditions under which RGS may be efficient in practice, and suggest possible applications.