Comparison of Random Walk Based Techniques for Estimating Network Averages

Konstantin Avrachenkov 1 Vivek Borkar 2 Arun Kadavankandy 1 Jithin Sreedharan 1
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 IIT Bombay - Indian Institute of Technology Bombay
Abstract : Function estimation on Online Social Networks (OSN) is an important field of study in complex network analysis. An efficient way to do function estimation on large networks is to use random walks. We can then defer to the extensive theory of Markov chains to do error analysis of these estimators. In this work we compare two existing techniques, Metropolis-Hastings MCMC and Respondent-Driven Sampling, that use random walks to do function estimation and compare them with a new reinforcement learning based technique. We provide both theoretical and empirical analyses for the estimators we consider.
Keywords : reinforcement learning random walks on graph estimation
Type de document :
Communication dans un congrès
Computational Social Networks, Aug 2016, Ho Chi Minh, Vietnam. Springer, 9795, pp.27 - 38, 2016, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007/978-3-319-42345-6_3〉. 〈10.1007/978-3-319-42345-6_3〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01402800
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 25 novembre 2016 - 10:59:10
Dernière modification le : samedi 21 juillet 2018 - 14:12:01
Document(s) archivé(s) le : lundi 20 mars 2017 - 19:44:50

Fichier

Csonet5_Paper28.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA

Citation

Konstantin Avrachenkov, Vivek Borkar, Arun Kadavankandy, Jithin Sreedharan. Comparison of Random Walk Based Techniques for Estimating Network Averages. Computational Social Networks, Aug 2016, Ho Chi Minh, Vietnam. Springer, 9795, pp.27 - 38, 2016, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007/978-3-319-42345-6_3〉. 〈10.1007/978-3-319-42345-6_3〉. 〈hal-01402800〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

266

Téléchargements de fichiers

100

Contact


archive-ouverte@inria.fr