Finding Diamonds in the Rough

By Kirk L. Kroeker

Spectral graph theory has proven to be very useful for text search and retrieval and for refining predictive-analysis systems.

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.

(This article appeared in CACM, vol. 51, no. 9, Sept. 2008, pp. 11-13.)

(download the PDF)