Subsampling for Chain-Referral Methods

Konstantin Avrachenkov (1) , Giovanni Neglia (1) , Alina Tuholukova (1)

1 MAESTRO - Models for the performance analysis and the control of networks

We study chain-referral methods for sampling in social networks. These methods rely on subjects of the study recruiting other participants among their set of connections. This approach gives us the possibility to perform sampling when the other methods, that imply the knowledge of the whole network or its global characteristics, fail. Chain-referral methods can be implemented with random walks or crawling in the case of online social networks. However, the estimations made on the collected samples can have high variance, especially with small sample size. The other drawback is the potential bias due to the way the samples are collected. We suggest and analyze a sub-sampling technique, where some users are requested only to recruit other users but do not participate to the study. Assuming that the referral has lower cost than actual participation, this technique takes advantage of exploring a larger variety of population, thus decreasing significantly the variance of the estimator. We test the method on real social networks and on synthetic ones. As by-product, we propose a Gibbs like method for generating synthetic networks with desired properties.

Domaines: Statistiques [stat]

Konstantin Avrachenkov, Giovanni Neglia, Alina Tuholukova. Subsampling for Chain-Referral Methods. International Conference on Analytical and Stochastic Modeling Techniques and Applications, Aug 2016, Cardiff, United Kingdom. pp.17 - 31, ⟨10.1007/978-3-319-43904-4_2⟩. ⟨hal-01401287⟩