“Studying information on the World Wide Web is a nice problem for computer scientists because it unifies many parts of the field,” says Computer Science Professor Jon Kleinberg. “You need graph theory for the properties of objects that can be linked; artificial intelligence, data mining, and machine learning to systematically identify important patterns; systems and databases to manage the massive quantities of information; and natural language processing because web pages are written in human languages.”

Internet search engines rely largely on network theory. To try to evaluate the content of billions of web documents put out there by disparate authors is impossible. But link analysis makes it possible to examine relationships among web pages (vertices in classical graph theory). Important pages are found at the centers of web-page communities, less important pages reside at the margin.

“Keep in mind that ‘industrial-strength’ search engines, like Google, combine several search methods,” says Kleinberg, an early practitioner of link analysis on the web at IBM. “They don’t merely count links and assign a rank. They use page-rank formulas along with information retrieval methods and algorithmy.”

Professor John Hopcroft eagerly anticipates the next generation of search engines. A project designed by some of his students worked with Citeseer, an on-line collection of articles in computer science, and sorted them by subject without being told in advance the subjects to look for.

“We would like to design discerning search engines that follow criteria for selection, that make judgments, and can make recommendations,” Hopcroft says. “The question is: what are the mathematics to find relevant information, as opposed to most-widely-sought information?”

Eva Tardos, professor and chair of the Department of Computer Science, investigates the implications of the web’s de-centralization. “Network flow algorithms don’t work here because planners lack the information and the power to make decisions,” Tardos says. Billions of individuals at personal computers engage the web in ways that reflect their own self-interest. In classical graph theory they would be called nodes; here, they operate on their own with a remarkable lack of central coordination. And the implications of this will be interesting to observe, she says.