Information Technology Reference
In-Depth Information
Clusters form among those individuals with strong interactions, forming closely knit
groups, clusters in which everyone knows everyone else. These clusters are formed
from strong ties, but then the cliques are coupled to one another through weak social
contacts. The weak ties provide contact from within a cluster to the outside world. It
is the weak ties that are all-important for interacting with the world at large, say for
getting a new job. A now classic paper by Granovetter, “The strength of weak ties”
[
19
], explains how it is that the weak ties to near strangers are much more important in
getting a new job than are the stronger ties to one's family and friends. In this “small
world” there are short cuts that allow connections from one tightly clustered group
to another tightly clustered group very far away. With relatively few of these long-
range random connections it is possible to link any two randomly chosen individuals
with a relatively short path. This has become known as the
six-degrees-of-separation
phenomenon
[
34
]. Consequently, there are two basic elements necessary for the small-
world model, clustering and random long-range connections.
6.1.1
Scale-free webs
Small-world theory is the precursor to scale-free networks. Recent research into the
study of how networks are formed and grow over time reveals that even the smallest
preference introduced into the selection process has remarkable effects on the final
structure of the web. Here the selection procedure is the process by which a node
entering the web chooses to connect with another node. Two mechanisms seem to be
sufficient to obtain many of the inverse power-law distributions that are observed in
the world. One of the mechanisms abandons the notion of independence between suc-
cessive choices within a network. In fact, the mechanism is known in sociology as the
Matthew effect, and was taken from the Book of Matthew in the Bible:
For unto every one that hath shall be given, and he shall have abundance: but from him that hath
not shall be taken away even that which he hath.
Or, in more familiar terms, this is the principle that the rich get richer and the poor
get poorer. In a computer-network context this principle implies that the node with the
greater number of connections attracts new links more strongly than do nodes with
fewer connections, thereby providing a mechanism by which a web can grow as new
nodes are added. It is worth pointing out that this mechanism is not new and was identi-
fied as the
Gibrat principle
in 1935 by Simon [
30
] and as
cumulative advantage
in 1976
by Price [
28
] as well as being called the
Matthew effect
by Merton [
23
] in 1968 and,
most recently,
preferential attachment
by Barabási and Albert [
6
] in 1999.
The thread of the argument presented by Barabási and Albert [
6
] to incorporate the
growth of a network and the dependence of the links made by the new nodes to the
previously existing nodes goes as follows. At time
t
=
0 there are
m
0
nodes with no
links to connect them. At later times
t
1
,
new vertices are established and with
each new vertex another
m
new edges are formed. We assume
m
t
2
,...
m
0
so that each new
node can accommodate all its edges with the nodes already belonging to the network.
The choice of the first
m
elements from the preexisting
m
0
elements to connect to the
≤
