Michael J. Okoniewski

Jon Kleinberg

The John D. and Catherine T. MacArthur Foundation today (Sept. 20) 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.

"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." Among previous recipients, he pointed out, are Paul Ginsparg, Cornell professor of physics and creator of the online ArXiv of physics research, and Kleinberg's Cornell classmate Sendhil Mullainathan '93, now a professor of economics at Harvard.

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.

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." Recipients include writers, scientists, artists, social scientists, humanists, teachers and entrepreneurs. The foundation does not require any reports or evaluation from the recipients. The grant is paid in quarterly installments over five years. "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." He added that he is still considering how to use the grant.

Since the original demonstration of the phenomenon four decades ago by Stanley Milgram, 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 both 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.

His work is useful to biologists as well. Four years ago, Kleinberg worked with Cornell researchers to compare the genomes of related plant species. The researchers sought to locate important genes that were identified in one species but not in another. This gives researchers clues to how both species evolved from a common ancestor. Making "comparative gene maps" had been a slow, painstaking process that in the past had been done by hand, taking months or years. With algorithms developed by Kleinberg and his collaborators, comparative genomes of maize and rice were made in minutes. The program also found evidence of an ancestral chromosome in maize that did not turn up in the handmade maps.

His textbook, "Algorithm Design" (Addison-Wesley, 2005), written with Cornell Professor Eva Tardos, introduces students to algorithms by looking at the real-world problems. In a clear style, the book shows how to analyze and define problems and to recognize design principles that are appropriate for a given situation.

Kleinberg received his S.M. degree (1994) and Ph.D. (1996) from the Massachusetts Institute of Technology. He has held research positions at IBM in the Theory and Computation Group (1995), the Computer Science Principles and Methodologies Group (1996-97) and, since 1998, continues to be a member of the Visiting Faculty Program at the IBM Almaden Research Center.