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
References:
Archives