Jon Kleinberg was so incredulous when a representative from MacArthur Foundation called him on Tuesday with the news that he had been named one of 25 recipients of the distinguished MacArthur Fellowship, that he Googled the number on his phones caller ID screen to make sure the call was for real.
Kleinbergs decision to use Google to figure out whether or not he was the victim of a hoax was appropriate enough—Kleinbergs work as a computer scientist and mathematician helped lay the theoretical foundation for technologies like Google. In coming years, his ideas may well revolutionize our understanding of how human beings interact and transform the way we learn.
The 33-year-old professor of computer science at Cornell University works at the edges of a handful of disciplines that dont often bump into one another: computer science, sociology, philosophy, mathematics and comparative genomics. His genius, say those who have worked with him, isnt just the ability to develop novel and elegant mathematical formulas but to derive those ideas from insights into the way people interact that one prominent researcher called "dazzling."
David Liben-Nowell, an assistant professor of computer science at Carleton College and a protégé of Kleinberg, said he couldnt have been less surprised at hearing of Kleinbergs selection.
"I was wondering when this would catch up with him. I dont think I could imagine a person more appropriate (for the MacArthur Fellowship)," he said.
Though his name is less well known than Google founders Sergey Brinn and Larry Page, Kleinberg worked and published groundbreaking research in the area of Web link analysis in the late 1990s similar to the "page rank" method for finding Web pages that Page and Brinn developed at Stanford University and turned into the Google search engine in 1998, according to Prabhakar Raghavan. Raghavan worked with Kleinberg at IBMs Almaden Research Center, in San Jose, Calif., at the time and is now head of research at Yahoo Inc.
The idea of building a better search engine was on the minds of a number of researchers at IBM at the time.
"AltaVista (search engine) had just taken off, and there were a number of us who had a vague sentiment that (Web search) was important and needed to be done better," he said.
Like Brinn and Page at nearby Stanford, Kleinberg and his colleagues realized that looking at the structure of links on the Web between sites that contained useful data and the sites that linked to them was useful for those who needed to find information online.
But Kleinberg took a different approach than Brinn and Page did to the problem, developing an algorithm called HITS, for Hyperlink-Induced Topic Search, that groups the Web into a series of information "authority" sites and "hub" sites that link to them.
"[HITS] unfolded in front of our eyes," Raghavan said. "Jon would come to me and say Heres what I figured out today. And each day you would see these beautiful insights," Raghavan said.
Kleinbergs work on what he terms "Small-World Phenomena" and "Decentralized Search" is another example of his ability to match social insight with "hard hitting math," he said.
For that research, Kleinberg started with Yale psychologist Stanley Milgrams groundbreaking 1967 small world experiment, in which residents in Wichita, Kan., were asked to forward a letter, by hand, to an individual in Cambridge, Mass. The study gave rise to the popular notion that just "six degrees of separation" connect every human on the planet.
Kleinbergs analysis revealed that Milgrams contemporaries, and generations of scientists after him, overlooked one of the experiments most interesting findings: that individuals with no knowledge about a complex network could still make efficient distant connections, or "long links," just using local information about their immediate neighbors.
Studying phenomena such as small world networks, social networking and viral marketing could shake up the Internet again, supplanting the current orthodoxy of link-based search engines, Kleinberg said.
"Google was a fresh take on how to find Web pages, but Google and Yahoo all use link analysis now, so were back to a network where you get one take of what is important," he said.
Users should be able to have multiple ways to get at information, including tools that take account of factors such as the passage of time or the importance of social influence, he said.
With better technology, Web sites like Amazon.com could make book recommendations based on potent factors such as the shopping behaviors of an individuals acquaintances, or those whose opinions the shopper trusts—factors that arent considered now, Raghavan said.
"If information is growing exponentially, but our ability to consume it is constant, then our algorithms have to get exponentially better by making use of queues like acquaintance and trust that are all around us and waiting to be tapped," he said.
While Kleinberg hasnt decided yet how he will use the "no strings attached" $500,000 MacArthur Fellowship, he said the money will give him the flexibility to do research that stretches across disciplines such as the social and computer sciences.
"The funding gives you the flexibility to navigate these areas very well," he said.