significant recent discoveries are the small-world effect
and the scale-free feature of most complex networks.
In 1998, in order to describe the transition from a regu-
lar lattice to a random graph, Watts and Strogatz (WS)
introduced the concept of small-world network [5]. It is
notable that the small-world phenomenon is indeed very
common. An interesting experience is that, oftentimes,
soon after meeting a stranger, one is surprised to find that
they have a common friend in between; so they both cheer:
“What a small world!” An even more interesting popular
manifestation of the “small-world effect” is the so-called
“six degrees of separation” principle, suggested by a social
psychologist, Milgram, in the late 1960s [6]. Although this
point remains controversial, the small-world pattern has
been shown to be ubiquitous in many real networks. A
prominent common feature of the ER random graph and
the WS small-world model is that the connectivity distri-
bution of a network peaks at an average value and decays
exponentially. Such networks are called “exponential net-
works” or “homogeneous networks,” because each node
has about the same number of link connections.
Another significant recent discovery in the field of com-
plex networks is the observation that many large-scale
complex networks are scale-free, that is, their connectivity
distributions are in a power-law form that is independent
of the network scale [7, 8]. Differing from an exponential
network, a scale-free network is inhomogeneous in nature:
most nodes have very few link connections and yet a few
nodes have many connections.
The discovery of the small-world effect and scale-free
feature of complex networks has led to dramatic
advances in the field of complex networks theory in the
past few years. The main purpose of this article is to pro-
vide some introduction and insights into this emerging
new discipline of complex networks, with emphasis on
the relationship between the topology and dynamical
behaviors of such complex networks.
Some Basic Concepts
Although many quantities and measures of complex net-
works have been proposed and investigated in the last
decades, three spectacular concepts—the average path
length, clustering coefficient, and degree distribution—
play a key role in the recent study and development of
complex networks theory. In fact, the original attempt of
Watts and Strogatz in their work on small-world networks
[5] was to construct a network model with small average
path length as a random graph and relatively large clus-
tering coefficient as a regular lattice, which evolved to
become a new network model as it stands today. On the
other hand, the discovery of scale-free networks was
based on the observation that the degree distributions of
many real networks have a power-law form, albeit power-
law distributions have been investigated for a long time in
physics for many other systems and processes. This sec-
tion provides a brief review of these important concepts.
Average Path Length
In a network, the distance
d
ij
between two nodes, labeled
i
and
j
respectively, is defined as the number of edges
8
IEEE CIRCUITS AND SYSTEMS MAGAZINE FIRST QUARTER 2003
Figure 2. [Courtesy of SCIENCE] A simple “complexity pyra-
mid” composed of various molecular components of cell-
genes, RNAs, proteins, and metabolites [47]. The bottom
of the pyramid shows the traditional representation of
the cell’s functional organization (level 1). There is a
remarkable integration of various layers at both the
regulatory and the structural levels. Insights into
the logic of cellular organization can be gained
when one views the cell as an individual com-
plex network in which the components are
connected by functional links. At the low-
est level, these components form genet-
ic-regulatory motifs or metabolic path-
ways (level 2), which in turn are the
building blocks of functional mod-
ules (level 3). Finally, these mod-
ules are nested, generating a
scale-free hierarchical archi-
tecture (level 4).