Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

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

Résumé

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 asymptotic posterior distribution of the estimate. Later the proposed ideas are validated with numerical experiments on inference problems in real-world networks.
Fichier principal
Vignette du fichier
RR-8793.pdf (949.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01216285 , version 1 (16-10-2015)
hal-01216285 , version 2 (19-10-2015)
hal-01216285 , version 3 (19-10-2015)
hal-01216285 , version 4 (17-12-2015)

Identifiants

Citer

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-01216285v3⟩
210 Consultations
114 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More