Information Technology Reference
In-Depth Information
Our average number of acquaintances is very much less than the size of the global
population. So the claim that any people in the world are just six degrees apart does
seem mysterious.
Stanley Milgram conducted a study in 1967 to test the small-world phenomenon
(Milgram
1967
). He asked volunteers in Nebraska and Kansas to deliver packets
addressed to a person in Boston through people they know and who might get
it closer to its intended recipient. Milgram kept track of the letters and the
demographic characteristics of their handlers. He found a median chain length of
about 6, 5.5 to be precise. However, two-thirds of the packets were never delivered
at all, and that the reported path length of 5.5 nodes was an average, not a maximum.
Over the past few years, there has been a surge of revived interest in this topic
among mathematicians, statisticians, physics, and psychologists (Watts
1999
; Watts
and Strogatz
1998
). Brian Hayes wrote two-part features in
American Scientist
to
introduce some of the latest studies of far-reaching implications of the small-world
phenomenon (Hayes
2000a
,
b
).
3.5.2
The Erdos-Renyi Theory
Random graphs are among the most intensively studied graphs. The Hungarian
mathematician Paul Erd os (1913-1996) and his colleague Alfred Renyi found that a
random graph has an important property: that is, when the number of edges exceeds
half the number of vertices, a “
giant component
” merges suddenly so that most of
the vertices become connected by the single piece. This is known as the Erd os-Renyi
theory.
Given that many huge graphs in the real world are not random graphs, it is
particularly interesting if there are such giant components in these graphs. For
example, a giant component in a citation network would indicate some mainstream
literature of a particular discipline. A giant component in the cyber-graph of the
World-Wide Web would identify the core users of the Web and the core customers
of e-commerce. James Abello of the AT&T Shannon Laboratories in New Jersey
studied the evolution of call graphs, in which the vertices are telephone numbers,
and the edges are calls made from one number to another (Abello et al.
1999
).
Within 20 days, the graph grew to a gigantic network of 290 million vertices and 4
billion edges. This is simply too big to analyze with current computing resources.
Abello and his colleagues analyzed a one-day call graph, containing 53,767,087
vertices and 170 million edges. Among 3.7 million components, most of them
tiny, they found one giant connected component that connects 44,989,297 vertices
together, which is more than 80 % of the total number of vertices. The gigantic
component has a diameter of 20, which implies that any telephone number in the
component can be linked to any other through a chain of no more than 20 calls. The
emergence of a giant component is characteristic of Erd os-Renyi random graphs,
but the pattern of connections in the call graph is certainly not random.
Search WWH ::
Custom Search