Biomedical Engineering Reference
In-Depth Information
3.
NETWORKS MODELS
The main role of network models is to explain the emergence and behavior
of some of the most important network characteristics. As they play a crucial
role in shaping our understanding of complex networks, we need to pay atten-
tion to some of the more important models.
3.1. Random Networks
While graph theory initially focused on regular graphs, since the 1950s
large networks with no apparent design principles, described as random graphs
(8), were proposed as the simplest and most straightforward realization of a
complex network. According to the Erdös-Rényi (ER) model of random graphs
(13), we start with
N
nodes and connect each pair of nodes with probability
p
,
creating a graph with approximately [
pN
(
N
- 1)]/2 randomly distributed links
(first column in Figure 3). The ER graph has an exponential degree distribution
and exhibits the small-world property. Indeed, in the ER network most nodes
have approximately the same number of links,
k
<
k
> (first column in Figure
4), and the mean path length is proportional to the network size, <
l
> ~ log
N
.
The growing interest in complex systems prompted many scientists to ask a
simple question: are real networks behind diverse complex systems, like the cell,
fundamentally random?
3.2. Scale-free Networks
A highly nontrivial development in our understanding of complex networks
was the discovery that for most large networks, including the metabolic and pro-
tein interaction networks (24,26), the degree distribution follows a power-law:
P
(
k
) ~
k
-
H
.
[4]
These networks are called scale-free, as a power law does not support the exis-
tence of a characteristic scale. Two mechanisms, absent from the classical ran-
dom network model, are responsible for the emergence of this power-law degree
distribution (5,6). First, most networks grow through the addition of new nodes,
which link to nodes already present in the system. Second, in most real networks
there is a higher probability to link to a node with a large number of connections,
a property called preferential attachment. The scale-free model introduced by
Barabási and Albert (the BA model; second columns in Figures 3 and 4) incor-
porates these features (5). Starting from a small graph, at each time step a
