Mapping Associations - Mapping Scientific Frontiers: The Quest for Knowledge Visualization - page 135

that represents movie stars as vertices and edges connecting them if they ever
starred in a movie together. A version of the Hollywood graph in 2001 represents
355,848 actors and actresses from 170,479 movies. In this graph, the focus is on
the centrality of Hollywood actor Kevin Bacon in the film industry. This Hollywood
graph has gained widespread publicity, partly because researchers have found a way
to replicate some key characteristics of this graph (Watts and Strogatz 1998 ). Brett
Tjaden and Glenn Wasson of the University of Virginia maintain TheOracleof
Bacon on the Web that calculates Bacon numbers.
Small-world networks are defined by three properties: sparseness, clustering, and
small diameter (Watts 1999 ). Sparseness means that the graph has relatively few
edges. Clustering means that edges are not uniformly distributed among vertices;
instead there tend to be clumps in the graph. Small diameter means that the longest
shortest path across the graph is small.
In 1998, Duncan Watts and Steven Strogatz of Cornell University found these
properties in the Hollywood graph and several other huge graphs have (Watts and
Strogatz 1998 ). Watts and Strogatz used a rewiring strategy to produce a graph
somewhere between a random graph and a regular graph. The rewiring process
started with a regular lattice and then rewired some of the edges according to a
probability p , ranging from 0 to 1. If p is equal to 0, then everything remains
unchanged. If p is equal to 1, then every edge is re-arranged randomly and the lattice
becomes a random graph. They calculated the minimum path length L averaged
over all pairs of vertices and found that L dropped dramatically when just a few of
the edges were rewired. Watts and Strogatz also measured the degree of clustering
in their hybrid graphs using a clustering coefficient C . They found the clustering
coefficient C remained high until the rewiring probability was rather large. The
Hollywood graph demonstrated a good match to their model.

3.5.4 Semantic Networks

Semantic networks are useful tools as representations for semantic knowledge and
inference systems. Historically, semantic networks refer to the classic network the-
ory of Collins and Quillian ( 1969 ) in which concepts are represented as hierarchies
of interconnected nodes with nodes linked to certain attributes. It is important to
understand the organization of large-scale semantic networks. By applying graph-
theoretic analyses, the large-scale structure of semantic networks can be specified
by distributions over a few variables, such as the length of the shortest path between
two words and the number of connections per word. Researchers have shown that
the large-scale organization of semantic networks reveals a small-world structure
that is very similar to the structure of several other real-life networks such as the
neural network of the worm C. elegans, the collaboration network of film actors
and the WWW. We have seen examples of Erdos numbers and Bacon numbers. We
return to C. elegans in later chapters for an example of gene expression visualization
of C. elegans.