Information Technology Reference
In-Depth Information
A clique is a fully connected graph, also known as a complete graph, in which
every vertex is linked to every other vertex directly. Abello et al. found more than
14,000 cliques of 30 vertices in their call graph. Each clique represented a distinct
group of 30 individuals in which everyone talked with everyone else at least once
on the phone during that day. Within such cliques, the degree of separation is one.
The Web is by far the largest real-world graph. More and more researchers are
turning their attention to the structure and evolution of the Web. Physicist Albert-
Laszlo Barabasi and his colleagues at University of Notre Dame in Indiana, USA,
studied the topology of the Web and found an amazing feature that web pages had
19 degrees of separation (Albert et al.
1999
; Barabasi et al.
2000
). They counted
hyperlinks between 260,000 unique sites on the Web and found that the distribution
of links followed a power law (Barabasi et al.
2000
). The power law implies that web
pages with just a few links are most common, but pages with hundreds of links may
still exist even though they are rare. The age of a site did not seem to have much
to do with its number of links; all sites were not created equal. In fact, the more
links a web page has, the more new links it will attract. The rich get richer. Here
we go again. Furthermore, web pages with a large number of links are important
in forming a gigantic component of the Web and reducing the degree of separation
between web pages. Two special kinds of link-rich web pages were studied by Jon
Kleinberg of Cornell University, Prabhakar Raghavan and Sridhar Rajagopalan of
the IBM Almaden Research Center:
hubs
and
authorities
(Kleinberg
1998
). Hubs
have a large number of outgoing links. Authorities have many incoming links.
3.5.3
Erdos Numbers
Paul Erd os (1913-1996) was a productive Hungarian mathematician. Figure
3.24
is
a photograph of Erd os. He has been regarded as the most brilliant mind in graph
theory. He published over one thousands of articles. When he died of a heart attack
in 1996, New York Times wrote:
Concentrating fully on mathematics, he traveled from meeting to meeting, carrying a half-
empty suitcase and staying with mathematicians wherever he went. His colleagues took
care of him, lending him money, feeding him, buying him clothes and even doing his taxes.
In return, he showered them with ideas and challenges - with problems to be solved and
brilliant ways of attacking them.
The Erd os number of a mathematician is in fact defined as the degree of
separation between Erd os and the mathematician in a collaboration graph. If a
mathematician has published a joint article with Erd os, then his or her Erd os number
is one. The Erd os number of someone who did not write with Erdos directly, but
wrote with someone with an Erd os number of one, would be two, and so on. It was
thought that this collaboration graph should have a well-connected component with
Erd os at the center and linking to almost all active scientists.
While mathematicians have their Erd os numbers, Hollywood actors and actresses
can have their Bacon numbers. The “Hollywood graph” is a collaboration graph
Search WWH ::
Custom Search