Biology Reference
In-Depth Information
For example, in the digraph of Figure
6.2
a, we have
ind
(
1
)
=
outd
(
1
)
=
2
=
outd
(
3
)
, while
ind
(
3
)
=
1. In a directed cycle graph
D
c
(
n
)
each node has indegree
and outdegree 1; in a complete loop-free digraph
D
max
(
n
)
each node has both indegree
and outdegree
n
1.
For nodes
v
in random digraphs, both
ind
−
are random variables. It
is easy to calculate the expected values of indegrees and outdegrees in Erdos-Rényi
digraphs.
Proposition 6.15.
(v)
and
outd
(v)
Let D be randomly drawn from
D
n
(
p
),
and let i
∈[
n
]
. Then
E
(
ind
(
i
))
=
E
(
outd
(
i
))
=
p
(
n
−
1
).
(6.7)
Proof.
This proof exemplifies a technique that is extremely useful in studying
random structures. For every potential arc
i
,
j
, define a random variable
ξ
i
,
j
that
takes the value 1 if
i
,
j
∈
A
D
and takes the value 0 if
i
,
j
∈
A
D
. Then
E
(ξ
i
,
j
)
=
p
·
1
+
(
1
−
p
)
·
0
=
p
. Moreover,
(
)
=
ξ
j
,
i
,
(
)
=
ξ
i
,
j
.
ind
i
outd
i
(6.8)
j
∈[
n
]\{
i
}
j
∈[
n
]\{
i
}
Since the expected value of a sum of random variables is the sum of their expected
values, we get
E
(
ind
(
i
))
=
E
(ξ
j
,
i
)
=
p
(
n
−
1
)
=
E
(ξ
i
,
j
)
=
E
(
outd
(
i
)),
(6.9)
j
∈[
n
]\{
i
}
j
∈[
n
]\{
i
}
as required.
The average indegrees and outdegrees correspond to the average number of
connections per neuron that can be estimated from empirical results even for those
networks where we do not know the actual connectivity graph. Notice that since the
uniform distribution
, nodes in a random loop-free digraph that
is drawn from this distribution will have average indegrees and outdegrees equal to
0
D
n
is equal to
D
n
(
0
.
5
)
5
n
. However, empirical results indicate that in neuronal networks of
actual organisms each neuron usually forms a lot fewer connections than that. For
example, as we mentioned in Section
6.2
, the human brain contains roughly 10
12
neurons, while individual neurons receive on average input from approximately 10
3
other neurons. This makes distributions
.
5
(
n
−
1
)
≈
0
.
with relatively small
p
more promising
candidates for predicting the dynamics of such networks than the uniform distribu-
tion. The probability
p
may in general depend on
n
, and we will often write
D
n
(
p
)
D
n
(
p
(
n
))
instead of
to emphasize this dependence.
There is a substantial literature on the study of Erdos-Rényi random
graphs,
which
are objects similar to digraphs, but with undirected
edges
D
n
(
p
)
{
i
,
j
}
instead of directed arcs
. These results tend to have straightforward translations into results on Erdos-
Rényi random digraphs. Project 6 [
1
] gives some references to the literature on the
subject. Many of these results go as follows: Suppose
p
i
,
j
(
n
)
is a function of the number
Search WWH ::
Custom Search