Information spread in a social graph
This isn't a full answer, but a partial one since there's a lot of literature out there.

To answer the question, we need some model of how information spreads in a social network. You seem to maybe be assuming that everyone we talk to tells their friends, but their friends don't tell anyone (so we just want to pick the set that maximizes the number of neighbors). But many other dynamics are possible. Usually, one thinks of the problem as finding an initial set of nodes to "infect", and assuming that all nodes have some rule for when they get infected as a function of the number of infected neighbors. For example, you could have a threshold which says that I get infected as soon as I have 3 or more infected neighbors; or that $i$ has a probability $p_{ij}$ of getting infected from $j$ in the timestep after $j$ is first infected. 

The original/classic paper for this problem is Maximizing the Spread of Influence Through a Social Network by Kempe, J. Kleinberg, and Tardos in 2003.1 If you search it on Google Scholar you'll see something like 1500 citations, so there is a lot of work in this area. You can see some on Jon Kleinberg's homepage under "Information Flow and Cascading Behavior in Networks"; he gave a survey talk on the area at this year's EC, but I don't know if the slides are available anywhere.

In 1, the authors show that, under several models of influence like those mentioned above, the "influence" of a set of vertices is a submodular function ; this allows greedy algorithms to find a set of initial nodes that gives a $1-1/e$ approximation to the best total influence. (However, solving the problem exactly is NP-hard.)

1 http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf