Improving immunization strategies
Improving immunization strategies
Lazaros K. Gallos1, Fredrik Liljeros2, Panos Argyrakis1, Armin Bunde3, and Shlomo Havlin4
Department of Physics, University of Thessaloniki, 54124 Thessaloniki, Greece
Department of Sociology, Stockholm University 106 91 Stockholm, Sweden
Institut für Theoretische Physik III, Justus-Liebig-Universität Giessen,
Heinrich-Buff-Ring 16, 35392 Giessen, Germany and
Minerva Center and Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel
(Dated: November 20, 2018)
We introduce an immunization method where the percentage of required vaccinations for immunity
are close to the optimal value of a targeted immunization scheme of highest degree nodes. Our
strategy retains the advantage of being purely local, without the need of knowledge on the global
network structure or identification of the highest degree nodes. The method consists of selecting
a random node and asking for a neighbor that has more links than himself or more than a given
threshold and immunizing him. We compare this method to other efficient strategies on three real
social networks and on a scale-free network model, and find it to be significantly more effective.
PACS numbers: 89.75.Hc, 87.23.Ge
Immunization of large populations through vaccination
is an extremely important issue with obvious implications
for the public health [1, 2, 3]. The eradication of Small
Pox through a global mass vaccination campaign during
the second part of the 20th century represents, for exam-
ple, a landmark in the history of the medical sciences [4].
Global or national mass vaccination may however not al-
ways be possible. The number of vaccinated people may
need to be minimized due to severe side effects of vacci-
nation such as for Small Pox, or temporary shortage of
vaccine that could be the case for a pandemic influenza.
The cost for a vaccine may also be an important limiting
factor. Improving efficiency of immunization is thus an
urgent task.
Recently [5], developments in the study of population
connectivities helped researchers in the field to present
new ideas on immunization, based on the heterogeneity
in the number of contacts between individuals. A number
of strategies have been proposed for lowering the required
minimum fraction fc of the population to be immunized.
The problem can be mapped to the well-known percola-
tion problem where nodes are immunized (removed) up
to a concentration fc, above which the spanning clus-
ter does not survive. Random immunization of nodes
has been shown incapable of protecting the population
when the contacts distribution is wide, since the perco-
lation threshold is close to fc = 1, i.e. practically all
nodes need to be immunized [6, 7, 8]. The best known
strategy today is believed to be targeted immunization,
where the highest connected nodes in the system are im-
munized in decreasing order of their degree. In this case
fc is less than 10% [7, 9, 10]. For all practical applica-
tions, though, this approach is unrealistic because it is
a ‘global’ strategy and requires a complete knowledge of
the high degree nodes, which is in many cases impossi-
ble. An effective strategy, called acquaintance immuniza-
tion, was recently introduced [11] that combines both ef-
ficiency and somewhat greater ease of applicability. Ac-
cording to this scheme a random individual is selected
who then points to one of his random acquaintances and
this node is the one to be immunized. This method is
more efficient compared to random immunization (fc is
of the order of 20-25%) but less efficient than targeted
immunization.
In this paper we introduce an immunization method,
which is practically as efficient as the accepted as opti-
mum strategy, but at the same time depends on local in-
formation only. The method consists in selecting random
individuals and asking them to direct us to their friend
who is more connected than they are and this acuain-
tance is immunized. If such a friend does not exist we
continue with another random selection. Alternatively,
in a second variation of the method we ask the randomly
chosen individual to point us to a random neighbor that
has a number of neighbors larger than e.g. k = 5 (or
an equally small and easily countable threshold value).
If they point to such an individual it is immunized, oth-
erwise we select another individual. Similar results are
obtained if the chosen individual is asked to estimate his
own number of contacts, rather than of his random neigh-
bor. Although this procedure is simpler, the selection of
a neighbor can also eliminate the bias that may be in-
troduced due to selfish people, lying about their contacts
in order to receive the vaccine themselves. The method
is proposed for social networks, but it is expected that
it can be even more efficient for technological networks,
such as e.g. the Internet, where the number of links for
a given node is exactly known to the local network ad-
ministrator, and need not be estimated.
Our method is local because the decision for immu-
nization of a given node is taken without the need to
know the connectivity of other nodes. This is in contrast
with global strategies where immunization of a node has
to be decided only after we have gathered information for
the entire network. This means that for immunization of
e.g. a city or a country in a global method we have to
http://arxiv.org/abs/0704.1589v1
send special teams to collect this information and trans-
mit it to a central place. This central authority decides
then which nodes should be immunized and transmits
back the outcome to the local authorities which then go
on with vaccinations. For a local method, there is no
need to collect or compare data from other areas of the
network. Based on the answer of each individual the de-
cision is made immediately on whether a node should be
immunized or not.
We study the proposed method on real social networks
with a fat tail in their degree distribution, as well as on
a random scale-free model network. We also compare
this method with several other immunization strategies,
including such that partial knowledge on the global net-
work of contacts is available and we demonstrate the ad-
vantage of the proposed method via the improvement in
The social networks used in this study represent dif-
ferent interactions among the members of an online com-
munity, as described in Ref. [12]. These interactions in-
clude a) exchange of messages, b) signing of guestbooks,
c) flirt requests, and d) established friendships. The first
three networks are directed but we consider only their
undirected projection, by transforming arcs into edges.
No significant difference is observed in the results for
the undirected network and the projections of the di-
rected networks. The size of the networks is of the order
N = 104. The percentage of immunized nodes is denoted
with f , while the percentage of nodes suveyed is denoted
with p. The four strategies that we employ are summa-
rized below. Strategy I: Immunize a node with probabil-
ity proportional to kα, where k is the number of connec-
tions and α tunes the probability of preferentially select-
ing high-connectivity or low-connectivity nodes. Large
positive values of α tend towards mainly selecting the
hubs (α → ∞ is equivalent to targeted immunization),
the value α = 0 represents the random immunization
model, while negative α values lead to selecting the lower-
connected nodes [13]. This parameter can be interpreted
as a measure of the extent of our knowledge on the struc-
ture. Strategy II: Select a node with probability propor-
tional to kα and immunize a random acquaintance of this
node. The value α = 0 corresponds to the acquaintance
immunization scheme [11]. Strategy III: Select a random
node and immunize one of its acquaintances i, with prob-
ability proportional to kαi , where ki represents the degree
of the neighbor. Strategy IV: Select a random node and
ask for an acquaintance, which is immunized if a cer-
tain condition is met. We study two variations: a) The
selected node points randomly to a node which is more
connected than himself. If there are no such neighbors
no node is immunized. b) The selected node is asked
to choose a random neighbor with degree larger than a
threshold value kcut then this acquaintance is immunized.
Equivalently, we can ask the node to estimate its own de-
gree. If it is larger than a threshold value we immunize
-3 -2 -1 0 1 2 3
-3 -2 -1 0 1 2 3
(b) Guestbook(a) Messages
(c) Flirt
(d) γ=2.5
II II
IV IV
FIG. 1: Critical immunized fraction fc of the population as
a function of α for (a)-(c) Real-life social networks, and (d)
scale-free network model with γ = 2.5. Four different strate-
gies are used as described in the text and indicated in the
plot. The two symbols correspond to the critical fraction
for the strategies of the enhanced acquaintance immuniza-
tion method (the open circle corresponds to asking for an
acquintance with threshold kcut = 7, while the filled circle
corresponds to asking for a better connected node).
the node, otherwise we ignore it. These two variations are
similar when kcut = 〈k〉. We call strategy IV “enhanced
acquaintance immunization” (EAI) method.
In Figs. 1a-c we present the results of fc for the four de-
scribed strategies applied to three of the social networks,
as defined by different types of interactions. All networks
follow similar patterns for a given strategy. In strategy
I we can see the abrupt decrease of fc when increasing
α from α ≤ 0 (random immunization) with fc = 1 to
α = ∞ (targeted immunization) with fc ≪ 1. Strategy
II presents an improvement over the first strategy for val-
ues α . 1. The critical value fc presents a minimum at
α ≃ 1, indicating that identification of large hubs actu-
ally deteriorates the results, since the neighbors of large
hubs, which are chosen to be immunized, are with higher
probability low degree nodes for dissasortative networks,
similarly with the acquaintance immunization method
[11]. Strategy III leads to monotonic decrease in fc and
prevails from the first two methods when we have limited
global network knowledge, i.e. in the range α ∈ [0, 1].
However, in Strategy III we find that when α = ∞ (i.e.
we always immunize the most connected neighbor) it may
be impossible to destroy the spanning cluster, because al-
most all selected nodes point to the same hubs. Finally,
the enhanced acquaintance immunization strategy seems
to be the most efficient method, although it assumes no
1 2 3 4 5 6 7
1 2 3 4 5 6 7
(a) Messages (b) Guestbook
(c) Flirt
(d) γ=2.5
FIG. 2: Critical immunized fraction fc of the population as
a function of the threshold value kcut for the enhanced ac-
quaintance immunization strategy applied to (a)-(c) social in-
teraction networks, (d) random model scale-free network with
γ = 2.5 (of size N = 105 nodes). Filled symbols correspond to
immunizing a random neighbor of the selected node if its de-
gree is ≥ kcut and open symbols to immunizing the selected
node itself. The upper horizontal dotted line is the result
for acquaintance immunization, the dashed line in the middle
corresponds to immunizing a more connected acquaintance,
while the lower line refers to targeted immunization.
knowledge of the underlying structure (the method is in-
dependent of α). The value of fc is lower than an attack
with α = 3 and very close to the results of the targeted
immunization.
To gain more insight into the different immunization
methods we also performed numerical simulations on a
model network. We consider each member of a popula-
tion represented by a node, while the acquaintances of a
person with other people form links. It is well established
that many social networks follow a broad distribution in
the degree of a node, such as the power-law distribution
P (k) ∼ k−γ , where the exponent γ is usually found to
be between 2 < γ < 4 [5, 14, 15, 16]. The above real
networks are scale-free with γ ≃ 2.4[12]. The results in
Fig. 1d correspond to the four strategies in such a model
network (created with the configuration random model
[17]) with exponent γ = 2.5, which is close to the re-
ported exponent γ ≃ 2.4 of the real networks used. All
strategies in this plot follow closely the results for the
real networks.
The two ‘transition’ points for the first three strategies
are located at α = 0 and α = 1. At α = 0, strategies II
and III coincide. In the range α ∈ [0, 1] strategy III is
0 0.1 0.2 0.3 0.4
0 0.1 0.2 0.3 0.4
P∞(f)
P∞(f)
1 2 3 4 5 6 7
1 2 3 4 5 6 7
(b) Guestbook(a) Messages
(c) Flirt (d) γ=2.5
FIG. 3: Size of epidemics, measured via the fraction of nodes
belonging to the largest cluster over the number of not-
immunized nodes P∞(f), as a function of the fraction f of im-
munized nodes. In each plot, from top to bottom, the curves
correspond to acquaintance immunization, EAI redirecting to
a better connected node, the EAI with kcut = 7, and targeted
immunization. (a)-(c): real networks, and (d): random scale-
free network with γ = 2.5. Insets: Ratios for f1/fc of the
critical immnunized fraction fc over the critical fraction f1
for acquaintance immunization (kcut = 1) and pc/p1, i.e. the
number of people surveyed, as a function of kcut for the EAI
method.
more efficient, indicating that in this range it is preferable
to let the nodes choose their neighbors according to their
connectivity, rather than selecting nodes with probabil-
ity proportional to kα and following random links. The
value α ≃ 1 is the optimum value for strategy II. In prac-
tice, the process is equivalent to selecting a random link
and immunizing one of the two nodes attached to the
given link (provided the uncorrelated network hypothe-
sis holds). It is also interesting to note that up to the
value α = 1 the acquaintance immunization strategy is
superior to direct immunization of the initially selected
nodes, but close to this value the two methods yield a
similar value for fc. When α > 1 the direct immuniza-
tion method becomes more efficient than acquaintance
immunization.
The enhanced acquaintance immunization is, however,
found to be superior to all the above methods. The value
of fc for a given kcut value is of course independent of α,
meaning that it works equally well when there is no fur-
ther information on the network structure, i.e. global
knowledge does not offer any significant advantage over
completely random selections. Thus, the strategy is local
and easy to implement. The choice of kcut, though, influ-
ences fc and can further reduce the fc value when more
accurate knowledge on the network structure is available.
The gain of this method for kcut = 7 when compared to
the original acquaintance immunization method is about
a factor of 4, which is for practical purposes a significant
improvement. This striking variation is evident in Fig. 2,
where the critical percentage decays from fc ≃ 0.26 at
kcut = 1 (acquaintance immunization) to fc ≃ 0.06 at
kcut = 7. For kcut = 7 the strategy works comparably
well to the targeted immunization. The fraction fc, how-
ever, remains very low even when the cutoff value kcut
decreases to values close to, but less than 7. This stabil-
ity over the value of kcut offers greater flexibility since the
method seems tolerant to mistakes of lower degree nodes
being pointed at for immunization, without siginificant
loss in the efficiency (even at a value of kcut = 4 the
critical fraction fc remains lower than 10%). The results
are different when we immunize directly the initially se-
lected random node (without asking for an acquaintance)
and only at kcut = 7 the two methods seem to coincide
(Fig. 2). There exists, though, a critical degree above
which this strategy no longer works, simply because the
number of nodes with degree larger than this value is
smaller than the critical number needed for complete im-
munization. Thus, it seems preferable to remain con-
servative on the estimation of kcut and choose a smaller
value over a larger one.
A considerable advantage is gained, even when the
question is posed in a much simpler way, i.e. we ask
a random node to direct us to a friend who is better con-
nected than his and immunize him. This simple approach
already offers a significant improvement over the original
acquaintance method, as is evident in Fig. 2, although it
is not as efficient as when asking for a friend whose degree
exceeds the cutoff value. Since it is, however, much easier
for an individual to estimate an acquaintance who is bet-
ter connected than himself, and practically everyone can
understand and correctly answer this simple question, we
consider this method as a useful strategy which is easy
to apply in real-life situations.
In order to assess the size of the epidemics in the im-
munization process we measure the size of the spanning
cluster (epidemics size) as a function of the immunized
nodes f . In Figs. 3a-c we present the fraction of nodes
belonging to the spanning cluster over the total number
of non-immunized nodes for the real networks described
above and compare the targeted immunization with the
enhanced acquaintance immunization and the original ac-
quaintance immunization methods. The results for the
model scale-free networks (Fig. 3d) are averages over 100
different realizations of networks with exponent γ = 2.5.
In all cases the critical fraction for the targeted immu-
nization and the EAI with the cutoff value are similar,
while acquaintance immunization leads to considerably
higher values of fc. Again, the EAI with an estimation
of a better connected friend yields a result between these
two extremes. However, during the removal process the
targeted immunization yields the faster decomposition of
the spanning cluster, since it first removes the most con-
nected nodes in the system. The results for all the ac-
quaintance immunization methods depend on when these
largest hubs will be selected and the averaging conceals
the fact that during one realization the size of the largest
cluster drops abruptly when the largest hubs are selected.
Despite this, the proposed methods follow closely the re-
sults of targeted immunization, while retaining the ad-
vantage of being local.
In the insets of Fig. 3 we can see that compared to the
acquaintance immunization method (which is the EAI
method with kcut = 1) in general we need to survey more
nodes for their acquaintances as kcut increases, but this
is a small change compared to the improvement in the
number of required immunizations presented in the same
plots.
A work with similar scope was performed by Holme
[18]. Among other methods, an immunization scheme
was introduced, where a random node points to one of its
highest degree neighbors or to its most connected neigh-
bor. This corresponds to strategy III of the current work
with α → ∞ (where we encounter the problem of select-
ing always the same nodes as described above) and the
first variation of Strategy IV. The results in that paper
are consistent with the ones presented above for these
limiting cases.
In summary, we introduced and compared various im-
munization strategies on real and model networks. We
have shown that the fraction of immunized nodes can
be significantly reduced to the almost optimum level of
intentional immunization using a completely local infor-
mation strategy. This simple process is enough to ensure
that the immunization threshold is significantly lowered,
as compared to other local methods.
We thank R. Cohen and D. Brewer for useful discus-
sions. This work was supported by a European research
NEST/PATHFINDER project DYSONET 012911, by a
project of the Greek GGET in conjunction with ESF and
by the Israel Science Foundation.
[1] R.M. Andserson and R.M. May, Infectious Diseases of
Humans: Dynamics and Control (Oxford University
Press, Oxford, U.K., 1992).
[2] T. Britton, J. R. Stat. Soc. B 63, 705 (2001).
[3] F. Ball, D. Mollison, and G. Scalia-Tomba, Ann. Appl.
Prob. 7, 46 (1997).
[4] H. Bazin, The Eradication of Small Pox: Edward Jenner
and the First and Only Eradication of a Human Infec-
tious Disease (Academic Press, London, 2000).
[5] R. Albert and A.-L. Barabasi, Rev. Mod. Phys. 74, 47
(2002).
[6] R. Cohen et al., Phys. Rev. Lett. 85, 4626 (2000).
[7] D.S. Callaway et al., Phys. Rev. Lett. 85, 5468 (2000).
[8] R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett.
86, 3200 (2001).
[9] R. Albert et al., Nature 406, 378 (2000).
[10] R. Cohen et al., Phys. Rev. Lett. 86, 3682 (2001).
[11] R. Cohen et al., Phys. Rev. Lett. 91, 247901 (2003).
[12] P. Holme et al., Soc. Networks 26, 155 (2004).
[13] L.K. Gallos et al., Phys. Rev. Lett. 94, 188701 (2005).
[14] S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Net-
works: From Biological nets to the Internet and WWW
(Oxford University Press, 2003).
[15] R. Pastor-Satorras and A. Vespignani, Evolution and
Structure of the Internet, (Cambridge Univ. Press, 2004).
[16] M.E.J. Newman, SIAM Review 45, 167 (2003).
[17] M. Molloy and B. Reed, Random Struct. Algor. 6, 161
(1995); Comb. Probab. Comput. 7, 295 (1998).
[18] P. Holme, Europhys. Lett. 68, 908 (2004).
