Biology Reference
In-Depth Information
use the Erd˝s
e
R´nyi network to exemplify them. The
most basic characteristic of a node is its degree, k,defined
as the number of links it has to other nodes in the network.
In the Erd˝s
e
R´nyi graph every node can potentially be
linked to any of its N
(A)
3
9
2
1 counterparts with independent
4
10
1
probability
p. The
average
degree will
thus
be
h
pN. The random nature of this network
invokes some variability in the degree of the nodes, so that
several nodes will have more links than the average, while
others will have less. This variability can be described by
the degree distribution of the graph. Denoted by P
k
i¼
p
ð
N
1
Þ
z
5
6
8
7
,itis
defined as the probability that a randomly selected node
will have exactly k links. As we will see later, the degree
distribution is one of the most fundamental characteristics
of a network, carrying crucial information about its
evolution and formation process. In the Erd
˝
s
e
R
´
nyi
network P
ð
k
Þ
(B)
3
9
2
4
ð
Þ
10
follows a Poisson distribution, which indi-
cates that most nodes are characterized by roughly the
same degree, the probability to encounter a node with
a degree significantly different than
k
1
5
being vanishingly
small. The average degree is thus the characteristic scale
of the degree distribution.
In directed networks, we distinguish between the
in-degree of a node, denoting the number of incoming
links, and the out-degree, denoting the number of outgoing
links. For instance, if gene x regulates n other genes, it will
have an out-degree of k
out
¼
h
k
i
6
8
7
FIGURE 9.1
(A) An undirected network which includes 10 nodes. The
network path between nodes 1 and 8 is emphasized (red). (B) In the
directed version of this network, the path must advance in accordance with
the direction of the edges.
n, whereas if it is being
regulated by m other genes, its in-degree will be k
in
¼
m.
Accordingly, the degree distribution in such networks is
split into the incoming distribution P
ð
k
in
Þ
and the outgoing
emerge as long as
h
k
i
1. Moreover, in the case where
distribution P
. As an example, consider node number
four in
Figure 9.1
, which in the undirected version of the
graph (a) has a total degree of k
ð
k
out
Þ
1
ln N, this giant component is likely to
encompass almost all of the nodes in the network
[6,27]
.
Networks impose a unique metric by which the distance
between nodes can be measured. Consider the network path
between a pair of nodes. Its length is defined as the number
of links it crosses. The length of the shortest path between
a pair of nodes, x and y, is the network distance, l
xy
.
Figure 9.1
(a) displays the shortest path between nodes 1
and 8 . The network distance between these two nodes is
l
1
;
8
¼
h
k
i
5, while in the directed
version (b) it is characterized by k
in
¼
¼
2 and k
out
¼
3.
Network Paths and the Small World
Phenomena
A crucial feature of any biological network is its ability to
maintain a flow of information, mass or energy, between
all of its nodes. From the graph theoretical perspective
this requirement translates into the existence of a network
path connecting all (or most) of the nodes in the network.
By network path we refer to a route leading from one
node to another by passing solely over existing links
(
Figure 9.1
). Such a group of interconnected nodes
constitutes a connected component, and if indeed a large
fraction of the nodes in the graph can be reached from one
another via these network paths, the graph is said to have
a giant connected component. This seemingly remote
feature appears rather frequently and does not require
much high-level organization for it to be observed. In
fact, for an Erd˝s
e
R´nyi graph, a giant component will
4. If no such path exists, then the pair of nodes
cannot communicate with one another and their distance is
set to be infinite. The distance between a pair of nodes
parameterizes the potential to propagate information from
one to the other, such that close nodes are more likely to
affect one another than far-away nodes. Averaging over all
pairs of nodes in the network gives the average path length
of the network,
, which offers a measure of the network's
overall connectivity. If the network includes infinite paths,
i.e., has isolated components, the averaging is commonly
carried out over the nodes belonging to the giant connected
component. For an Erd˝s
e
R´nyi network (as well as
almost all other random networks) we find that the average
path length is strikingly small compared to the network
size. To understand this we focus on the surrounding of
h
l
i
