Network Bucket Testing

International World Wide Web Conference (WWW)


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.

Related Publications

All Publications

Open Source Evolutionary Structured Optimization

Jeremy Rapin, Pauline Bennet, Emmanuel Centeno, Daniel Haziza, Antoine Moreau, Olivier Teytaud

Evolutionary Computation Software Systems Workshop at ​GECCO - July 9, 2020

Adherence to suicide reporting guidelines by news shared on a social networking platform

Steven A. Sumner, Moira Burke, Farshad Kooti

PNAS - July 6, 2020

A Counterfactual Framework for Seller-Side A/B Testing on Marketplaces

Viet Ha-Thuc, Avishek Dutta, Ren Mao, Matthew Wood, Yunli Liu

ACM SIGIR - July 25, 2020

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, Chenyi Zhang

ICDE - April 20, 2020

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy