Full text of DOI:10.1007/s100510070218

Eur. Phys. J. B 16, 569–571 (2000)
THE EUROPEAN
PHYSICAL JOURNAL B
EDP Sciences
Societa` Italiana di Fisica
Springer-Verlag 2000
c
ꢀ
On social percolation and small world network
E. Ahmed and H.A. Abdusalama
1
Mathematics Department, Faculty of Sciences, UAE University, Al-Ain, PO Box 17551, Egypt
Mathematics Department, Faculty of Sciences, Cairo University, Giza, Egypt
2
Received 24 February 2000
Abstract. The social percolation model is generalized to include the propagation of two mutually exclusive
competing effects on a one-dimensional ring and a two-dimensional square lattice. It is shown that the result
depends significantly on which effect propagates first i.e. it is a non-commutative phenomenon. Then the
propagation of one effect is studied on a small network. It generalizes the work of Moore and Newman of
a disease spread to the case where the susceptibility of the population is random. Three variants of the
Domany-Kinzel model are given. One of them (delayed) does not have a chaotic region for some value of
the delay weight.
PACS. 05.50.+q Lattice theory and statistics (Ising, Potts, etc.) – 05.70.Fh Phase transitions: general
studies – 64.60.Ak Renormalization-group, fractals, and percolation studies of phase transitions
1 Social percolation
the movie) and if q1 ≥ p(i) then site i becomes of type
one. Else if one of its n.n. is of type two and if q2 ≥ p(i)
then site i is of type two.
The second propagation rule is, if site i is not affected
and if one of its n.n. is of type two and q2 ≥ p(i) then site
i becomes of type two. Else if one of its n.n. is of type one
and q1 ≥ p(i) then it becomes of type one. Consequently
this propagation has the order reversed compared to the
first rule.
In all our one-dimensional simulations we have 500
agents. Let q1 = 0.4, q2 = 0.8, and initially 10% of the
sites were informed about each effect i.e. at the beginning
a total of 20% of the lattice was already affected. When
the first rule is applied we obtained the average result
ρ1 = 0.271, ρ2 = 0.188 but in the case of the second rule
we obtained ρ1 = 0.156, ρ2 = 0.419. where ρ1(ρ2) is the
final fraction of sites of type 1(2).
Social percolation [1,2] is a model to relate a social trend
to percolation theory [3]. Consider the propagation of a
social effect such as say going to a movie. The society
members are assumed to occupy the sites of a lattice. Ev-
eryone can affect the opinion of his (her) nearest neigh-
bors (n.n.). Every site has its own threshold p(i) and also
the effect (movie) is given a value say q (a real number).
Initially a small number of sites are informed about the
movie. Then the propagation rule is: If an individual at
site i has not gone to the movie and if one of his (hers)
n.n. has seen it then if q > p(i) then agent i will go to the
movie. On a regular lattice this is a classical percolation
problem i.e. the effect will spread if q ≥ pc, where pc is
the critical concentration of the lattice.
In two dimensions we have an 80×80 square lattice and
the results are ρ1 = 0.411, ρ2 = 0.34 when the first rule is
followed while the second rule gave ρ1 = 0.186, ρ2 = 0.640.
This confirms that this propagation process is non-
commutative and shows the importance of reaching first
to the potential agents. This result depends also on the
assumption that the effects are mutually exclusive.
2 Two mutually exclusive effects on a regular
lattice
The situation becomes more interesting when two mutu-
ally exclusive effects (e.g. two movies but everyone has to
go only to one of them) compete to spread on the lattice.
As a corollary an individual will have to stick to its choice.
We assumed q2 = 2q1 hence one might intuitively expect
that the second effect will occupy twice as much as the first
one provided that the initial number of agents of each ef-
fect is the same. However the result depends significantly
on the order of spread i.e. which effect spreads first. Two
rules of propagation can be followed in this problem.
The first is, if an individual at site i is not yet affected
and if one of his (her) n.n is of type one (e.g. has seen
3 Small world network and social percolation
Small world networks [4–6] is a model proposed for social
networks. It is a one-dimensional ring plus shortcuts join-
ing some random sites. Here we consider shortcuts with
length k = 1 as seen in Figure 1. Let φ be the average
number of shortcuts per bond on the lattice, hence for
a large number (L) of sites in the lattice, the probabil-
ity that two random sites are connected by a shortcut
a
e-mail: hosny@math-sci.cairo.eun.eg

570
The European Physical Journal B
It is relevant to find an estimation of the number of
infected persons in the simple susceptible-infected (SI)
model studied above as a function of time [8]. Assume
that the speed of disease spread is unity and that the per-
sons occupy the vertices of a SWN, let φ be the fraction
of shortcuts hence 2φ is the density of shortcut-ends in
the graph. Setting p(i) = 0 ∀i hence the number of in-
fected persons will grow initially as a sphere with surface
Γdtd−1 where Γ1 = 2, Γ2 = 2π, Γ3 = 4π and so on. This is
called the primary sphere. Once a shortcut is reached (the
probability of such an event is 2φΓdtd−1 per unit time) a
secondary sphere forms and so on. Hence the total number
of infected persons is given by
Fig. 1. An example of a small-world graph with L = 26 sites
(black sites are occupied and white sites are empty) and 6
shortcuts with length k = 1.
Z
t
is Ψ ' 2kφ/L. Naturally the critical concentration of this
graph pc is smaller than the one for the ring pc = 1. To
derive the new pc the work of Moore and Newman will
V (t) = Γd
τd−1{1 + 2φV (t − τ)}dτ.
(5)
0
be used. Build the lattice starting form a connected lo- Defining V 0 = 2φV , t0 = t[2φΓd(d − 1)!]1/d and differen-
tiating d times with respect to t0 one gets ∂dV 0/∂t0d
1 + V 0 whose solution is
=
cal cluster then follow shortcuts. Let vi be the probability
that a local cluster of length i is included, hence in the
next step in the cluster building one has
X
∞
t0di
X
V 0( t0) =
·
(6)
vi0 =
Mijvj,
Mij ' ijΨNi,
(1)
(di)!
i=1
j
In one dimension one has V 0( t0) = exp(t0) − 1, in two
dimensions V 0(t0) = cosh(t0) − 1. For t0 < 1 the num-
ber of infected persons grow as a power law t0d/d! while
for t0 > 1 it grows exponentially. The transition occurs at
t0 = 1 i.e. at t = [2φΓd(d − 1)!]. This has an important
effect on vaccination policies since it implies that vaccina-
tion should be administered as early as possible and with
the highest possible ability to avoid reaching the exponen-
tial phase. Also immunizing sites with shortcuts is more
efficient than immunizing ordinary sites. This idea of tar-
get immunization and target disease resistance has been
proposed in more realistic situations e.g. schistosomiasis.
Now we study SIRS (susceptible-infected-recovered-
susceptible) [9] on a small world network. The study on
an ordinary lattice has been done in [10]. A state s(i) is
assigned to each vertex i at time t. s(i) = 0 for suscepti-
ble, s(i) = −1 for infected and infecting, and s(i) = 1 for
recovered, where i = 1, 2, ..., n (n = 500). The graph is
a small world network as defined by Newman and Watts
and the automata rules are:
for full derivation see [7]. If the maximum eigenvalue of
Mij is less than one then the propagation process will
eventually stop otherwise it will propagate throughout the
cluster. Thus the critical concentration corresponds to the
eigenvalue one i.e.
X
X
1 + p
1 − p
Mijvj = λvi =⇒ λ = Ψ
j2Nj =⇒ λ = 2φp
·
j
j
(2)
(3)
(4)
So the critical concentration is
p
4φ2 + 12φ + 1 − 2φ − 1
pc =
·
4φ
For small φ, we can write,
pc ' 1 − 4φ.
Now consider the propagation across a small world net-
work. We consider the spread of an epidemic in a popula-
tion with random susceptibility thus our work generalizes
that of Moore and Newman. In our simulations φ = 0.05
and shortcuts are assigned randomly from the beginning.
The propagation rule is: if site i is not affected and
if one of its n.n. or its shortcut neighbor (if exists) is af-
fected and if q ≥ p(i) then site i will be affected. This
model corresponds to the spread of an epidemic with force
of infection q in a population with random susceptibilities
p(i). For q = 0.4 we found that the disease infected 19%
of the population if they live on a ring. Adding shortcuts
increased the infection to 23%. Similarly for q = 0.9 the
infected percentage increased form 69% in the case of a
i) if s(i) = −1 then s1(i) = 1;
ii) if s(i) = 1 then s1(i) = 0 with probability q2;
iii) if s(i) = 0 and s(i + 1) = −1 or s(i − 1) = −1 or
s(sc(i)) = −1 then s1(i) = −1 with probability q
where sc(i) is the shortcut neighbor of site i (if exis-
tent). We obtained that the boundary separating the
regions where the disease persists (region II) or disap-
pears (region I) is given by the following set of points
in the (q, q2) plane
{(0.66, 1), (0.7, 0.87), (0.8, 0.5), (0.9, 0.27), (1, 0.18)}. (7)
ring to 75% to the case of a small world network. Recall As expected the region where the disease persists has in-
that without shortcuts the disease cannot spread through- creased in the SWN case compared to the regular graph
out the lattice except only at q = 1.
case [10], as seen in Figure 2.

E. Ahmed and H.A. Abdusalam: On social percolation and small world network
571
ii) if sum = 1 then s1(i) = 1 with probability p1 else
s1(i) = 0;
iii) if sum = 2 then s1(i) = 1 with probability p2 else
s1(i) = 0;
where sum is defined by
sum = Int{ω[s(i, t) + s(i + 1, t)]
+(1 − ω)[s(i, t − 1) + s(i + 1, t − 1)] + 0.5}, (8)
where 1 ≥ ω > 0 is the delay weight and Int[x] is the
integer part of x. Our simulations have shown that, on a
regular graph the introduction of delay reduces the chaotic
region and that for the value ω = 0.5 the chaotic region
disappears.
Fig. 2. The phase space of two distinct regions. In the first
(region I), the disease disappears while in the second (region II)
it persists.
5 Conclusions
In conclusion, in the first part of this work, the social
percolation problem has been studied. In the second part,
the social percolation model is generalized to include the
propagation of two mutually exclusive competing effects
on a one-dimensional ring and a two-dimensional square
lattice. It is noticed that the propagation process is a non-
commutative phenomenon.
In the third part, the propagation of one effect is stud-
ied on a small world network and the work of Moore and
Newman of a disease spread is generalized to the case
where the susceptibility of the population is random. We
found that the region where the disease persists has in-
creased in the small world network case compared to the
regular graph case.
In simulating a small world network one usually fixes
the sites connected by shortcuts beforehand. However, it
may be easier in simulation if one determines them ran-
domly (with probability φ) during simulation. We call this
network a random small world network RSWN. Presum-
ably this will not significantly alter the simulation results.
Anyway, all the simulations done here are on the standard
small world network SWN.
4 Domany-Kinzel model on SWN
Finally, three variants of the Domany-Kinzel model are
given and generalized by using the ideas of social percola-
tion and small world network. Our simulations have shown
that, on a regular graph the introduction of delay reduces
the chaotic region and that for some value of the delay
weight, the chaotic region disappears.
The Domany-Kinzel (DK) model [11,12] is an interesting
realization of directed percolation. Here it is generalized
using ideas form social percolation and SWN.
The first version has every site in a one-dimensional
lattice endowed with a random number p(i). Then the
evolution rules are:
References
i) if s(i) = 0 and s(i + 1) = 0 then s1(i) = 0;
ii) if s(i) + s(i + 1) = 1 then if p1 ≥ p(i) then s1(i) = 1
else s1(i) = 0;
iii) if s(i) + s(i + 1) = 2 then if p2 ≥ p(i) then s1(i) = 1;
where s1(i) is s(i) in the next run. We studied only the
case p2 = 0 and found that for 0 ≤ p1 ≤ 0.6 the results
were 2-cycle, for 0.6 ≤ p1 ≤ 0.8 the number of active sites
(s(i) = 1) was a 4-cycle and for p1 ≥ 0.8 the number
changes chaotically with time.
The second version is to model the Domany-Kinzel
model on a SWN. In this case we set φ = 0.05 and p2 = 0.
Only a slight change in the critical value of p1 = 0.79
instead of the standard p1 = 0.8 for DK model on the
ring. The full phase diagram of the modified DK model
will be reported elsewhere.
1. S. Solomon, G. Weisbuch, Social Percolation Models,
Adapt-org 9909001.
2. S. Solomon, G. Weisbuch, L. de Arcangelis, N. Jan, D.
Stauffer, Social Percolation Models, Physica A 277, 239
(2000).
3. D. Stauffer, A. Aharony, Introduction to Percolation The-
ory (Taylor and Francis, London, 1994).
4. D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998).
5. M.E.J. Newman, D.J. Watts, Phys. Lett. A 263, 341
(2000).
6. A. Barrat, M. Weigt, Eur. Phys. J. B 13, 547 (2000).
7. C. Moore, M.E.J. Newman, Phys. Rev. E (submitted),
cond-mat 9911492.
8. C.F. Moukarzel, Phys. Rev. E 60, R6263 (1999).
9. L. Edelstein-Keshet, Mathematical Models in Biology
(Random House N.Y., 1988).
10. E. Ahmed, H.N. Agiza, Physica A 253, 347 (1998).
11. E. Domany, W. Kinzel, Phys. Rev. Lett. 53, 311 (1984).
12. P. Grassberger, J. Stat. Phys. 79, 13 (1995).
A third version which is applicable on any graph is the
delayed DK model. It is given by the rules:
i) if sum = 0 then s1(i) = 0;