Network Bucket Testing
                       Lars Backstrom, Facebook

Bucket testing, also known as A/B testing, is a practice that is
widely used by on-line sites with large audiences: in a simple version
of the methodology, one evaluates a new feature on the site by
exposing it to a very small fraction of the total user population and
measuring its effect on this exposed group. For traditional uses of
this technique, uniform independent sampling of the population is
often enough to produce an exposed group that can serve as a
statistical proxy for the full population.

In on-line social network applications, however, one often wishes to
perform a more complex test: evaluating a new social feature that will
only produce an effect if a user and some number of his or her friends
are exposed to it. In this case, independent uniform draws from the
population on their own will be unlikely to produce a group that
contains users together with their friends, and so the construction of
the sample must take the network structure into account. This leads
quickly to challenging combinatorial problems, since there is an
inherent tension between producing enough correlation to select users
and their friends, but also enough uniformity and independence that
the selected group is a reasonable sample of the full population.

Here we develop an algorithmic framework for bucket testing in a
network that addresses these challenges. First we describe a novel
walk-based sampling method for producing samples of nodes that are
internally well-connected but also approximately uniform over the
population. Then we show how a collection of multiple independent
subgraphs constructed this way can yield reasonable samples for
testing. We demonstrate the effectiveness of our algorithms through
computational experiments on large portions of the Facebook network.