Acquaintance Immunization

Image from inSPOT a nonprofit Internet notification service that allows you to send e-cards to your sex partners to break the bad news that they should get tested. Cards can be sent anonymously but they suggest, not unreasonably, that cards with a name are much more effective.

On a related note tell me that this isn't a good idea:

It is well established that random immunization requires immunizing a very large fraction of a computer network, or population, in order to arrest epidemics that spread upon contact between infected nodes (or individuals. Many diseases require 80%– - 100% immunization (for example, measles requires 95% of the population to be immunized). The same is correct for the Internet, where stopping computer viruses requires almost 100% immunization. On the other hand, targeted immunization of the most highly connected individuals, while effective, requires global information about the network in question, rendering it impractical in many cases. Here, we develop a mathematical model and propose an effective strategy, based on the immunization of a small fraction of random acquaintances of randomly selected nodes. In this way, the most highly connected nodes are immunized, and the process prevents epidemics with a small finite immunization threshold and without requiring speci fic knowledge of the network.

From a paper entitled 'Efficient Immunization Strategies for Computer Networks and Populations' in Physical Review Letters.

So, for example, for a sexually transmitted disease you would only need the identity of a single sexual partner from a large sample of people (unfortunately this should be a random selection from those available which may cause difficulties). You then collate this information and target your vaccination on those names that come up the most frequently (most likely the 'superspreaders' in this case). But you have identified them without constructing the whole partner network.