Inference in OSNs via Lightweight Partial Crawls

Abstract : Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (SNA) but often crawling an OSN network via its Application Programming Interface (API) is the only way to gather data from a third party. To date, these partial API crawls are the majority of public datasets and the synonym of lack of statistical guarantees in incomplete-data comparisons, severely limiting SNA research progress. Using regenerative properties of the random walks, we propose estimation techniques based on short crawls that have proven statistical guarantees. Moreover, our short crawls can be implemented in massively distributed algorithms. We also provide an adaptive crawler that makes our method parameter-free, significantly improving our statistical guarantees. We then derive the Bayesian approximation of the posterior of the estimates, and in addition, obtain an estima-tor for the expected value of node and edge statistics in an equivalent configuration model or Chung-Lu random graph model of the given network (where nodes are connected randomly) and use it as a basis for testing null hypotheses. The theoretical results are supported with simulations on a variety of real-world networks.
Type de document :
Communication dans un congrès
ACM SIGMETRICS, Jun 2016, Juan Les Pins, France. 2016, ACM SIGMETRICS 2016 Proceedings. 〈10.1145/2896377.2901477〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 25 novembre 2016 - 13:43:53
Dernière modification le : jeudi 11 janvier 2018 - 16:58:49
Document(s) archivé(s) le : mardi 21 mars 2017 - 15:33:41


Fichiers produits par l'(les) auteur(s)




Konstantin Avrachenkov, Bruno Ribeiro, Jithin Sreedharan. Inference in OSNs via Lightweight Partial Crawls. ACM SIGMETRICS, Jun 2016, Juan Les Pins, France. 2016, ACM SIGMETRICS 2016 Proceedings. 〈10.1145/2896377.2901477〉. 〈hal-01403018〉



Consultations de la notice


Téléchargements de fichiers