AEROSPACE

The John D. and Catherine T. MacArthur Foundation 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, a Cornell faculty member since 1996, 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." Among previous recipients, he pointed out, are Paul Ginsparg, Cornell professor of physics and creator of the online ArXiv of physics research, and his Cornell classmate Sendhil Mullainathan '93, now a professor of economics at Harvard. 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, entrepreneurs and others. 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 at this point he has no idea how he will 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're so good at posing 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 Kleinberg's algorithms, comparative genomes of maize and rice were made in hours. The program also found evidence of an ancestral chromosome in maize that did not turn up in the handmade maps. Kleinberg's recently published textbook, "Algorithm Design" (Addison-Wesley, 2005), 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.