document: Network bucket testing 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 will be unlikely to produce groups 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 .
doc_bio_tags: O B I B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O