Pay few, influence most: Online myopic network covering

Abstract : Efficient marketing or awareness-raising campaigns seek to recruit a small number, w, of influential individuals - where w is the campaign budget - that are able to cover the largest possible target audience through their social connections. In this paper we assume that the topology is gradually discovered thanks to recruited individuals disclosing their social connections. We analyze the performance of a variety of online myopic algorithms (i.e. that do not have a priori information on the topology) currently used to sample and search large networks. We also propose a new greedy online algorithm, Maximum Expected Uncovered Degree (MEUD). Our proposed algorithm greedily maximizes the expected size of the cover, but it requires the degree distribution to be known. For a class of random power law networks we show that MEUD simplifies into a straightforward procedure, denoted as MOD because it requires only the knowledge of the Maximum Observed Degree.
Type de document :
Communication dans un congrès
6th IEEE INFOCOM International Workshop on Network Science for Communication Networks (NetSciCom 2014), May 2014, Toronto, Canada. pp.813-818, 2014, 〈http://www.ctr.kcl.ac.uk/netscicom14/〉. 〈10.1109/INFCOMW.2014.6849335〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01092416
Contributeur : Konstantin Avrachenkov <>
Soumis le : lundi 8 décembre 2014 - 16:23:30
Dernière modification le : jeudi 21 juin 2018 - 16:38:01

Lien texte intégral

Identifiants

Collections

Citation

Konstantin Avrachenkov, Prithwish Basu, Giovanni Neglia, Bruno Ribeiro, Don Towsley. Pay few, influence most: Online myopic network covering. 6th IEEE INFOCOM International Workshop on Network Science for Communication Networks (NetSciCom 2014), May 2014, Toronto, Canada. pp.813-818, 2014, 〈http://www.ctr.kcl.ac.uk/netscicom14/〉. 〈10.1109/INFCOMW.2014.6849335〉. 〈hal-01092416〉

Partager

Métriques

Consultations de la notice

207