图 书 馆
聚类图随机化：多个普遍性下的网络暴露Clustered Graph Randomization: Network Exposure to Multiple Universes |
|
| 课程网址: | http://videolectures.net/kdd2013_ugander_multiple_universes/ |
| 主讲教师: | Johan Ugander |
| 开课单位: | 康奈尔大学 |
| 开课时间: | 2013-09-27 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | A/B testing is a standard approach for evaluating the effect of online experiments; the goal is to estimate the `average treatment effect' 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 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 cluster randomization admits an efficient exact algorithm to compute the probabilities for each vertex being network exposed under several of these exposure conditions. Using these probabilities as inverse weights, a Horvitz-Thompson estimator can then provide an effect estimate that is unbiased, provided that the exposure model has been properly specified. Given an estimator that is unbiased, we focus on minimizing the variance. First, we develop simple sufficient conditions for the variance of the estimator to be asymptotically small in n, the size of the graph. However, for general randomization schemes, this variance can be lower bounded by an exponential function of the degrees of a graph. In contrast, we show that if a graph satisfies a restricted-growth condition on the growth rate of neighborhoods, then there exists a natural clustering algorithm, based on vertex neighborhoods, for which the variance of the estimator can be upper bounded by a linear function of the degrees. Thus we show that proper cluster randomization can lead to exponentially lower estimator variance when experimentally measuring average treatment effects under interference. |
| 关 键 词: | 网络暴露; 效果评估; 社交网络; 估计方差 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-06-10：chenxin01 |
| 最后编审: | 2023-06-10：chenxin01 |
| 阅读次数: | 19 |