N news
Science | DOI: 10.1145/1378727.1378732
Kirk L. Kroeker
finding Diamonds
in the Rough
Spectral graph theory has proven to be very useful for text search
and retrieval and for refining predictive-analysis systems.
IN TERNE T BGP-AS ROUTING GRAPH REPRESENTATION COUR TESY OF ROSS M. RICHARDSON, DEP T. OF MATHEMATICS, UNIVERSIT Y OF CALIFORNIA, SAN DIEGO.
THERE IS A little-known approach to information analysis
that has built the foundation
for many of the information
technologies that we now consider to be givens of the 21st century.
The strategy, called spectral graph theory, is well known among mathematicians and those working with massive
data sets, but has not received a great
deal of credit in the mainstream media
as being an important method for understanding key relationships in data
sets consisting of millions or even billions of nodes. With roots in the early
20th century, spectral graph theory
and the corresponding interpretative
method of spectral analysis were initially used as a theoretical approach to
solving specialized math problems in
which relationships between certain
classes would otherwise be difficult
to ascertain.
The origin of spectral graph theory
can be traced to Markov chains, harmonic analysis, statistics, and spectral
geometry, with mathematicians asking
Zen-like questions such as “How can
you hear the shape of a drum?” In the
intervening years, spectral graph theory
was applied in several areas, with IBM
researcher Alan J. Hoffman even using
the technique in the 1970s to partition
circuitry on silicon chips. In the 1980s,
Microsoft’s Susan Dumais, the University of Colorado’s Tom Landauer, and
their colleagues used spectral analysis
to cluster documents in a technique
called latent semantic analysis. However, it wasn’t until the 1990s that spectral graph theory became one of the
most important tools in understanding
how to conduct text search and retrieval
more efficiently.
Spectral graph theory, which might
be characterized as a kind of advanced
Boolean logic on steroids (in the sense
that it can help simplify extremely complex relationships among class members that are also members of other
classes), has become useful not only to
those working in Web search, but also
to those refining predictive-analysis systems of the type used to determine what
books you might find most interesting
or what movies you might like to watch.
In her early work with spectral analysis, Fan Chung, an Akamai professor in
Internet mathematics at the University
of California, San Diego, applied the
theory to light patterns to help determine the molecular composition of
stars. Chung is now taking spectral
analysis in new directions for Web
search, such as how to analyze and improve Google’s PageRank, which was introduced in 1998 and based on a math
strategy called random walks. “One of
the main applications of spectral graph
