Análise de Algoritmos de Clusterização para Experimentos Randomizados em Redes Sociais de Larga Escala

• Bruno Demattos Nogueira UFMG
• Francisco Galuppo Azevedo UFMG
• Fabricio Murai UFMG
• Ana Paula Couto da Silva UFMG

DOI: https://doi.org/10.5753/wperformance.2018.3329

Resumo

Grandes empresas realizam testes A/B para estimar o efeito de mudanças nos seus websites. Nestes testes, usuários são redirecionados aleatoriamente para uma de duas versões do site. Porém, em redes sociais, usuários que acessam diferentes versões podem influenciar uns aos outros se estiverem relacionados, dificultando a estimação. Para minimizar esta interferência, foram propostos algoritmos para particionar a rede em clusters de usuários bem conectados (ε-net e FENNEL). Todos os usuários dentro de um cluster são redirecionados para uma mesma versão. Neste trabalho, propomos uma versão paralela do ε-net e um novo algoritmo chamado NoMAS, inspirado no FENNEL. Apresentamos uma análise teórica da escalabilidade dos algoritmos complementada por resultados empíricos sobre a acurácia da estimação.

Referências

Aronow, P. M. and Samii, C. (2012). Estimating average causal effects under general interference. In Summer Meeting of the Society for Political Methodology, pages 19–21.

Azevedo, F. G., Nogueira, B. D., Murai, F., and da Silva, A. P. C. (2018). Modelos de resposta para experimentos randomizados em redes sociais de larga escala. arXiv:1803.03497.

Backstrom, L. and Kleinberg, J. M. (2011). Network bucket testing. In WWW, pages 615–624.

Eckles, D., Karrer, B., and Ugander, J. (2014). Design and analysis of experiments in networks: Reducing bias from interference. CoRR abs/1507.00803, stat.ME.

Fortunato, S. (2010). Community detection in graphs. Physics Reports-Review Section of Physics Letters, 486(3-5):75–174.

Gui, H., Xu, Y., Bhasin, A., and Han, J. (2015). Network A/B Testing: From Sampling to Estimation. WWW, pages 399–409.

Katzir, L., Liberty, E., and Somekh, O. (2012). Framework and algorithms for network bucket testing. In WWW, pages 1029–1036.

Kohavi, R., Deng, A., Frasca, B., Walker, T., Xu, Y., and Pohlmann, N. (2013). Online controlled experiments at large scale. In KDD, pages 1168–1176.

Kohavi, R., Longbotham, R., Sommerfield, D., and Henne, R. M. (2009). Controlled experiments on the web: survey and practical guide. DMKD, 18(1):140–181.

Manski, C. F. (2013). Identification of treatment response with social interactions. Econometrics Journal, 16(1):S1–S23.

Middleton, J. A. and Aronow, P. M. (2011). Unbiased Estimation of the Average Treatment Effect in Cluster-Randomized Experiments. SSRN Electronic Journal.

Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577–8582.

Nishimura, J. and Ugander, J. (2013). Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In KDD, pages 1106–1114.

Saveski, M., Pouget-Abadie, J., Saint-Jacques, G., Duan, W., Ghosh, S., Xu, Y., and Airoldi, E. M. (2017). Detecting Network Effects. In KDD, pages 1027–1035.

Stanton, I. and Kliot, G. (2012). Streaming graph partitioning for large distributed graphs. In KDD, pages 1222–1230. ACM.

Tsourakakis, C., Gkantsidis, C., Radunovic, B., and Vojnovic, M. (2014). Fennel: Streaming graph partitioning for massive scale graphs. In WSDM, pages 333–342. ACM.

Ugander, J., Karrer, B., Backstrom, L., and Kleinberg, J. (2013). Graph cluster randomization: Network exposure to multiple universes. In KDD, pages 329–337.

Xu, Y., Chen, N., Fernandez, A., Sinno, O., and Bhasin, A. (2015). From infrastructure to culture: A/B testing challenges in large scale social networks. In KDD, pages 2227–2236.