Database Reference
In-Depth Information
the discovery that despite the intrinsic distinctions in the nature and functional-
ity of the nodes and their interactions, many real-world networks follow highly
reproducible patterns. There are three most studied properties that characterize
a real network:
Average path length
measures the average steps it takes for one node to reach
another node in the network, also commonly referred as diameter of a network.
Although real networks often consist of a large number of nodes, they have a
very small diameter, which is most known as the “small world” property or “six
degrees of separation.” That is, individuals on the planet are separated by six
degrees of social contacts. Despite its simplicity, the random graph model well
captures this property, predicting the average path length
d
∼
ln
N
, where N is
the size of the network.
Clustering
represents densely connected cliques in a network, and was for-
mally quantified by Watts and Strogatz (1998). They introduced clustering coef-
ficient
C
i
for node
i
, which measures the fraction of neighbors of
i
are also
connected to each other. In the random graph model, as links are distributed
randomly among the nodes, it predicts
C
i
=
p
. Yet in almost all real networks,
the clustering coefficients are significantly higher than the random graph model
prediction. To capture the pervasive clustering phenomena, Watts and Strogatz
introduced the small-world model, also known as the WS model: start from
a regular network, for instance a ring, in which each node is connected to its
k
nearest neighbors. Let us redirect links with probability
p
, moving one end
of an edge to a new location chosen uniformly at random from the lattice.
When
p
0, the network is a regular lattice, thus characterized by a very high
clustering coefficient but a large average path length. On the other end, when
p
=
1, the network is equivalent to a random graph. As we start to increase
p
from 0 to 1, the diameter of the network quickly shrinks, while the cluttering
coefficients remain roughly the same. Therefore, for a wide range of
p
,theWS
model gives rise to networks with both high clustering coefficients and small
diameter.
Degree distribution
,
P
(
k
), measures the probability that a randomly selected
node has
k
edges. The random graph model predicts
P
(
k
) follows a Poisson
distribution corresponding to a homogeneous network, where every node has
roughly the same degree around
k
. However, a variety of real networks, span-
ning from the Internet and WWW to scientific citations and actor collaborations,
exhibit the “scale-free” property, a highly reproducible pattern not accounted for
by either random graph model or WS model. That is,
P
(
k
) follows a power law
P
(
k
)
∼
k
−
γ
. This result indicates that real networks are rather heterogeneous:
most nodes in the network have very low degree, although there are a notable
number of nodes with a large number of connections. Think about Yahoo! for the
Web, ATP protein for metabolic networks, and Heathrow for air traffic network.
To explain the possible origin of the observed scale-free property, Barabasi and
=
