Análise de algoritmos de clusterização para experimentos randomizados em redes sociais de larga escala

Abstract

Large companies conduct A/B tests to estimate the effect of changes in their websites. In these tests, users are randomly redirected to one of two versions of the site. However, in social networks, users that access different versions can influence each other if they are linked, making estimation more difficult. To minimize this interference, graph partitioning algorithms were proposed to find clusters of well-connected users (e.g. -net and FENNEL). All users within a cluster are redirected to the same version. In this work, we propose a parallel variant of -net and a new algorithm dubbed NoMAS, inspired on FENNEL. We present a theoretical analysis of the proposed algorithms’ scalability complemented by empirical results on the estimation accuracy.