Communications - July 2009

Milestones | DOI: 10.1145/1538788.1538798
Alan Joch
Master of Connections

Jon Kleinberg is honored for his pioneering research on the Web and social networking.

Jon Kleinberg

In 1981, 10-year-old realized he could use his Apple II computer not just to play existing games but to invent his own. “I had a sense that you

could actually create things with this device, and that presented computing in a very engaging way for me,” recalls Kleinberg, now the Tisch professor of computer science at Cornell University.

That epiphany kindled in Kleinberg a passion that led him to become a rising star in computer science. The latest kudo: In April, Kleinberg won the ACM-Infosys Foundation Award in the Computing Sciences for his pioneering work in Web search techniques and large social networks. Kleinberg has previously received fellowships from the MacArthur, Packard, and Sloan foundations, and last year earned a spot on Discover magazine’s list of “best brains under 40.”

The Web link-analysis models Kleinberg created while a visiting scientist at IBM Almaden Research Center in 1996 contributed to the success of search-engine algorithms that help people navigate the volume and diversity of information on the Web, which had just exploded onto the scene a few years before. He has also used the Web’s reach to explore the “six degrees of separation” phenomenon, which describes how closely connected individuals are throughout the world.

PhO TOGRAPh BY CORNELL UNIVERSIT Y PhOTOGRAPh Y / ROBERT BARkER

“There are problem posers, problem solvers, and problem kibitzers,” says Tom Leighton, a professor of applied mathematics at Massachusetts Institute of Technology, where Kleinberg completed his graduate studies. “Jon is very good at all of the pieces. He’s the kind of guy who can come up with the clever intellectual leaps and then fill in the details to prove that the ideas do work.”

What makes Kleinberg’s work distinctive is his ability to marry computer and social sciences. “He is driven by looking outside and then seeking

to explain it,” says Susan L. Graham, computer science professor emerita at the University of California, Berkeley. “There is interesting mathematics behind what he does, but he doesn’t describe it in terms of ‘Here are the theorems I’ve proven.’ He describes it in terms of ‘Here’s how to explain why on average there’s only the distance of six hops from one person to another.’ ”

The ability to bridge scientific disciplines helps explain the popularity of a class Kleinberg teaches at Cornell with economist David Easley. The course,

“There are problem
posers, problem
solvers, and problem
kibitzers,” says
Tom Leighton.
“Jon is very good at
all of the pieces.”

called Networks, examines connections among social, technological, and natural worlds. “We draw from the everyday experiences of our undergrads, who are fluent in applications that enrich social connections, and ask, ‘What’s the science behind it?’ ” Kleinberg says. “That science involves computer science, economics, and the quantitative aspects of the social sciences.”

Prabhakar Raghavan, head of Yahoo! Research, has seen this approach in action since 1996, when he oversaw Kleinberg’s work at Almaden. One evening, they sat outside a Starbucks and watched as people ambled either into the coffee shop or into a Jamba Juice franchise next door. When Jamba Juice closed for the day and Starbucks continued to attract customers for another hour, Kleinberg quipped that Jamba Juice was losing business because it hadn’t done enough data mining to understand the local market dynamics. “Jon has a very pragmatic mind,” says Raghavan, “but he’s always tying it back to the work he has done.”