  Efficient marketing or awareness-raising campaigns seek to recruit $n$
influential individuals -- where $n$ is the campaign budget -- that are able to
cover a large target audience through their social connections. So far most of
the related literature on maximizing this network cover assumes that the social
network topology is known. Even in such a case the optimal solution is NP-hard.
In practice, however, the network topology is generally unknown and needs to be
discovered on-the-fly. In this work we consider an unknown topology where
recruited individuals disclose their social connections (a feature known as
{\em one-hop lookahead}). The goal of this work is to provide an efficient
greedy online algorithm that recruits individuals as to maximize the size of
target audience covered by the campaign.
  We propose a new greedy online algorithm, Maximum Expected $d$-Excess Degree
(MEED), and provide, to the best of our knowledge, the first detailed
theoretical analysis of the cover size of a variety of well known network
sampling algorithms on finite networks. Our proposed algorithm greedily
maximizes the expected size of the cover. For a class of random power law
networks we show that MEED simplifies into a straightforward procedure, which
we denote MOD (Maximum Observed Degree). We substantiate our analytical results
with extensive simulations and show that MOD significantly outperforms all
analyzed myopic algorithms. We note that performance may be further improved if
the node degree distribution is known or can be estimated online during the
campaign.
