Shrinking Degrees of Separation

Computerworld -

Jon Kleinberg, a professor of computer science at Cornell University

"Jon Kleinberg is a computer scientist with a reputation for tackling important, practical problems and, in the process, deriving deep mathematical insights," says the Web site of the John D. and Catherine T. MacArthur Foundation. Kleinberg, a professor of computer science at Cornell University, was a recent winner of a MacArthur Fellowship, often referred to as a "genius" grant.
Kleinberg's research covers a diverse range of topics, including computer and social networking, network routing and search, genomics and protein structure analysis. He has found surprising similarities in the underpinnings of these disciplines.
For example, he discovered how to build networks so that one node can connect to a faraway node efficiently and without knowledge of the overall network topology. The idea builds on the concept of "six degrees of separation," which holds that any two people can find connections to each other via shared relationships with others. Kleinberg's discoveries have influenced the design of decentralized peer-to-peer file-sharing services such as Freenet and social networks such as LiveJournal.com.

Kleinberg's research aims to transform Internet search. Above is a map of the Internet, with major connections color-coded by IP address. Image Credit: Lumeta Corp., Somerset, N.J.

When he worked at IBM, Kleinberg showed how search engines can be improved by considering not only a site's content, but also the number and quality of links to it. He developed the concept of "authorities" (a PC's manufacturer, for example) and connecting "hubs" (reviews of that PC), and he figured out how to recursively find the best hubs and authorities for a given search. His algorithms can also be used to define and explain social groups and their connections. In a recent interview, he told Computerworld where some of those ideas could lead.

Are the major public search engines today using your network search principles? Yes, but exactly what they do is a closely guarded secret. They all have very extensively tuned methods that combine link information with content information. The search engine that most directly incorporates hubs and authorities is Teoma, used by Ask Jeeves.

Is search a mature technology? It's still in its early stages. The more that's done, the more it becomes clear it's a very hard problem. What you'd like a search engine to do is simulate the experience of talking with someone very knowledgeable about a topic. Instead, you type a few words into a box, and it gives you some links. What's impressive is how far you can get with that.


What's an example of a question you'd like to ask the search engine of the future?