Biology Reference
In-Depth Information
probability distribution
D
n
.If
Ch
is a characteristic property of digraphs, then we
can say that
a typical digraph drawn from these distributions has property Ch
if the
probability that a digraph drawn from
.
We can talk about
typical dynamics
of networks with connectivities drawn from the
distributions
D
n
has property
Ch
approaches 1 as
n
→∞
D
n
in a similar fashion.
The most straightforward implementation of this idea is obtained by assuming that
D
n
is the uniform distribution on the set of all loop-free digraphs
D
=[
n
]
,
A
D
.
For this distribution, consider a potential arc
i
,
j
with
i
,
j
∈[
n
]
and
i
=
j
. Notice
that
i
,
j
is contained in the arc set of exactly half of all digraphs in
D
n
. Thus
P
(
i
,
j
∈
A
D
)
=
0
.
5. Similarly, if
i
1
,
j
1
,...,
i
,
j
,...,
i
m
,
j
m
are pairwise
distinct potential arcs, then
2
−
m
P
(
∀
k
∈[
]
i
k
,
j
k
∈
A
D
and
∀
k
∈[
m
]\[
]
i
k
,
j
k
∈
A
D
)
=
.
(6.5)
A
D
are
independent.
This formula is very useful. For
example, it immediately implies the following:
Proposition 6.13.
In a typical loop-free digraph drawn from the uniform distribution
every two nodes will be connected by a path of length 2
Thus the events
i
,
j
∈
;
in particular
,
the digraph
will be strongly connected.
Proof.
If
i
=
j
are different nodes, then
3
n
−
2
4
n
−
2
.
P
(
∀
k
∈[
n
]\{
i
,
j
}
i
,
k
∈
A
D
or
k
,
j
∈
A
D
)
=
(6.6)
Note that Eq. (
6.6
) gives the probability of the event that there does
not
exist a
directed path of length 2 from
i
to
j
. Now consider the event
F
that for
some i
,
j
with
i
=
j
there does not exist a path of length 2 from
i
to
j
. There are
n
(
n
−
1
)
ordered
pairs
j
, and the probability of a union of events is always
bounded from above by the sum of their probabilities. It follows from Eq. (
6.6
) that
P
i
,
j
with
i
,
j
∈[
n
]
,
i
=
3
n
−
2
(
F
4
n
−
2
.
Note that lim
n
→∞
n
)
n
(
n
−
1
)
3
n
−
2
4
n
−
2
F
c
1, where
F
c
denote
s
(
n
−
1
)
=
0. Thus lim
n
→∞
P
(
)
=
the complement of event
F
.
It follows from Eq. (
6.5
) that
D
n
is exactly the probability distribution of random
digraphs on
[
n
]
that can be constructed in the following way: For each potential arc
in
A
D
if and only if the coin comes up heads.
One can generalize this construction to the case where the coin is not fair and comes
up heads with probability
p
, which can be an arbitrary number with 0
i
,
j
, flip a fair coin. Include
i
,
j
<
p
<
1. The
corresponding probability distributions will be denoted by
. These distributions
give the classes of so-called
Erdos-Rényi
random loop-free digraphs.
Definition 6.14.
Let
D
D
n
(
p
)
=
V
D
,
A
D
be a digraph and let
v
∈
V
D
.The
indegree
of
v
, denoted by
ind
(v)
, is the number of
w
∈
V
D
with
w, v
∈
A
D
.The
outdegree
of
v
, denoted by
outd
(v)
, is the number of
w
∈
V
D
with
v, w
∈
A
D
.
Search WWH ::
Custom Search