Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls

Abstract : Online social networks (OSN) contain extensive amount of information about the underlying society that is yet to be explored. One of the most feasible technique to fetch information from OSN, crawling through Application Programming Interface (API) requests, poses serious concerns over the the guarantees of the estimates. In this work, we focus on making reliable statistical inference with limited API crawls. Based on regenerative properties of the random walks, we propose an unbiased estimator for the aggregated sum of functions over edges and proved the connection between variance of the estimator and spectral gap. In order to facilitate Bayesian inference on the true value of the estimator, we derive the approximate posterior distribution of the estimate. Later the proposed ideas are validated with numerical experiments on inference problems in real-world networks.
Type de document :
Rapport
[Research Report] RR-8793, Inria Sophia Antipolis; Purdue University. 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01216285
Contributeur : Jithin Sreedharan <>
Soumis le : jeudi 17 décembre 2015 - 17:20:36
Dernière modification le : samedi 27 janvier 2018 - 01:31:41
Document(s) archivé(s) le : samedi 29 avril 2017 - 19:11:27

Fichiers

RR-8793.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01216285, version 4
  • ARXIV : 1510.05407

Collections

Citation

Konstantin Avrachenkov, Bruno Ribeiro, Jithin K. Sreedharan. Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls. [Research Report] RR-8793, Inria Sophia Antipolis; Purdue University. 2015. 〈hal-01216285v4〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

82