Análise de Algoritmos de Clusterização para Experimentos Randomizados em Redes Sociais de Larga Escala
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.
