Information Technology Reference
In-Depth Information
consensus? It is evident that all-to-all coupling is not realistic when applied to the entire
web; it is too slow and consumes too many resources. It is more plausible if the coupling
concerns small clusters, and when these are truncated at a given distance
T
trunc
.
Is it
possible to establish a condition that the best web topology is that which produces the
largest value of the truncation distance? It is plausible that the best web topology that fits
this condition does not coincide with the “best” topologies devised by other methods [
5
].
Finally, note that one of the most important properties of complex networks is the size
of the web; that is, the number of jumps from one node to any other node of the web is
surprisingly small. It is evident that, if there are all-to-all coupling clusters, the length
l
of a cluster is
l
1; that is, any node in the web can be reached from any other node
in a single step. If the clusters are suitably connected by long-distance links, we can
produce webs of relatively small access size, that is, of length
l
=
However, it is
important to take into account that not all the links have the same importance, which is
a fact of significance in sociological networks [
19
]. In this chapter we adopt for most of
the discussion the simple assumption of uniform links; that is, each link has the same
dynamical behavior and exerts the same influence on all the other links. This is not a
realistic assumption and we eventually move beyond it to a more realistic supposition
in the next chapter.
≈
6
.
6.1
Web growth
The understanding of scale-free inverse power-law webs by physicists began with small-
world theory, a theory of social interactions in which social ties can be separated into
two primary kinds: strong and weak. Strong ties exist within a family and among the
closest of friends, those you call in case of emergency and contact to tell about a pro-
motion. These are the people who make up most of our lives. Then there are the weak
ties, such as those we have with many of our colleagues at work with whom we chat,
but never reveal anything of substance, friends of friends, business acquaintances and
most of our teachers.
Figure
6.1
depicts schematically a random web and a scale-free web. It is evident
that scale-free webs are characterized by clusters and that each cluster contains at least
one hub, that being a node interacting with all, or nearly all, the other nodes of the
same cluster. The power-law distribution strongly influences the web topology. It turns
out that the major hubs are closely followed by smaller ones. These nodes, in turn,
are followed by other nodes with even smaller degrees and so on. This hierarchy of
connectedness allows fault-tolerant behavior. Since failures typically occur at random
and the vast majority of nodes will be those with small degree, the likelihood that a
hub would be affected by a random failure is almost negligible. Even if such events
as the failure of a single hub occur, the web will not lose its connectedness, which is
guaranteed by the remaining hubs. On the other hand, if we choose a few major hubs
and take them out of the web, the network simply falls apart and the interconnected web
is turned into a set of rather isolated graphs. Thus, hubs are the strength of scale-free
networks as well as being their Achilles' heel.
