  We investigate methods to vaccinate contact networks -- i.e. removing nodes
in such a way that disease spreading is hindered as much as possible -- with
respect to their cost-efficiency. Any real implementation of such protocols
would come with costs related both to the vaccination itself, and gathering of
information about the network. Disregarding this, we argue, would lead to
erroneous evaluation of vaccination protocols. We use the
susceptible-infected-recovered model -- the generic model for diseases making
patients immune upon recovery -- as our disease-spreading scenario, and analyze
outbreaks on both empirical and model networks. For different relative costs,
different protocols dominate. For high vaccination costs and low costs of
gathering information, the so-called acquaintance vaccination is the most cost
efficient. For other parameter values, protocols designed for query-efficient
identification of the network's largest degrees are most efficient.

Populations and Evolution;Physics and Society