Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Monday, December 8, 2014 - 4:23:30 PM
Last modification on : Thursday, January 20, 2022 - 4:17:38 PM




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, ⟨10.1109/INFCOMW.2014.6849335⟩. ⟨hal-01092416⟩



Record views