Exceptional Creativity

Cornell Professor Jon Kleinberg receives MacArthur "Genius Award"

The John D. and Catherine T. MacArthur Foundation last fall named Jon Kleinberg, Cornell professor of computer science, among the 25 new MacArthur Fellows—the so-called "Genius Awards"—for 2005. He will receive $500,000 in no-strings-attached support over the next five years.

Kleinberg, who received his bachelor’s degree from Cornell in 1993 and became a faculty member just three years later, is a computer scientist with a reputation for tackling important, practical problems and in the process deriving deep mathematical insights. He is best known for his contributions to network theory, particularly in expanding the "small worlds" concept and in developing improved methods for searching the World Wide Web. But his research also covers Internet routing, data mining, comparative genomics and protein structure, and the sociology of the web.

"I was completely surprised when I heard about this," Kleinberg said. "Then I thought back on all the people who have won this and felt humbled."

The MacArthur Fellowships are awarded based on "exceptional creativity, promise for important future advances based on a track record of significant accomplishment, and potential for the fellowship to facilitate subsequent creative work." The foundation does not require any reports or evaluation from the recipients. "It’s a chance to do things that would be hard to do otherwise," Kleinberg said. "It gives you a level of freedom and flexibility that would be hard to get any other way."

It has become widely understood that any two people are linked by a relatively small number of connections among mutual acquaintances—or "six degrees of separation." The same mathematical principles apply to computer or other networks as well as networks of people. Kleinberg extended this concept by introducing the notion of navigability—how well the information structure of the network allows individuals to make distant connections efficiently. He was able to prove that in networks with random connections, a computer algorithm with only local information has no way to find the shortest path to a distant point. This demonstration has important implications in sociology and in distributed network architecture design and in applications, such as peer-to-peer file sharing.

In addition, Kleinberg has developed an algorithm—a method on which computer programs can be based—for identifying the structure of web site interactions. His algorithm distinguishes "authority" sites, which contain definitive information, from "hub" sites, which refer to authority sites using hyperlinks. The algorithm is used in several contemporary web search engines, where sites that are most linked to by the most important hubs are listed higher in search results. Beyond that, the algorithm makes it possible to identify communities of interest on the web without explicit effort needed by members and even without an awareness of the existence of the community, simply by examining links between sites.

Recently he has applied these ideas to sociology and is a member of a group of computer scientists and sociologists collaborating to study the sociology of the web. "It’s great to be working with sociologists, because they bring such different perspectives and they’re so good at posing interesting questions," he noted.