This is a much studied question, at the crossroad of several fields: epidemiology, mathematics, statistical mechanics, and computer science, at least.
The model you consider is known as SI with parameter p, of which many variants exist.
The vaccination problem is very similar to the robustness problem: how many nodes may be removed from a network without breaking connectivity for most nodes. Here, the main criterion is the size of the largest connected component, seen as a bound for the size of any epidemics.
The problem is also related to the influence maximization problem, where one seeks for (sets of) nodes in a network that may effectively spread an information.
Mathematical approaches to all these problems are strongly related to the study of connected components in various kinds of random graphs. A much regarded question is the influence of the graph degree distribution, with various interesting threshold effects.
An approach that I like claims that, if you have no global knowledge of your network, then you should choose random nodes and ask them to cite a random person. This person is likely to have many contacts (the probability that it is cited is proportional to the number of persons knowing her), more than random individuals, and so she is a good vaccination target.
It is hard to choose among the many references I may cite on this topic, but I suggest the 2008 book "Dynamical Processes on Complex Networks" by Barrat, Barthélémy and Vespignani, Cambridge University Press. You may also search the web for the topics above.