A/B testing is a standard approach for evaluating the effect of online experiments; the goal is to estimate the Average Treatment Effect (ATE) of a new feature or condition by exposing a sample of the overall population to it. A drawback with A/B testing is that it is poorly suited for experiments involving social interference, when the treatment of individuals spills over to neighboring individuals along an underlying social network. In this work, we propose a novel methodology for using graph clustering to analyze average treatment effects under social interference. To begin, we characterize graph-theoretic conditions under which individuals can be considered to be 'network exposed' to an experiment. We then show how graph clustered randomization admits an efficient exact algorithm to compute the probabilities for each vertex being network exposed under several of these exposure conditions, allowing for a straightforward effect estimator using inverse probability weights. This estimator is also unbiased assuming that the exposure model has been properly specified. Given this framework for graph cluster randomization, we analyze the variance of the estimator as a property of cluster design, and the bias/variance trade-offs of the estimator under simulated exposure model misspecifications. Our analysis of the variance includes a novel clustering algorithm for which the variance is at most linear in the degrees of the graph, an important challenge. Our analysis of misspecifications highlights when clustering appears to be strongly favorable: when the network has a sufficiently clustered structure, and when social interference is sufficiently strong.

Johan Ugander is currently a postdoc at MSR Redmond, hosted by Eric Horvitz, and will be joining Stanford as an Assistant Professor in Management Science & Engineering, starting Fall 2015. His research develops tools for analyzing massive social graphs and other forms of large-scale social data. More specifically, developing better understandings of the structure of social systems, social networks, and human decision making. Dr. Ugander's work commonly falls at the intersections of graph theory, probability theory, statistics, optimization, and algorithm design. Dr. Ugander obtained his Ph.D. in Applied Mathematics from Cornell University in June 2014, advised by Jon Kleinberg. From May 2010 - June 2014, he also held an affiliation with the Facebook Data Science team.