Biology Reference
In-Depth Information
Erdős-Rényi
Random graph
S. cerevisiae
Protein-protein interaction network
E. coli
Metabolic interaction network
(A1)
(B1)
(C1)
(A2)
(B2)
(C2)
10
−1
In
Out
10
−1
10
−1
10
−2
10
−3
10
−2
10
−2
10
−3
10
−4
10
−3
10
−4
10
−5
10
−4
10
−5
10
−6
10
0
10
1
10
2
10
0
10
1
10
2
10
3
05
10
15
20
25
k
k
k
FIGURE 9.3
The degree distribution of the Erd
T
s
e
R´nyi network (A1) follows a Poisson (A2) as opposed to the cellular networks (B1) and (C1) for
which it follows a power-law (B2)
e
(C2). While the Poisson distribution is concentrated around the mean, the degrees observed in the cellular networks
range over several orders of magnitude. This non-uniformity of the cellular networks is expressed in the coexistence of dense and sparse patches visible in
the network graph. For the metabolic network, where the edges are directed, both the in-degree and the out-degree distributions are plotted. In all graphs
the dots represent the data, while the solid lines are fits to Poisson and to power-law distributions accordingly.
value of
g
becomes smaller. This means that smaller
g
values characterize more degree heterogeneous networks.
More specifically, Eq.
(2)
features three different regimes
as the value of
g
is changed. To observe this we consider
the value of the n th moment,
pathologies are removed once
g
3, as when the scaling
exponent is above this threshold, for many practical
purposes the scale-free nature of the distribution is no
longer relevant. These three regimes are also expressed in
the average path length of the network, as discussed in
more detail below.
k
n
h
i
, of the distribution, given
by
R
k
n
P
ð
Þ
dk. Note that for an infinite network, where k
ranges from zero to infinity, this integral diverges if n
k
g
2 the divergence is observed already at the
level of the first moment. In such cases, the distribution is
so broad that the average is undefined. In practice, when the
network is finite, this will take form in a topology where
almost all the nodes have degrees significantly lower than
the average, and a small minority of nodes will have such
a high degree that they connect directly to a significant
fraction of the nodes in the network, i.e., their degree is of
the order N. For 2
1. For
g
Network Integrity and the Role of Hubs
The SF topology allows for a disproportionate number of
highly connected nodes. These nodes play a crucial role in
the structural integrity of the network. To understand this
we consider the majority of nodes in the network, which
have only a few links. They are all likely to be connected to
the hubs by very short paths (of one or two edges). In
addition, any selected pair of hubs is also likely to be very
close to one another, due to the large number of links that
they have. The result is that in SF networks the path
between nodes becomes even shorter than in Erd˝s
e
R´nyi
networks, the hubs playing the role of network short-cuts
3 (typical of most cellular
networks) the distribution has a finite average, but the
second moment diverges. This means that the variance,
s
< g
2
, becomes undefined, capturing the high
2
k
2
¼h
ih
k
i
variability
of
the
distribution. These mathematical
