Skip to main content

more options

Jon Kleinberg

Jon Kleinberg

A network of research...on networks

If you haven't heard of Cornell professor of computer science Jon Kleinberg, then someone you know probably has. Kleinberg is an emerging authority in the study of networks. Though he is only 33, his work has already been noted in a way few others have: Kleinberg was a 2005 recipient of a $500,000 MacArthur Fellowship

This “genius award” comes with no obligations except, ideally, to keep pursuing the ideas that interest him: uncovering the secrets of networks, complex social and technological entities that surround and influence everyone, but that aren't understood very well at all.

“In the past seven to eight years there's been this big explosion of interest in networks,” says Kleinberg. “Part of that is because people are starting to really see them everywhere.”

By “networks” he means any thing that links other things, from material objects (such as power lines or telephone wires) to non-material entities (such as Web pages and hyperlinks) to social relations, like the nexus of personal friendships linking individuals in a human population. Kleinberg means to explore how all networks, no matter how intangible, function: “The interesting thing that has happened in the last few years is that people have begun to discover that many of these networks share similar properties, have similar structures, even though the networks are coming from very different worlds.”

In the mid 1990s, Kleinberg and his colleagues in a project known as the “Clever Project” focused on the problem of making better Web search engines. At that time, most Web searches functioned by simply pointing to the pages that had the most matches to the keyword entered by the user. But this method has an obvious flaw: if someone wants to find sites with material about Cornell, for instance, the engine might miss Web pages that are highly relevant but rarely use the query term “Cornell.” The Clever Project's insight was to concentrate not on the content of the pages, but on the hyperlinks that connect them. An especially relevant site (say, the Cornell homepage) has a lot of links connecting to it from other sites—such sites Kleinberg calls “authorities.” Sites that link to many authorities are called “hubs.” Exploiting this distinction, Kleinberg constructed an automated procedure for finding good “authorities” by looking at the hubs that link to them, and good “hubs” by looking at the quality of the sites to which they point. The method, which has influenced the development of search engines such as Google, Ask.com, and others, is successful because it relies on a fundamental insight: “looking at the network structure of the information offers facts about the information itself.”

More recently, Kleinberg has turned his attention to so-called “small world” networks—networks where the nodes (computers and people) are well-connected on a local level, but not so copiously on a global one. A defining property of some kinds of small world networks is that relatively few such links connect far-flung nodes. This is the famous “six degrees of separation” principle—that anyone on earth is only six relationships removed from anybody else—noted in the 1960s by sociologist Stanley Milgram. Kleinberg has made a quantitative study of the properties of small world networks that make it easier to navigate information from one node to another. Specifically, he's found the sweet-spot—the optimal mix of short and long-range connections—that lies at the crux of any navigable network.

Though Kleinberg's work is supported by such eminent bodies as NSF, the Alfred P. Sloan Foundation, and the David and Lucile Packard Foundation, the no-strings MacArthur award has thrown him somewhat for a loop.

“I'm still really considering what to do with it,” he confesses, looking like a man genuinely surprised to find, at this early phase of his career, all hubs point to him.