Information Technology Reference
In-Depth Information
Figure 6.7.
The elements in the web are evenly spaced on a circle and the probability of connecting any two
nodes is determined by the probability
p
:(a)
p
=
0
.
1; (b)
p
=
0
.
2.
L
N
(
p
)
=
E
max
p
,
(6.53)
which becomes more and more exact as
E
max
→∞
.For
p
=
0
.
1 the estimated num-
ber of links is between four and five, and for
p
=
0
.
2 it is about nine. In Figure
6.7
we assign three and nine links to the cases
p
=
0
.
1 and
p
=
0
.
2, respectively, for illus-
trative purposes. It is interesting to note that for
p
2 two triangles appear. These
triangles constitute our first meeting with the clustering phenomenon, but it is by no
means our last.
=
0
.
The Poisson distribution of links
Let us now evaluate the probability that a given node of a random network with
probability
p
has
k
links. The average number of links
z
is given by
z
=
(
N
−
1
)
p
.
(6.54)
We have
N
1 possible links to this specific node. Let us imagine that all these links
are contained in a box and that we decide to draw
k
of them to assign to a single node.
This can be done in a number of ways given by the combinatorial expression
N
−
−
1
(
N
−
1
)
!
≡
!
.
(6.55)
k
(
N
−
1
−
k
)
!
k
The probability of getting
k
links is
p
k
and the probability of not realizing
N
−
1
−
k
k
. Consequently, the probability of assigning
k
links to a given
node is determined by the product of these three expressions:
N
−
1
−
links is
(
1
−
p
)
N
p
k
−
1
N
−
1
−
k
p
k
=
(
1
−
p
)
.
(6.56)
k
Let us express (
6.56
) in terms of the average number of links
z
given by (
6.54
)to
obtain by direct substitution
N
z
N
k
1
N
−
1
−
k
−
1
z
p
k
=
−
(6.57)
k
−
1
N
−
1