Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Friday, November 25, 2016 - 1:43:53 PM
Last modification on : Thursday, January 20, 2022 - 4:12:22 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 3:33:41 PM


Files produced by the author(s)




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



Record views


Files downloads