Jon Kleinberg's Web-Search Ideas Make the Headlines

Search for "ice cream" using a search engine on the World Wide Web and you'll get almost 200,000 hits! How do you determine which of those hits will be most useful to you? We've all been bewildered with such problems. Assistant Professor Jon Kleinberg and colleagues at IBM Almaden have come up with some interesting ideas on determining the "authoritative" hits out of those 200,000. His ideas have been so intriguing that they are being discussed in places like The Economist (7/20/98), Scientific American (7/98), and Science News (5/2/98). Links on the World Wide Web contain a considerable amount of latent human annotation. For example, pages usually have links to other pages, and one simple idea would be to order hits based on the number of links to them. Jon shows in a paper that this naive approach just doesn't work well enough.

Instead, he and his colleagues developed more sophisticated methods. A link from one page to another indicates in some sense a "conferral of authority", and one would expect a lot of overlap in the links to the most "authoritative" pages. His algorithm, based on graph theory and computational linear algebra, uses such notions as dense bipartite communities in the link graph of the Web and the interpretation of the eigenvectors of matrices involved in this graph. The work shows nicely how theory can pay off in practice!

Experiments with Kleinberg's program also resulted in some promising observations about the growth of the World Wide Web. Generally speaking, the process by which Web users create pages and links is very difficult to understand at a "local" level. However, when viewed in terms of "authoritative" pages, one sees a much greater degree of orderly high-level structure than has typically been assumed.

For more information, see Jon's Web site http://www.cs.cornell.edu/home/kleinber

Oh, by the way, according to Jon's algorithm, the top five authoritative "ice cream" pages on the Web are given below, in order. Sure enough, Ben and Jerry's is there. The fifth page appears to be a general information page on ice cream at the University of Guelph.

http://www.edys.com/
http://www.benjerry.com/
http://www.dreyers.com/
http://www.baskinrobbins.com/
http://www.foodsci.uoguelph.ca/dairyedu /icecream.html