Shrinking Degrees of Separation

October 24, 2005 (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? "What's been the reaction to the release of Mac OS X Tiger? Have people been happy with it or not happy, and how is Apple responding?" You can hunt around until you find a page where some human has answered that, but there's no way to get a search engine to answer it.

What else is in the future of search? These tools weren't designed to track events unfolding hour by hour. When we use the Web to keep up with breaking news, we don't use search engines; we go to a few news Web sites. But it doesn't have to be that way. You are starting to see, especially in the blogging domain, people trying to create tools that have some of that capability.

Where will these kinds of advancements come from? There's a lot of feedback between university research and companies like Google, Yahoo and Microsoft. The companies are running high-volume services that are extremely innovative, but it's very hard for them to pursue all those interesting leads and possible dead ends. In universities, you may have the freedom to pursue slightly zany ideas that might not pan out.

Are there any lessons in your research for information systems developers? If you're going to think of new online media or new ways of communicating online -- not just IMing, but Internet telephony and Skype and all those things -- then you're going to have to think about social networks and how people use them. In the end, these tools are to connect people to each other and to information, and the way people succeed or fail at that is influenced by the nature of the tools.

Any other advice for IT people? Political discourse seems to be getting more polarized. Something we don't understand is to what extent that's an effect of the media we're using. Is there something about blogging and online discussion that causes polarization in some subtle way? It's an important challenge for people on the computer side, because it's within our power to create tools that shape discourse. For us to be able to help make civil dialogues more productive would be an amazing and wonderful thing.